Binary Heap

Structure

Let us begin with the structure of a binary heap. It is a binary tree, and also a complete binary tree; each node stores an element (or, equivalently, a value).

Heap property: the value of a parent is no smaller than the value of its child (a max-heap). Similarly, we can define a min-heap. This article uses a max-heap as an example.

By the heap property, the root stores the maximum value (so the getmax operation is immediate).

Process

Insertion

An insertion operation inserts an element into a binary heap while ensuring that the result is still a complete binary tree.

The simplest method is to insert it after the rightmost leaf on the lowest level.

If the lowest level is already full, add a new level.

Could the heap property fail after insertion?

Sift up: If the value of this node is greater than the value of its parent, swap them, and repeat until the property is restored or the root is reached.

It can be proved that after sifting up following an insertion, no other node violates the heap property.

The time complexity of sifting up is $O(\log n)$.

Deletion

A deletion operation removes the largest element from the heap, that is, the root node.

However, deleting it directly would produce two heaps, which is difficult to handle.

Therefore, consider the reverse of insertion: move the root node to the last node and then delete it directly.

In practice this is inconvenient, so the usual method is to swap the root node directly with the last node.

Then delete the root node (now at the last node), but the new root may violate the heap property...

Sift down: Among the node's children, find the largest one and swap it with the node; repeat until reaching the bottom level.

It can be proved that after deletion and sifting down, no other node violates the heap property.

The time complexity is $O(\log n)$.

Increasing a node's value

Clearly, after modifying the value directly, one sift-up operation is enough, with time complexity $O(\log n)$.

Implementation

We find that the operations introduced above mainly rely on two core operations: sifting up and sifting down.

Consider using a sequence $h$ to represent the heap. The two children of $h_i$ are $h_{2i}$ and $h_{2i+1}$, and $1$ is the root node:

Reference code:

void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    std::swap(h[x], h[x / 2]);
    x /= 2;
  }
}

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    std::swap(h[x], h[t]);
    x = t;
  }
}

Building a heap

Consider the following problem: starting with an empty heap, insert $n$ elements in an arbitrary order.

Inserting them one by one takes $O(n \log n)$ time. Is there a better method?

Method 1: use decreasekey (that is, sift up)

Start at the root and proceed in BFS order.

void build_heap_1() {
  for (i = 1; i <= n; i++) up(i);
}

Why does this work? For a node on level $k$, the sifting-up complexity is $O(k)$ rather than $O(\log n)$.

Total complexity: $\log 1 + \log 2 + \cdots + \log n = \Theta(n \log n)$.

(This was proved in “comparison-based sorting”.)

Method 2: use sift down

Now take a different approach: start from the leaves and sift down one node at a time.

void build_heap_2() {
  for (i = n; i >= 1; i--) down(i);
}

Another way to understand this is that each step “merges” two heaps that have already been adjusted, which explains its correctness.

Notice that the complexity of sifting down is $O(\log n - k)$. Also, leaves need no adjustment, so we can start from approximately position $n/2$ in the sequence. This reduces the constant somewhat without changing the complexity.

The reason a heap can be built in $O(n)$ time is that the heap property is weak; a binary heap is not unique.

If we imposed a strong condition like sorting, the situation would be different.

Applications

Two-ended heap

This problem can be further abstracted as dynamically maintaining the $k$-th largest number in a sequence, where $k$ may change.

For this type of problem, we can use the two-ended heap technique (avoiding the cumbersome implementation of a segment tree over values or a BST).

A two-ended heap consists of a max-heap and a min-heap. The min-heap maintains the larger values, namely the largest $k$ values (including the k-th); the max-heap maintains the smaller values, namely all other values smaller than the $k$-th largest value.

This data structure supports the following operations:

• Maintain: when the size of the min-heap is less than $k$, repeatedly remove the top element of the max-heap and insert it into the min-heap until the min-heap has size $k$; when the size of the min-heap is greater than $k$, repeatedly remove the top element of the min-heap and insert it into the max-heap until the min-heap has size $k$;
• Insert an element: if the inserted element is greater than or equal to the top element of the min-heap, insert it into the min-heap; otherwise, insert it into the max-heap, and then maintain the two-ended heap;
• Query the $k$-th largest element: the top element of the min-heap is the answer;
• Delete the $k$-th largest element: delete the top element of the min-heap, then maintain the two-ended heap;
• Change $k$ value by $+1/-1$: maintain the two-ended heap directly according to the new $k$.

Clearly, querying the $k$-th largest element takes $O(1)$ time. After an insertion, deletion, or change to $k$, the size of the min-heap differs from the desired $k$ by at most $1$, so each maintenance operation only needs at most one adjustment of elements between the max-heap and min-heap. Thus, these operations all take $O(\log n)$ time.

#include <iostream>
#include <queue>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t, x;
  cin >> t;
  while (t--) {
    // Max-heap, maintaining the first half of the elements (the smaller values)
    priority_queue<int, vector<int>, less<int>> a;
    // Min-heap, maintaining the second half of the elements (the larger values)
    priority_queue<int, vector<int>, greater<int>> b;
    while (cin >> x, x) {
      // For a query-and-delete operation, output and delete the top of the max-heap
      // This problem asks for the smaller median (with an even number of values there are two median candidates)
      // This differs slightly from the k-th-largest explanation above, but the correspondence is clear after a small adjustment
      if (x == -1) {
        cout << a.top() << '\n';
        a.pop();
      }
      // For an insertion, choose the appropriate heap according to the top value of the max-heap
      else {
        if (a.empty() || x <= a.top())
          a.push(x);
        else
          b.push(x);
      }
      // Adjust the two-ended heap
      if (a.size() > (a.size() + b.size() + 1) / 2) {
        b.push(a.top());
        a.pop();
      } else if (a.size() < (a.size() + b.size() + 1) / 2) {
        a.push(b.top());
        b.pop();
      }
    }
  }
  return 0;
}

Exercises

• SPOJ RMID - Running Median
• Luogu P1801 Black Box