Implementation of Priority Queue using Binary Heap

Intuitionthe queue's highest priority is always at one fixed place

A max-priority queue must return the greatest value currently stored. A binary max-heap makes that value easy to find: the root is always greater than or equal to both children, and the same rule holds recursively for every subtree. Therefore the value to extract is simply the element at index 0 of the heap array.

Insertion may disturb the rule only along the new value's path to the root. Place the value at the next free position, then swap it with its parent while it is larger. Extraction has the reverse shape: save the root, move the last element into index 0, and repeatedly swap it with its larger child until neither child is larger. Choosing the larger child is essential because the parent must remain at least as large as both children.

Approach

1. 1Start with an empty heap array and reserve space for all values, because the heap will contain every inserted value before extraction and repeated reallocations are unnecessary.
2. 2Append each value at the end of the heap, because the new node must occupy the next available position to preserve the complete-tree shape.
3. 3Move the appended value upward while it is greater than its parent, because only the new value can violate the heap rule after an insertion; stop when its parent is already at least as large.
4. 4Save heap[0] as the answer, because the max-heap property guarantees that the root is the greatest value in the queue.
5. 5Move the last element into heap[0] and remove the old last slot, because the replacement fills the root while the heap keeps its complete-tree shape.
6. 6At the current index, compare both existing children against the value at that index and select the larger child, because being larger than only one child is not enough to satisfy the max-heap property.
7. 7Stop when the current value is at least as large as both children, or swap with the selected child and continue downward, because every swap fixes the current position and can create a violation only at the child's new position.
8. 8Return the saved root value after sinking finishes, because the internal heap layout is not part of the result and no further work is needed.

Complexityn is the number of inserted values

Annotated solutionC++ · repeated insertion followed by one extraction

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int extractMax(vector<int> values) {
        vector<int> heap;
        heap.reserve(values.size());

        for (int x : values) {
            heap.push_back(x);
            int i = static_cast<int>(heap.size()) - 1;

            while (i > 0) {
                int parent = (i - 1) / 2;
                if (heap[parent] >= heap[i]) break;
                swap(heap[parent], heap[i]);
                i = parent;
            }
        }

        int answer = heap[0];
        heap[0] = heap.back();
        heap.pop_back();

        int i = 0;
        while (true) {
            int best = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < static_cast<int>(heap.size()) &&
                heap[left] > heap[best]) {
                best = left;
            }
            if (right < static_cast<int>(heap.size()) &&
                heap[right] > heap[best]) {
                best = right;
            }

            if (best == i) break;
            swap(heap[i], heap[best]);
            i = best;
        }

        return answer;
    }
};

The two index updates are the lines that preserve the running-time bound. After an upward swap, i becomes the parent's index, so the loop examines the next level rather than restarting. After a downward swap, i becomes the selected child's index, so the replacement is followed along the only path where a violation can remain. The comparisons use >= for the upward stop and > for child selection, allowing duplicate values to remain in place without affecting correctness.

The bottom-up alternativean O(n) heap build when the insertion order is not part of the work you need to model

You can append all values first and heapify the array from the last internal node back to the root. This is an optimisation: it builds the heap in O(n) time instead of simulating n separate insertions in O(n log n). The extraction step is unchanged and costs O(log n). Bottom-up heapify is usually the better implementation when you only need the final priority queue, while repeated insertion mirrors the stated insertion process more directly.

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
private:
    void siftDown(vector<int>& heap, int i) {
        while (true) {
            int best = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < static_cast<int>(heap.size()) &&
                heap[left] > heap[best]) {
                best = left;
            }
            if (right < static_cast<int>(heap.size()) &&
                heap[right] > heap[best]) {
                best = right;
            }

            if (best == i) break;
            swap(heap[i], heap[best]);
            i = best;
        }
    }

public:
    int extractMax(vector<int> values) {
        vector<int> heap = values;

        for (int i = static_cast<int>(heap.size()) / 2 - 1; i >= 0; --i) {
            siftDown(heap, i);
        }

        int answer = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(heap, 0);

        return answer;
    }
};

Common mistakesthree wrong shapes that look plausible in a heap implementation