## Heap Algorithms

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.