**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.