Heaps & its operation -Max Heap, Min Heap

Heaps, Heap as priority queue, heaps operation, Max Heap, Min Heap.

1. HEAPS Presented by: Aashika Lamichhane Sarika Mainali

2. INTRODUCTION TO HEAPS Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree

3. Types of heap MAX HEAP In a max heap, the parent node's value is always greater than or equal to the values of its children. This arrangement ensures that the maximum element is at the root of the heap

4. Types of heap MIN HEAP A min heap is a binary tree-based data structure where the value of each node is less than or equal to the values of its children. In other words, the smallest element is always at the root. This satisfies the min-heap property. The root node contains the minimum value: 3. Each parent node has a smaller value than its children. It satisfies the property of a min heap.

5. Elements are inserted into a heap next to its right-most leaf at the bottom level. Then the heap property is restored by percolating the new element up the tree until it is no longer ”older” then its parent. On each iteration, the child is swapped with its parent. INSERTING ELEMEN T TO AN HEAP

6. DELETING ELEMENT FROM AN HEAP The heap removal algorithm always removes the root element from the tree. This is done by moving the last leaf element into the root element and the restoring the heap property by per collecting the new root element down the tree until it is no longer “younger” then its children. On each iteration, the parent is swapped with the older of its two children.

7. HEAP AS PRIORITY QUEUE A Priority queue is a BIFO container: The best one in comes out first. That means that each element is assigned a priority number, and the element with the highest priority comes out first. Heaps are commonly used to implement priority queues, where elements are removed based on their priority. The highest (max heap) or lowest (min heap) priority element is always at the root.

8. Operation on Heaps Maintain/Restore the max-heap property MAX-HEAPFY Create a max-heap from an unordered array BUILD-MAX-HEAP Sort an array in place HEAPSORT

9. MAX-HEAPIFY OPERATION Find location of largest value of A[ i ], A[left( i )], A[right( i )] If not A[ i ], max-heap property does not hold. Exchange A[ i ] with the larger of the two children to preserve max-heap property. Continue this process of compare/exchange down the heap until sub-tree rooted at I is a max-heap. At a leaf, the sub-tree rooted at the leaf is trivially a max-heap. Algorithm MAX-HEAPIFY(A, I ,n) { l-=left( i ) R=right( i ) Largest=I If l <=n and A[ i ] > A[largest] Largest=I If r <= n and A[r] > A[largest] largest-=r If largest!=I Exchange(A[ i ] ,A[largest]) MAX-HEAPIFY(A, largest, n) } If any node violets the heap property then swap this node with its larger children to maintain the heap property, this is called heapify .

10. BUILD-MAX-HEAP To build a max-heap from any tree, we can thus start heapifying each sub-tree from the bottom up and end up with a max-heap after the function is applied on all elements including the root element . In this case of complete tree, the first index of non-leaf node is given by n/2-1. Algorithm Build-max-Heap(A) { n =length[A] For( i =floor(n/2); i >=1; i __) { MAX_HEAPIFY(A, I, n); } }

11. heapsort Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum elements at the end. Build a max-heap from any array Swap the root with the last element in the array Discard this last node by decreasing the heap size Perform Max- Heapify operation on the new root node Repeat this process until only one node remains.

12. g Program for implementation of Heap sort #include< stdio.h > Void heapify ( int arr [], int n, int i ) Int largest =I; Int 1=2*i+1; Int r=2*i+2; If(l<n && arr [1] > arr [largest]) Largest=1; If(r< && arr [r] > arr [largest]) Largest=r; If (largest != i ) [ Swap( arr [ i ], arr [largest]); Heapify ( arr , n, largest); }} Void heapsort ( int arr [], int n) { For( int i =n/2-1; i >=0; i --) Heapify ( arr , n, i ); For( int i =n-1;i>=0; i --) { Swap( arr [0], arr [ i ]); Heapify ( arr , I, 0); }} Void printArray ( int arr [], int n){ For( int i =0; i <n; ++ i ) Cout << arr [ i ] << “”; Cout << “/n”; } Int main() { Int arr []={ 12, 11, 13, 5, 6, 7} Int n=6; Heapsort ( arr n); Printf (“Sorted array is \n”); printArray ( arr,n ); } OUTPUT 5 6 7 11 12 13

13. THANK YOU