Max Heap, Min Heap, Heapify, Heap sort, Build max Heap

Max Heap, Min Heap, Heapify, Heap sort

1. Heap (Max/ Min / Heapify ) Prepared By: Mr. Zeeshan Mubeen (Senior Lecturer, RSCI) Unit No. 10

2. What is a Heap? A Heap is a special Tree-based data structure in which the tree is a complete binary tree. It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). Generally, Heaps can be of two types: Max Heap Min Heap

3. Max Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

4. Min Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

5. Traversal Method: The traversal method use to achieve Array representation is Level Order Arr [(i-1)/2] Returns the parent node Arr [(2*i)+1] Returns the left child node Arr [(2*i)+2] Returns the right child node Below table shows indexes of other nodes for the i th node, i.e., Arr [i]:

6. Build Max Heap Build Max-Heap : Using MAX-HEAPIFY() we can construct a max-heap by starting with the last node that has children (which occurs at A.length /2 the elements the array A. BUILD-MAX-HEAP(A) A.heapsize = A.length for i = A.length /2 downto MAX-HEAPIFY( A,i )

7. Max- Heapify : Max- Heapify : Given a tree that is a heap except for node i,Max-Heapify function arranges node i and it’s subtrees to satisfy the heap property.

8. Build max Heap:

9. Build max Heap….

10. Build max Heap….

11. Build max Heap….

12. Heap Sort:

13. Heap Sort….

14. Heap Sort….

15. Heap Sort….

16. Heap Sort….

17. Heap Sort….

18. Heap Sort….

19. Heap Sort….

20. How Heap Sort Works? Since the tree satisfies Max-Heap property, then the largest item is stored at the root node. Swap: Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place. Remove: Reduce the size of the heap by 1. Heapify : Heapify the root element again so that we have the highest element at root. The process is repeated until all the items of the list are sorted.