Heap

#programming #data-structures

A heap is a complete binary tree with an additional ordering property.

A complete binary tree is one where every level is fully filled, except possibly the last
The last level is filled left to right.
This property allows easy storage in arrays.

Types

1. Min heap : Every node $\le$ it's children. Root is minimum
2. Max heap : Every node $\ge$ it's children. Root is maximum

Array representation

For every node, at index $i$,

• Left child is at $2i+1$
• Right child is $2i+2$
• Parent is at $\lfloor (i-1)/2\rfloor$

Core operations

Insert (push)

• Insert at the end
• Fix heap property by bubbling-up (heapify-up).

Steps :

• Add element at last index
• Compare with parent
• Swap if violation of property
• Repeat

Time complexity : $O(\log n)$, since height of tree is $\lfloor \log n\rfloor$

Extract (pop)

• To remove root
• Replace root with last valid element (last in terms of array).
• Delete last element (now root)
• Fix heap property by heapify down

Steps:

• Swap root
• Compare new root
• Swap if violation

Time complexity : $O(\log n)$

Heapify

This refers to the process of building a heap from an unsorted array

Naive approach

Insert element one by one, while continually maintaining heap property and fixing if violated.
Time complexity : $O(n\log n)$

Bottom up heapify

We assume that the last few elements are already leaf nodes. Since they have no children, they can violate no properties (note that property is only with children, not parent).

Precisely, the leaf nodes in an array of size $n$ : $n/2$ to $n-1$.
This means that the last non-leaf node is at index $n/2-1$

Therefore we iterate backwards from that index and go to zero.

At each node, since we would've already processed it's children, we need only to process the current node, and fix it's property (if broken) by using heapify-down.

The advantage is that, since at each node we only work on the existing subtree, and not the entire tree, heapify-down operation is less expensive than $O(\log n)$

For $n/2$ nodes : Height = 0 $⟹$ $O(1)$ work.
For $n/4$ nodes : Height = 1 $⟹$ $O(1)$ work.
For $n/8$ nodes : Height = 2 $⟹$ $O(2)$ work.

Therefore, total work is $n\times (1/2+1/4+1/8\dots )=O(n)$

Therefore,
Time complexity : $O(n)$

Keep in mind

• A heap is not a sorted structure. Only root is guaranteed min/max, subtrees are not ordered.
• Heap is not a BST.
• Duplicate elements are generally fine.

Applications

• Heap Sort
• Prim's Algorithm
• Priority queue