code

Definition:

A Heap is a binary tree storing keys with the following properties:

1. key( child ) <= key ( parent )
2. 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.