C++UCS301
Heaps & Priority QueuesC++17

Binary Heap

A binary heap is a complete binary tree stored compactly in an array and ordered by a min-heap or max-heap property.

What to understand

  • Array index relationships
  • Sift up and sift down
  • Bottom-up heap construction
  • Complete-tree shape

Remember this

  1. 1Parent of i is (i−1)/2
  2. 2Children are 2i+1 and 2i+2
  3. 3Build-heap is O(n), not O(n log n)

Detailed notes

A binary heap combines complete-tree shape with heap order. Completeness permits compact array storage with calculated parent and child indices; heap order guarantees only that the root is extreme, not that siblings or subtrees are fully sorted.

Insertion appends to preserve shape and sifts upward. Extraction replaces the root with the last element, removes the last slot, and sifts downward. Bottom-up build starts at the final internal node and is Θ(n).

How it works

  1. 1Preserve complete shape by appending/removing only at the end.
  2. 2Compare an inserted key with successive parents.
  3. 3During sift-down, exchange with the more extreme child.
  4. 4Build by heapifying internal nodes from right to left.

Worked trace

Insert into a min heap

Heap [3,8,5,12,10], insert 2
  1. 1Append 2 at index 5 to preserve completeness.
  2. 2Parent index is 2, containing 5; swap 2 and 5.
  3. 3New parent index is 0, containing 3; swap again.
  4. 4No parent remains, so sift-up stops.
Result: [2,8,3,12,10,5]

Where it is used

  • Priority queues and schedulers
  • Heap sort and top-k processing
  • Frontier management in graph algorithms

Common mistakes

  • Expecting inorder traversal to be sorted
  • Choosing the left child without comparing both children
  • Claiming bottom-up build is O(n log n)

Complexity analysis

OperationBestAverageWorstExtra space
PeekO(1)O(1)O(1)O(1)
InsertO(log n)O(log n)O(log n)O(1)
ExtractO(log n)O(log n)O(log n)O(1)
Build heapO(n)O(n)O(n)O(1)

C++ implementation

C++17 reference
main.cpp

Min-heap from scratch

Insertion repairs upward; extraction moves the final item to the root and repairs downward.

class MinHeap {
    vector<int> data;
public:
    void push(int value) {
        data.push_back(value);
        int i = data.size() - 1;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (data[parent] <= data[i]) break;
            swap(data[parent], data[i]); i = parent;
        }
    }
    int pop() {
        int answer = data.front();
        data.front() = data.back(); data.pop_back();
        int i = 0;
        while (2 * i + 1 < static_cast<int>(data.size())) {
            int child = 2 * i + 1;
            if (child + 1 < data.size() && data[child + 1] < data[child]) ++child;
            if (data[i] <= data[child]) break;
            swap(data[i], data[child]); i = child;
        }
        return answer;
    }
};
25 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.