DSA SheetEasy
EditorialPractice

HEAP (PRIORITY QUEUE) › INTRODUCTORY QUESTIONS

Implementation of Priority Queue using Binary Heap

EasyEditorial · 8 minGenerated by gpt-5.6-luna · Aug 27

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A binary max-heap stored in an array during extractionA heap is drawn as a tree with the maximum at the top, two children beneath it, and lower levels below. The root is removed and the last array element is placed at the root as the replacement. At each position, the replacement is compared with its left and right children. The larger child is circled, and an arrow shows the replacement swapping with that child and continuing downward. The picture emphasizes that only the replacement's path can violate the heap property, and the larger child must be selected at every step.90returned12replacement55left child42right child1255423018remove maxswap with larger childcompareheap array after max removalThe replacement moves downward by swapping with the larger child.
Extraction restores the heap along one downward path.

Approach

  1. Start 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. Append 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. Move 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. Save heap[0] as the answer, because the max-heap property guarantees that the root is the greatest value in the queue.
  5. Move 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. At 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. Stop 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. Return 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

MEASUREBOUNDWHY
TimeO(n log n)The ith insertion can move up at most the heap height, so summing the worst-case O(log n) work over n insertions gives O(n log n). The one extraction moves down at most the same height and adds O(log n), which does not change the total bound.
SpaceO(n) extraThe heap array stores all n values before the extraction, so its working storage is O(n). The returned integer is output and is excluded from the space bound. The downward walk itself uses O(1) additional variables; even in the worst input shape, the heap array remains O(n).
Here n is the number of values. A complete binary heap has height O(log n), while its array still contains O(n) elements.

Annotated solutionC++ · repeated insertion followed by one extraction

CPPInsert every value with sift-up, then remove the root with sift-down.
#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.

CPPHeapify all values bottom-up, then perform the same root extraction.
#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