Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Priority Queue via Binary Heap

MEDIUMProblemSolveExternal Links

Description

A priority queue is an abstract data structure where each element has an associated priority, and elements with higher priority are served before those with lower priority.

Given a binary heap implementation of a Priority Queue, extract the maximum element from the queue — that is, remove it from the queue and return its value.

A binary max-heap stores elements in a complete binary tree where every parent node is greater than or equal to its children. This structure can be efficiently represented as an array: for a node at index i, its left child is at 2i + 1, its right child is at 2i + 2, and its parent is at (i - 1) / 2.

Examples

Example 1

Input: arr = [4, 2, 8, 16, 24, 2, 6, 5]

Output: 24

Explanation: After inserting all elements into the priority queue, the internal max-heap is [24, 16, 6, 5, 8, 2, 4, 2]. The maximum element 24 sits at the root. After extracting 24, the heap is restructured to [16, 8, 6, 5, 2, 2, 4].

Example 2

Input: arr = [64, 12, 8, 48, 5]

Output: 64

Explanation: The max-heap after all insertions is [64, 48, 8, 12, 5]. The root holds 64 (the maximum). After extraction and heapify-down, the heap becomes [48, 12, 8, 5].

Constraints

  • 1 ≤ n ≤ 500
  • Each element is an integer
  • Expected Time Complexity: O(log n)
  • Expected Auxiliary Space: O(1) (beyond the heap array itself)

Editorial

Brute Force — Unsorted Array

Intuition

Before understanding the heap-based solution, consider the simplest way to implement a priority queue: store elements in a plain unsorted array.

With an unsorted array, inserting an element is instant — just append it to the end in O(1) time. However, to extract the maximum, we have no choice but to scan every element because the maximum could be hiding anywhere. We compare each element against the current best, then remove the winner.

Think of it like finding the tallest person in a crowd with no order. You must walk past every single person and measure each one. You cannot skip anyone because you have no structure telling you where the tallest person stands.

Step-by-Step Explanation

Let's trace extractMax on the unsorted array [4, 2, 8, 16, 24, 2, 6, 5]:

Step 1: Initialize max_val = arr[0] = 4, max_idx = 0. The first element is our starting candidate.

Step 2: Check arr[1] = 2. Is 2 > 4? No. Skip.

Step 3: Check arr[2] = 8. Is 8 > 4? Yes. Update max_val = 8, max_idx = 2.

Step 4: Check arr[3] = 16. Is 16 > 8? Yes. Update max_val = 16, max_idx = 3.

Step 5: Check arr[4] = 24. Is 24 > 16? Yes. Update max_val = 24, max_idx = 4. This is the actual maximum, but we do not know that yet.

Step 6: Check arr[5] = 2, arr[6] = 6, arr[7] = 5. None exceed 24. Scan complete.

Step 7: Remove element at index 4 by swapping with the last element. Array becomes [4, 2, 8, 16, 5, 2, 6]. Return 24.

Brute Force — Linear Scan to Find Maximum — Watch how the linear scan must visit every element to guarantee finding the maximum. Without any structural guarantee, no element can be safely skipped.

Algorithm

  1. Initialize max_val = arr[0], max_idx = 0
  2. For each index i from 1 to n-1:
    • If arr[i] > max_val, update max_val = arr[i] and max_idx = i
  3. Swap arr[max_idx] with arr[n-1] to remove the max element
  4. Reduce the array size by 1
  5. Return max_val

Code

class Solution {
public:
    int extractMax(vector<int>& arr, int n) {
        if (n == 0) return -1;
        
        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        
        int maxVal = arr[maxIdx];
        arr[maxIdx] = arr[n - 1];
        
        return maxVal;
    }
};
class Solution:
    def extractMax(self, arr, n):
        if n == 0:
            return -1
        
        max_idx = 0
        for i in range(1, n):
            if arr[i] > arr[max_idx]:
                max_idx = i
        
        max_val = arr[max_idx]
        arr[max_idx] = arr[n - 1]
        
        return max_val
class Solution {
    int extractMax(int[] arr, int n) {
        if (n == 0) return -1;
        
        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[maxIdx]) {
                maxIdx = i;
            }
        }
        
        int maxVal = arr[maxIdx];
        arr[maxIdx] = arr[n - 1];
        
        return maxVal;
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan through all n elements to find the maximum — there is no way to skip elements without structural guarantees. The swap and removal take O(1). Total: O(n) per extraction.

Space Complexity: O(1)

Only a few variables (max_val, max_idx, i) are used. No additional data structures required.

Why This Approach Is Not Efficient

The unsorted array approach takes O(n) for every extractMax call. If we perform n extractions (to fully drain the queue), the total cost is O(n²). With n up to 500, that is 250,000 operations — manageable for this constraint, but the approach fails to scale.

The fundamental problem is the lack of structure. An unsorted array gives us no information about where the maximum lives, so we must exhaustively search. What if we maintained a specific ordering property that always keeps the maximum in a known position?

Key insight: a binary max-heap guarantees the maximum is always at the root (index 0) — giving us O(1) access to the max. The cost of maintaining this property during removal is just O(log n) for heapify-down, because the heap's tree height is at most log₂(n). For n = 500, that is at most 9 levels versus 500 comparisons.

Bar chart comparing O(n) unsorted array extraction versus O(log n) binary heap extraction for n=500
Bar chart comparing O(n) unsorted array extraction versus O(log n) binary heap extraction for n=500

Optimal Approach - Binary Max-Heap

Intuition

A binary max-heap is a complete binary tree stored as an array where every parent is greater than or equal to its children. This single property gives us a powerful guarantee: the root always holds the maximum element.

To extract the maximum:

  1. Save the root value (that is our answer).
  2. Replace the root with the last element in the array and reduce the heap size by one. This maintains the complete tree structure but may violate the heap ordering.
  3. Perform heapify-down (also called sift-down or percolate-down) from the root: repeatedly swap the misplaced element with its larger child until it reaches a position where it is greater than both children, or it becomes a leaf.

The beauty of this approach is that heapify-down only travels down one path from root to leaf. Since a complete binary tree with n nodes has height at most log₂(n), the operation takes O(log n) time. We never need to examine the entire array — the tree structure guides us directly to the right position.

Think of it like a corporate hierarchy. When the CEO (root) leaves, you promote the janitor (last element) to CEO temporarily. The janitor is clearly unqualified, so they get demoted step by step: compared with their two direct reports, the more qualified one gets promoted. This cascading demotion continues until the janitor reaches a level where they outrank their reports.

Binary max-heap tree showing values 24, 16, 6, 5, 8, 2, 4, 2 with array indices and parent-child formulas
Binary max-heap tree showing values 24, 16, 6, 5, 8, 2, 4, 2 with array indices and parent-child formulas

Step-by-Step Explanation

Let's trace extractMax on the max-heap [24, 16, 6, 5, 8, 2, 4, 2]:

Step 1: The maximum element is at the root: arr[0] = 24. Save max = 24.

Step 2: Replace the root with the last element: arr[0] = arr[7] = 2. Remove the last position. Heap becomes [2, 16, 6, 5, 8, 2, 4] with size 7.

Step 3: The root (2) violates the heap property — it is smaller than its children 16 and 6. Begin heapify-down.

Step 4: Compare root 2 with children: left = 16 (index 1), right = 6 (index 2). Largest child is 16. Swap 2 and 16. Heap: [16, 2, 6, 5, 8, 2, 4].

Step 5: Now at index 1, value 2 has children: left = 5 (index 3), right = 8 (index 4). Largest child is 8. Swap 2 and 8. Heap: [16, 8, 6, 5, 2, 2, 4].

Step 6: Now at index 4, value 2 has no children (indices 9 and 10 exceed heap size 7). Heapify-down terminates.

Step 7: Return 24. The heap [16, 8, 6, 5, 2, 2, 4] is valid — every parent exceeds its children. Total work: 2 swaps across 3 levels.

Max-Heap ExtractMax — Root Removal and Heapify-Down — Watch how the maximum element (root) is extracted by swapping it with the last element, then sinking the replacement down through the tree until the heap property is restored.

Algorithm

  1. Save the root value: max_val = arr[0]
  2. Replace the root with the last element: arr[0] = arr[n-1]
  3. Reduce heap size: n = n - 1
  4. Heapify-down from index 0:
    a. Set i = 0
    b. Compute left = 2i + 1, right = 2i + 2
    c. Find the index of the largest among arr[i], arr[left], arr[right]
    d. If largest == i, stop (heap property satisfied)
    e. Otherwise, swap arr[i] with arr[largest], set i = largest, repeat from (b)
  5. Return max_val

Code

class Solution {
public:
    int extractMax(vector<int>& arr, int n) {
        if (n == 0) return -1;
        
        int maxVal = arr[0];
        arr[0] = arr[n - 1];
        n--;
        
        // Heapify down from root
        int i = 0;
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            
            if (left < n && arr[left] > arr[largest])
                largest = left;
            if (right < n && arr[right] > arr[largest])
                largest = right;
            
            if (largest == i) break;
            
            swap(arr[i], arr[largest]);
            i = largest;
        }
        
        return maxVal;
    }
};
class Solution:
    def extractMax(self, arr, n):
        if n == 0:
            return -1
        
        max_val = arr[0]
        arr[0] = arr[n - 1]
        n -= 1
        
        # Heapify down from root
        i = 0
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < n and arr[left] > arr[largest]:
                largest = left
            if right < n and arr[right] > arr[largest]:
                largest = right
            
            if largest == i:
                break
            
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest
        
        return max_val
class Solution {
    int extractMax(int[] arr, int n) {
        if (n == 0) return -1;
        
        int maxVal = arr[0];
        arr[0] = arr[n - 1];
        n--;
        
        // Heapify down from root
        int i = 0;
        while (true) {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            
            if (left < n && arr[left] > arr[largest])
                largest = left;
            if (right < n && arr[right] > arr[largest])
                largest = right;
            
            if (largest == i) break;
            
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            i = largest;
        }
        
        return maxVal;
    }
}

Complexity Analysis

Time Complexity: O(log n)

Retrieving the root is O(1). The heapify-down traverses at most one path from root to leaf. A complete binary tree with n nodes has height ⌊log₂(n)⌋, so at most ⌊log₂(n)⌋ comparisons and swaps occur. Each comparison and swap is O(1). Total: O(log n).

For n = 500, this means at most 9 swap operations versus the brute force's 500 comparisons.

Space Complexity: O(1)

The heapify-down uses only a constant number of variables (i, largest, left, right, temp). No additional arrays or recursive call stacks are needed (the iterative implementation avoids recursion overhead).