Max-Heap and Priority Queue: Implementation and Applications

Max-Heap and Priority Queue

A max-heap is a complete binary tree where every parent is greater than or equal to its children. The maximum element is always at the root. This is the mirror of a min-heap.

Max-Heap Property

       9
      / \
     7    8
    / \  / \
   3   5 6   2

Every parent ≥ both children. Array: [9, 7, 8, 3, 5, 6, 2]

Operations

The operations are identical to min-heap but with reversed comparisons:

• Insert: Bubble up if the new element is greater than its parent.
• Extract-Max: Remove root, move last element to root, bubble down swapping with the larger child.
• Peek: Return the root (maximum element).

All complexities are the same: insert O(log n), extract O(log n), peek O(1).

Priority Queue

A priority queue is an abstract data type where each element has a priority. The element with the highest priority is served first, regardless of insertion order.

Heaps are the standard implementation:

Priority Queue Operation	Heap Operation	Complexity
Insert with priority	Heap insert	O(log n)
Get highest priority	Peek	O(1)
Remove highest priority	Extract	O(log n)
Update priority	Decrease/Increase key	O(log n)

Min-Heap vs Max-Heap for Priority Queues

• Max-heap: Highest priority = largest value. Used when larger numbers mean higher priority (task scheduling, bandwidth allocation).
• Min-heap: Highest priority = smallest value. Used when smaller numbers mean higher priority (Dijkstra's algorithm where shorter distances have higher priority).

Top-K Problems

Max-heaps and min-heaps are commonly used for top-K problems:

• K largest elements: Use a min-heap of size K. For each new element, if it is larger than the heap's minimum, extract-min and insert the new element. After processing all elements, the heap contains the K largest.

• K smallest elements: Use a max-heap of size K. Mirror logic.

This approach is O(n log K) which is better than sorting O(n log n) when K is much smaller than n.

Comparison with Sorted Array

Operation	Sorted Array	Heap
Insert	O(n)	O(log n)
Get max/min	O(1)	O(1)
Extract max/min	O(1)*	O(log n)

* O(n) if shifting is needed

Heaps are preferred when insertions are frequent. Sorted arrays are preferred when the data is static and only lookups are needed.