Priority Queues and Binary Heaps

A priority queue repeatedly returns the element with the best priority rather than the earliest arrival. A binary heap is a compact implementation stored in an array, with each parent at least as preferred as its children. The whole array is not sorted; only the root is guaranteed to be the extreme element. Priority queues power Dijkstra, scheduling, and greedy choices. Our runnable example repeatedly merges the two smallest weights, minimizing the total merge cost. This demonstrates why a min-heap is useful even when the input initially arrives in arbitrary order.

Prerequisites: Arrays and Vectors, Trees terminology, and basic greedy reasoning.

Build the idea

1. 1. Understand the structural invariant. A complete binary tree fills every level before the next, filling the last from left to right. In a 1-based heap array, children of i are 2i and 2i+1, and its parent is i/2. A min-heap satisfies heap[parent] ≤ heap[child] on every edge; consequently the root is no greater than any descendant. Siblings and distant subtrees need not be ordered relative to each other. For [2,5,3,9,7], both the structure and min-heap order hold, although the array is not sorted.
2. 2. Repair only one root-to-leaf path. To insert, append at the next complete-tree position and swap upward while the new value violates its parent relation. To remove the minimum, replace the root with the last element, shorten the array, then swap downward with the smaller child until order holds. Only one path changes, and a complete tree has logarithmic height. Looking at the minimum does not modify the heap and is O(1). Bottom-up heap construction can be O(n): most nodes lie near leaves and require only short repairs, so summing repair heights is linear rather than n log n.
3. 3. Use the C++ adaptor correctly. priority_queue<long long> is a max-heap by default. priority_queue<long long, vector<long long>, greater<long long>> makes a min-heap. Include queue, vector, and functional explicitly. top reads the best element and pop removes it without returning it. For pair<distance,vertex>, comparisons are lexicographic: distance is compared first and vertex breaks ties. The comparator must define a strict ordering; using <= as a “less-than” predicate violates the requirements.
4. 4. Work through optimal merging. Merging weights x and y costs x+y and produces one item of that combined weight. For [4,3,2,6], merge 2+3=5, then 4+5=9, then 6+9=15. Total cost is 5+9+15=29. A min-heap performs exactly the repeated choice of the two smallest current weights. The merged value must be inserted back because it participates in later decisions. Sorting only the original list and never reinserting combined values does not maintain the set of available choices.
5. 5. Why the greedy choice is safe. A full merge plan forms a binary tree: original items are leaves, and each merge is an internal node. Total cost equals the sum of each original weight times its leaf depth. For nonnegative weights, a plan can be chosen with the two smallest weights at two deepest sibling leaves: swapping a smaller weight downward with a larger one cannot increase cost. Merge that sibling pair first and replace it by their sum. The remaining problem has the same form, so induction proves the greedy algorithm. Nonnegative weights are part of the model; do not silently apply this reasoning to an unrelated merge objective.
6. 6. Connect to Dijkstra and limits. Dijkstra stores candidate distances in a min-priority queue. std::priority_queue has no decrease-key operation; push a new improved candidate and ignore an old entry when its popped distance differs from dist[v]. A heap is not a FIFO queue and does not support arbitrary search or removal efficiently. The merge program uses long long for both merged weights and accumulated cost, and checks additions for overflow. A single item needs no merge, so its cost is zero; an empty collection also costs zero.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
#include<limits>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)||n<0){
        return 0;
    }
    // greater makes the smallest current weight accessible at top().
    priority_queue<long long,vector<long long>,greater<long long>>pq;
    for(int i=0;i<n;++i){
        long long x;
        cin>>x;
        if(x<0){
            cout<<"INVALID\n";
            return 0;
        }
        pq.push(x);
    }
    long long total=0;
    const long long limit=numeric_limits<long long>::max();
    while(pq.size()>=2){
        // Remove the two smallest available groups for the greedy merge.
        long long x=pq.top();
        pq.pop();
        long long y=pq.top();
        pq.pop();
        if(x>limit-y){
            cout<<"OVERFLOW\n";
            return 0;
        }
        long long combined=x+y;
        if(total>limit-combined){
            cout<<"OVERFLOW\n";
            return 0;
        }
        total+=combined; // Pay for this merge exactly once.
        pq.push(combined); // The result is available for another merge.
    }
    cout<<total<<'\n';
}

Complexity analysis

top is O(1); each push/pop performs O(log n) heap comparisons. The standard vector-backed queue can occasionally reallocate, so a single push may also incur linear storage movement, while repeated pushes retain the usual amortized O(log n) cost. Inserting n inputs and doing n−1 merges takes O(n log n) total time and O(n) storage. Constructing a heap directly from a range can build the initial heap in O(n), but the merge loop still costs O(n log n).

Example input and output

Read n ≥ 0, then n nonnegative signed-64-bit weights. Print the minimum total binary-merge cost. The program prints INVALID for a negative weight and OVERFLOW if an intermediate sum or total cannot fit in signed 64 bits.

Input

4
4 3 2 6

Output

29

Merge 2 and 3 for cost 5; merge 4 and 5 for cost 9; merge 6 and 9 for cost 15. The total is 29, which is optimal for nonnegative merge weights.

Practical applications

Priority queues support Dijkstra, greedy merging, event simulation, scheduling by earliest finishing time, and keeping the best k candidates. Two heaps maintain a streaming median. Heap Sort uses the same heap-order idea to sort in O(n log n) worst-case time with constant auxiliary array storage.

Check your understanding

Which property is guaranteed by a min-heap?

Put it into practice

Maintain the k largest input values while reading a long stream, using only O(k) extra memory.