Binary Heap

Min/max binary heap with push, pop, and top in O(log n).

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#heap#priority-queue#binary-heap

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

struct Heap {
    vector<int> a;
    int sz = 0;

    Heap() { a.push_back(0); }

    bool cmp(int i, int j) { return a[i] < a[j]; }

    void up(int i) {
        while (i > 1 && cmp(i, i / 2)) {
            swap(a[i], a[i / 2]);
            i /= 2;
        }
    }

    void down(int i) {
        while (2 * i <= sz) {
            int j = 2 * i;
            if (j + 1 <= sz && cmp(j + 1, j)) j++;
            if (cmp(i, j)) break;
            swap(a[i], a[j]);
            i = j;
        }
    }

    void push(int x) { a.push_back(x); sz++; up(sz); }

    void pop() { swap(a[1], a[sz]); a.pop_back(); sz--; down(1); }

    int top() { return a[1]; }

    bool empty() { return sz == 0; }

    int size() { return sz; }
};

38 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Binary Heap

Complete binary tree stored in a 1-indexed array. Parent of node $i$ is $\lfloor i/2 \rfloor$ , children are $2i$ and $2i+1$ .

Operations

push(x) — insert element, bubble up to restore heap property

pop() — remove top, swap with last, bubble down

top() — peek at min/max element

Heap Property

Min-heap — parent

\le

children (default)

Max-heap — parent

\ge

children (change comparator)

When to Use

Priority queue implementation

Understanding how priority_queue works internally

When you need custom heap behavior beyond std::priority_queue

Notes

In contests, priority_queue, greater> is usually sufficient for min-heap

This template is for learning or when custom heap operations are needed

Complexity

Push / Pop —

O(\log n)

Top —

O(1)

Space —

O(n)