Heap Tree

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1

Heap of height h

• The levels above the lowest level form a complete binary tree of height h -1 and 2^h -1 nodes.
• minimum number of nodes possible in a heap of height h is 2^h.
• maximum number of nodes is 2^h+1 -1 nodes.

Four basic procedures on heap are

1. Heapify, which runs in O(log n) time.
2. Build-Heap, which runs in linear time.
3. Heap Sort, which runs in O(n log n) time.
4. Extract-Max, which runs in O(log n) time