DATA STRUCTURES
🇬🇧UK Edition🇨🇦Canada Edition🌐Global Tech

Building a Binary Heap & Priority Queue in C++20

Dr. Alistair Vance
Dr. Alistair Vance
Principal CS Fellow
Updated 03/09/20266 min read0 views

Heap Array Index Representation

For a node at index i:

  • Left child = 2i + 1

  • Right child = 2i + 2

  • Parent = (i - 1) // 2

cpp
#include <iostream>
#include <vector>
#include <algorithm>

class MinHeap {
    std::vector<int> heap;
public:
    void push(int val) {
        heap.push_back(val);
        std::push_heap(heap.begin(), heap.end(), std::greater<int>());
    }
    int pop() {
        std::pop_heap(heap.begin(), heap.end(), std::greater<int>());
        int minVal = heap.back();
        heap.pop_back();
        return minVal;
    }
};

int main() {
    MinHeap h;
    h.push(40);
    h.push(10);
    h.push(30);
    std::cout << "Min Element: " << h.pop() << std::endl;
    return 0;
}

Frequently Asked Questions (FAQ)

Q: What is the time complexity of buildHeap?

Building a heap from an array of N elements takes O(N) linear time.

Dr. Alistair Vance
Written by Dr. Alistair VanceAdSense EEAT Verified

Principal CS Fellow. Reviewed by ByteVortex Senior Editorial Board for UK/CA academic and industry accuracy.