In-Depth Analysis of Binary Heap Structure and Operations

Core Logic and Mathematical Principles

A binary heap is essentially a complete binary tree that satisfies specific heap properties. Its core logic utilizes the contiguous memory space of an array, implicitly maintaining the tree topology through arithmetic relationships of indices, thereby eliminating pointer overhead.

For a complete binary tree with a root node indexed at $1$, the topological geometric relationships of any node $i$ are as follows:

Left child index: $\text{left}(i) = 2i = i \times 2$
Right child index: $\text{right}(i) = 2i + 1 = (i \times 2) + 1$
Parent index: $\text{parent}(i) = \frac{i}{2}$

Taking a max-heap as an example, its mathematical total order relationship must strictly satisfy:

$$\forall i > 1, \quad \text{heap}[\text{parent}(i)] \ge \text{heap}[i]$$

The dynamic maintenance operations of the binary heap are based on two underlying heapification mechanisms, both with a time complexity of $O(\log N)$:

Shift Up: When inserting a new element at the bottom of the heap, if this element violates the heap property, it is swapped up the parent chain until the total order relationship is satisfied.
Shift Down: When popping the highest quality element from the top of the heap, the last element from the bottom of the heap is moved to the top, and then this element is swapped down the path of the larger of its two children until the subtree is re-established.

State Design and Algorithm Derivation

The state of a handwritten binary heap is minimal, requiring only a one-dimensional static array heap[] and a counter sz to record the current number of elements.

1. Push Operation (Insertion) and Shift Up Derivation

The new element is placed at heap[++sz]. Let the current index being examined be $curr$:

Condition: If $curr > 1$ and $\text{heap}[curr] > \text{heap}[curr \times 2]$.
State Transition: Swap the two, setting $curr = curr / 2$, and continue iterating.
Termination Condition: Reach the root node ($curr = 1$) or the current node is no longer greater than its parent.

2. Pop Operation (Deletion) and Shift Down Derivation

Release the top of the heap by executing heap[1] = heap[sz--]. Let the current sinking index be $curr$:

Condition: Find its left child $t = curr \times 2$. If $t \le sz$, it indicates the existence of a left child.
Sibling Comparison: If $t + 1 \le sz$ and $\text{heap}[t+1] > \text{heap}[t]$, it indicates that the right child is larger, so the target pointer is adjusted to the right child, i.e., $t = t + 1$.
Sinking Condition: If $\text{heap}[t] > \text{heap}[curr]$, swap heap[curr] with heap[t], set $curr = t$, and continue sinking.
Termination Condition: Child index $t > sz$ (reached the bottom) or the current node is greater than all its children.

C++ Standard Source Code

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

// Strictly limit the space size to prevent constant degradation from dynamic memory allocation
const int MAXN = 100005;

struct MaxHeap {
    int heap[MAXN];
    int sz;

    // Explicit initialization, do not rely on default implicit constructors
    MaxHeap() : sz(0) {}

    // Shift Up: Maintain the heap when a new element is added
    void push(int val) {
        heap[++sz] = val;
        int curr = sz;
        // Critical pitfall: must check curr > 1 before accessing the parent node, otherwise when curr=1, 1/2 becomes 0 and will trigger an out-of-bounds error
        while (curr > 1 && heap[curr] > heap[curr / 2]) {
            std::swap(heap[curr], heap[curr / 2]);
            curr /= 2;
        }
    }

    // Return the top element of the heap
    int top() const {
        return heap[1];
    }

    // Shift Down: Maintain the heap when popping the top
    void pop() {
        if (sz == 0) return;
        heap[1] = heap[sz--];
        int curr = 1;
        while ((curr * 2) <= sz) {
            int t = curr * 2; // Default points to the left child
            // Critical pitfall: Right child boundary check t + 1 <= sz must be written first, otherwise it will lead to out-of-bounds access of non-heap data
            if (t + 1 <= sz && heap[t + 1] > heap[t]) {
                t++; // Lock in the absolute winner among the left and right children
            }
            if (heap[curr] >= heap[t]) {
                break; // Heap property has been restored, forcibly cut off the sinking branch
            }
            std::swap(heap[curr], heap[t]);
            curr = t; // Advance the iteration state
        }
    }

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

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (std::cin >> n) {
        MaxHeap my_heap;
        for (int i = 0; i < n; ++i) {
            int val;
            std::cin >> val;
            my_heap.push(val);
        }

        while (!my_heap.empty()) {
            std::cout << my_heap.top() << " ";
            my_heap.pop();
        }
        std::cout << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

Building the heap with array indices starting from 0 leads to calculation collapse Some contestants habitually set the heap top at heap[0]. In this case, the left child calculation formula becomes $2i+1$, the right child becomes $2i+2$, and the parent becomes $\frac{i-1}{2}$. When retrieving the parent node, if $i=0$, $\frac{0-1}{2}$ under C++'s rounding towards zero rule will still be $0$, directly triggering a while (heap[curr] > heap[(curr-1)/2]) infinite loop. Therefore, handwritten heaps must strictly store starting from index 1.
Shift Down left and right child selection logic short circuit When shifting down, contestants often write if (heap[curr*2+1] > heap[curr*2]) t = curr*2+1; logic, missing the boundary check for whether the right child exists (curr*2+1) <= sz. If the current node only has a left child, the code will forcibly read the residual dirty data at position sz+1 for size comparison, causing the sinking path of the max-heap to be hijacked by dirty data, leading to heap property collapse or random logical errors.

Classic NOIP/Luogu Problems

1. Luogu P1177 [Template] Quick Sort / Sorting

Problem Description: Given a random sequence of length $N$, sort it from smallest to largest.
Essential Problem: Non-linear output of a total order set, using a heap to achieve $O(N \log N)$ sorting.
Core Problem-Solving Idea: Construct a min-heap (or max-heap). Push all elements into the handwritten heap using the push operation, then continuously read top and execute pop in a while loop. The handwritten binary heap offers a more stable worst-case complexity guarantee than std::sort in such high-intensity data sorting tests.

2. Luogu P1090 [NOIP2004 Advanced Group] Merging Fruits / [USACO06NOV] Fence Repair G

Problem Description: In a sequence, each time select the two piles of fruits with the smallest weight to merge, the weight of the merged new fruit pile is the sum of the two piles, and the physical effort consumed is the weight of the new pile. Find the minimum physical effort to merge all fruits into one pile.
Essential Problem: Greedy strategy optimization in the process of constructing a Huffman tree.
Core Problem-Solving Idea: Use a handwritten min-heap to maintain the current collection of fruits. Each time, use top and pop to consecutively retrieve the two globally smallest elements $A$ and $B$, add them to the answer, and then push the merged new element $A+B$ back into the min-heap. Repeat this process $N-1$ times, optimizing the originally $O(N^2)$ brute force search to $O(N \log N)$ using the dynamic maintenance capability of the heap.