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 lies in utilizing the contiguous memory space of an array to implicitly maintain the tree topology through arithmetic relationships of indices, thereby eliminating pointer overhead.

For a complete binary tree rooted at index $1$, the topological geometric relationships of any node $i$ satisfy:

Left child index: $2i$
Right child index: $2i + 1$
Parent index: $\lfloor i/2 \rfloor$

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

$$\forall i > 1, \quad \text{heap}[\lfloor i/2 \rfloor] \ge \text{heap}[i]$$

The dynamic maintenance operations of a 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 upward along the parent chain until the total order relationship is satisfied.
Shift Down: When popping the highest-priority element from the top of the heap, the last element from the bottom is moved to the top, and then this element is swapped downward along the path of the larger of its two children until the subtree property is restored.

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 under examination be $curr$:

Condition: If $curr > 1$ and $\text{heap}[curr] > \text{heap}[\lfloor curr/2 \rfloor]$.
State Transition: Swap the two, set $curr = \lfloor curr/2 \rfloor$, 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

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

Condition: Find its left child $t = 2 \times curr$. If $t \le sz$, a left child exists.
Sibling Comparison: If $t + 1 \le sz$ and $\text{heap}[t+1] > \text{heap}[t]$, the right child is larger, so adjust the target pointer to the right child: $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++ Core Template Code (NOI Style)

const int MAXN = 100005;
int heap[MAXN], sz = 0;

void push(int val) {
    heap[++sz] = val; // Place the new element at the bottom of the heap
    int curr = sz;
    // Shift Up: must ensure curr > 1 to avoid out-of-bounds access to heap[0]
    while (curr > 1 && heap[curr] > heap[curr / 2]) {
        swap(heap[curr], heap[curr / 2]);
        curr /= 2; // Move up along the parent path
    }
}

void pop() {
    if (sz == 0) return;
    heap[1] = heap[sz--]; // Overwrite the top with the bottom element and decrement the size
    int curr = 1;
    // Shift Down: continue as long as a left child exists
    while ((curr * 2) <= sz) {
        int t = curr * 2; 
        // Critical boundary check: must first confirm t + 1 <= sz to prevent out-of-bounds reading of residual dirty data
        if (t + 1 <= sz && heap[t + 1] > heap[t]) {
            t++; // Lock in the larger of the left and right children
        }
        if (heap[curr] >= heap[t]) {
            break; // Parent already satisfies heap property, terminate sinking early
        }
        swap(heap[curr], heap[t]);
        curr = t; // Update the current node index and continue iterating
    }
}

int top() {
    return heap[1]; // O(1) return of the heap top extremum
}

NOIP Practical Pitfall Guide

Building the heap with array indices starting from 0 leads to calculation collapse Some contestants habitually place the heap top at heap[0]. In this case, the left child calculation becomes $2i+1$, the right child becomes $2i+2$, and the parent becomes $\lfloor (i-1)/2 \rfloor$. When retrieving the parent node, if $i=0$, the computation $(0-1)/2$ under C++'s rounding toward zero rule still yields 0, which directly triggers an infinite upward loop. Therefore, handwritten heaps must strictly start storage from index 1.
Shift Down left and right child selection logic short circuit When performing Shift Down, directly writing the comparison logic if (heap[curr*2+1] > heap[curr*2]) misses the boundary check for the existence of the right child: $(curr \times 2 + 1) \le sz$. If the current node only has a left child, the code will forcibly read residual dirty data at position sz+1 for comparison. This causes the sinking path to be hijacked by dirty data, leading to heap property corruption.

Classic NOIP/Luogu Problems

1. Luogu P1177 [Template] Sorting

Problem Description: Given a sequence of length $N$, sort it from smallest to largest and output the result.
Problem Essence: Non-linear output of a totally ordered set, using a heap to achieve $O(N \log N)$ sorting.
Core Solution Idea: Build a min-heap. Push all elements into the heap using push, then continuously call top and pop in a loop to achieve stable sorting.

Core Code (Min-Heap Sorting Application):

// Assume the max-heap template above has been modified to a MinHeap
MinHeap my_heap;
for (int i = 1; i <= n; ++i) {
    my_heap.push(a[i]); // Insert all elements into the heap
}
for (int i = 1; i <= n; ++i) {
    a[i] = my_heap.top(); // Retrieve the current global minimum in order
    my_heap.pop();
}

2. Luogu P1090 [NOIP2004 Advanced Group] Merging Fruits

Problem Description: Each operation selects the two piles with the smallest weight to merge, with the physical effort consumed equal to the weight of the new pile. Find the minimum total physical effort required to merge all fruits into one pile.
Problem Essence: Greedy strategy optimization during the construction of a Huffman Tree.
Core Solution Idea: Each operation requires dynamically retrieving and deleting the two global minimum elements, and inserting a new element. Directly use STL's priority queue to implement a min-heap, optimizing the original $O(N^2)$ search down to $O(N \log N)$.

Core Code (STL Priority Queue Implementation):

#include <queue>
#include <vector>

// Define STL min-heap
priority_queue<int, vector<int>, greater<int>> pq;

int ans = 0;
// Assume the initial weights of the n fruit piles have all been pushed into pq
for (int i = 1; i < n; ++i) { // Merging n piles requires n-1 operations
    int a = pq.top(); pq.pop(); // Retrieve the smallest pile
    int b = pq.top(); pq.pop(); // Retrieve the second smallest pile

    ans += (a + b);       // Accumulate the physical effort of this merge
    pq.push(a + b);       // Re-insert the merged new pile
}
// After the loop ends, ans is the minimum total physical effort