Priority Queue

Binary Heap

A complete binary tree optimized for constant-time maximum or minimum retrieval.

What is Binary Heap?

A Binary Heap is a complete binary tree stored inside an array that satisfies the heap property. In a Max Heap, for any given node I, the value of I is greater than or equal to the values of its children, making the root the maximum element. In a Min Heap, the value of I is less than or equal to its children, making the root the minimum element. Heaps are extremely efficient for sorting (Heapsort) and Priority Queues.

Key Characteristics:

  • Maintains a complete binary tree structure
  • Array mapping: left = 2*i + 1, right = 2*i + 2, parent = floor((i-1)/2)
  • Max Heap root holds maximum value; Min Heap root holds minimum value
  • Heapify operations restore tree properties dynamically

Complexity Analysis

Avg Time Complexity: O(log n) for Insert & Extract, O(1) for Peek
Space Complexity: O(n) space in array format
Best Case: O(1) (peeking root or inserting with no violations)
Worst Case: O(log n) (heapifying up/down the full tree height)

How it Works Step-by-Step

  1. Insert: Append node at the end of the array, then Heapify Up to resolve violations.
  2. Extract Root: Swap root with the last element, pop last element, then Heapify Down from root.
  3. Heapify Up: Compare node with parent; swap if heap property is violated, and recurse.
  4. Heapify Down: Compare node with children; swap with the larger/smaller child, and recurse.

Code Implementation

Worked Trace Example

Inserting 45 into Max Heap [40, 30, 20]:
1. Append 45: [40, 30, 20, 45]
2. Compare 45 with parent 30: 45 > 30, swap -> [40, 45, 20, 30]
3. Compare 45 with parent 40: 45 > 40, swap -> [45, 40, 20, 30]
Result: 45 is now root.