Definition:
A Heap is a binary tree storing keys with the following properties:
- key( child ) <= key ( parent )
- left-filled levels
- the last level is left-filled
- the other levels are full
Properties:
- The cost of Heapify is proportional to the number of level visited. T( n ) = O( n ).
- Cost of HeapInsert is T ( n ) = O ( lgn )
- Cost of RemoveMax is T ( n ) = O ( lgn )
- Cost of HeapSort is T ( n ) = O ( n lgn )
- leftchild ( i ) = 2i
- rightchild ( i ) = 2i +1
- parent ( i )= floor ( i/2 )
Heapfy Algorithm
Assumes L and R subtrees of i are already heaps.
Pseudecode of Heapify:
Heapify ( A, i) l = LEFT (i); r = RIGHT (i); if ( l <= heapSize ( A ) and A[ l ] > A[ i ] ) then largest = l ; else largest=i ; if ( r <= heapSize ( A ) and A[ l ]> A[ i ] ) then largest = r ; if ( largest != i ) then exchange A [ i ] and A[ largest ] ; Heapify( A, largest ); End
Pseudecode of Building A Heap:
BuildingHeap ( A ) for i = floor ( n/2 ) down to 1 do Heapify ( A , i ); End
In figure, A is written as binary heap. There are 10 nodes in the tree. From 5th node, Heapify algorithm starts to run.
Step A: i=5, There is no change.
Step B: i=4, 2 exchanges with 14.
Step C: i=3, 3 exchanges with 10.
Step D: i=2, 1 exchanges with 16, then 1 exchanges with 7.
Step E: i=1, 4 exchanges with 16, then 4 exchanges with 14, then 4 exchanges with 8.
Step F: Final Heap.
Pseudecode of Remove Max:
HeapRemoveMax(A) Remove A [ 1 ] A[1]= A[ heapSize [ A ] ] heapSize-- Heapify( A , 1 ) End
Pseudecode of Heap Insert:
HeapInsert ( A, key ) heapSize ( A ) ++ i = heapSize ( A ) while ( i > 1 and A[ parent ( i ) ] < key ) A[ i ] = A [ parent ( i ) ] i=parent( i ) A[ i ] = key
Heap Sort:
Pseudecode of Heap Sort:
HeapSort ( A ) BuildHeap ( A ) for i = n down to 2 do Exchange A [ 1 ] and A [ i ] heapSize -- Heapify ( A, 1 ) endfor End
How does Heap Sort work?
Step A: 1 exchanges with 16. HeapSize decreases (write 16 at the end of the array now), then Heapify.
Step B: 1 exchanges with 14. HeapSize decreases (write 14 after 16), then Heapify.
Step C: 2 exchanges with 10. HeapSize decreases (write 10 after 14), then Heapify.
Step D: 2 exchanges with 9. HeapSize decreases (write 9 after 10), then Heapify.
Step E: 1 exchanges with 8. HeapSize decreases (write 8 after 9), then Heapify.
Step F: 2 exchanges with 7. HeapSize decreases (write 7 after 8), then Heapify.
Step G: 1 exchanges with 4. HeapSize decreases (write 4 after 7), then Heapify.
Step H: 1 exchanges with 3. HeapSize decreases (write 3 after 4), then Heapify.
Step I: 1 exchanges with 2. HeapSize decreases (write 2 after 3), then Heapify.
Step J: Only 1 remains, write 1 after 2. And list is sorted.