Binary Heap - Course 3

Module 1: 2D DP

Longest common subsequence (LCS)
Longest Increasing Subsequence (LIS)
Longest Increasing Subsequence (LIS) in $O(N \log N)$
Knapsack problem
Lazy DP

Module 2: DSU

System of disjoint sets

Module 3: MST

Minimum and maximum spanning trees
Kruskal's Algorithm
Prim's Algorithm
Borůvka's Algorithm

Module 4: Combinatorics

Stars and columns
The principle of inclusion-exclusion

Module 5: Geometry

Finding the area of a simple polygon

Module 6: Arbitrary-Precision Arithmetic

Long Arithmetic

Module 7: Data structures for keeping minimum

Stack with Minimum
Queue with Minimum
Deque with Minimum

Module 8: Heap [BONUS]

Binary Heap

Home Courses Resources Problems National Olympiad Contests Leaderboard

...

Home/Courses/Course 3/Module 8: Heap [BONUS]/Binary Heap

Binary Heap

Binary Heap

Binary Heap (Binary Heap)

Introduction

A binary heap (binary heap) is a binary rooted tree for which the following conditions hold:

Each vertex has no more than two children.
The value of any vertex is not less than the values in its children (this is a max-heap).

Also, a heap is an almost complete binary tree:

On the $i$ -th (starting from zero) layer there are $2^i$ vertices, except for the last.
The last layer is filled from left to right.

Structure

It is convenient to store the heap in an array $a_0, a_1, \ldots, a_{n-1}$ .

,

a1

,

…

,

an−1

Root: $a_0$
Children of vertex $a_i$ $a_{i}$ :
- left: $a_{2i+1}$
- right: $a_{2i+2}$

The height of the heap is $O(\log N)$ , so the main operations are performed quickly.

Two key procedures

We always maintain the heap property, where each parent $\geq$ its children. Thanks to this, the maximum is always at the root.

`sift_up(i)` — sifting up

Used with push.

Algorithm:

Insert the element at the end of the array.
While the element is greater than its parent:
- swap them
- move up to the parent

Since the height of the heap is $O(\log N)$ , the operation runs in $O(\log N)$ .

`sift_down(i)` — sifting down

Used with pop.

Algorithm:

Swap the root with the last element.
Remove the last element.
Sift the new root down:
- choose the larger child
- if the child is greater than the parent — swap them
- continue the process

Also runs in $O(\log N)$ .

Implementation

struct Heap {
    vector<int> a;

    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * i + 2; }

    void sift_up(int i) {
        while (i > 0 && a[parent(i)] < a[i]) {
            swap(a[parent(i)], a[i]);
            i = parent(i);
        }
    }

    void sift_down(int i) {
        while (true) {
            int l = left(i);
            int r = right(i);
            int best = i;

            if (l < (int)a.size() && a[l] > a[best]) {
                best = l;
            }
            if (r < (int)a.size() && a[r] > a[best]) {
                best = r;
            }

            if (best == i) {
                break;
            }

            swap(a[i], a[best]);
            i = best;
        }
    }

    void push(int x) {
        a.push_back(x);
        sift_up((int)a.size() - 1);
    }

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

    void pop() {
        a[0] = a.back();
        a.pop_back();
        if (!a.empty()) {
            sift_down(0);
        }
    }

    bool empty() {
        return a.empty();
    }

    int size() {
        return (int)a.size();
    }
};