Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Min-Heap & Max-Heap Implementation

MEDIUMProblemSolveExternal Links

Description

You are given an empty Binary Min-Heap and a series of queries. Your task is to implement three fundamental heap operations:

  1. insertKey(x): Insert an element with value x into the min-heap.
  2. deleteKey(pos): Remove the element at the given position pos from the min-heap.
  3. extractMin(): Remove and return the minimum element from the min-heap. If the heap is empty, return -1.

A binary min-heap is a complete binary tree where the value of each node is less than or equal to the values of its children. It is efficiently stored as an array where for any element at index i:

  • Left child is at index 2i + 1
  • Right child is at index 2i + 2
  • Parent is at index ⌊(i − 1) / 2⌋

Examples

Example 1

Input: Q = 7
Queries: insertKey(4), insertKey(2), extractMin(), insertKey(6), deleteKey(0), extractMin(), extractMin()

Output: [2, 6, -1]

Explanation:

  • insertKey(4): Heap becomes {4}
  • insertKey(2): 2 is smaller than its parent 4, so it bubbles up to the root. Heap becomes {2, 4}
  • extractMin(): Removes and returns the root element 2. Heap becomes {4}
  • insertKey(6): 6 is larger than its parent 4, so no swap needed. Heap becomes {4, 6}
  • deleteKey(0): Removes the element at position 0 (value 4). Heap becomes {6}
  • extractMin(): Removes and returns 6. Heap becomes empty {}
  • extractMin(): Heap is empty, so return -1

Example 2

Input: Q = 5
Queries: insertKey(8), insertKey(9), deleteKey(1), extractMin(), extractMin()

Output: [8, -1]

Explanation:

  • insertKey(8): Heap becomes {8}
  • insertKey(9): 9 > 8 (parent), no swap needed. Heap becomes {8, 9}
  • deleteKey(1): Removes element at position 1 (value 9). Heap becomes {8}
  • extractMin(): Removes and returns 8. Heap becomes empty {}
  • extractMin(): Heap is empty, returns -1

Constraints

  • 1 ≤ Q ≤ 10^4
  • 1 ≤ x ≤ 10^4
  • 0 ≤ pos < current heap size (for deleteKey operations)

Editorial

Brute Force

Intuition

The most straightforward way to support insert, delete, and extract-minimum operations is to use an ordinary unsorted array.

Think of it like an unorganized drawer of numbered cards. To add a card, you simply toss it in anywhere — instant and effortless. But when you need to find the smallest card, you have to rummage through every single card in the drawer, checking each one. Similarly, deleting a specific card by its position means pulling it out and pushing all the cards behind it forward to close the gap.

This approach is simple to implement but pays a heavy price for the extract-minimum operation because the array has no ordering to exploit. Every time we need the minimum, we must check every element from scratch.

Step-by-Step Explanation

Let's trace through Example 1 with queries: insertKey(4), insertKey(2), extractMin(), insertKey(6), deleteKey(0), extractMin(), extractMin()

Step 1: insertKey(4)

  • Append 4 to the end of the array.
  • Array: [4]

Step 2: insertKey(2)

  • Append 2 to the end. No reordering.
  • Array: [4, 2]

Step 3: extractMin() — Start scanning

  • Need to find the minimum by scanning every element.
  • Check index 0: value = 4. Assume this is the minimum so far.

Step 4: extractMin() — Continue scanning

  • Check index 1: value = 2. Is 2 < 4? Yes.
  • Update minimum to 2 at index 1. Scan complete.

Step 5: extractMin() — Remove minimum

  • Remove element at index 1 (value 2). Return 2.
  • Array: [4]. Output so far: [2]

Step 6: insertKey(6)

  • Append 6. Array: [4, 6]

Step 7: deleteKey(0)

  • Remove element at index 0 (value 4). Shift remaining elements left.
  • Array: [6]

Step 8: extractMin()

  • Scan array: only element is 6. Minimum = 6.
  • Remove and return 6. Array: []. Output: [2, 6]

Step 9: extractMin() — Empty array

  • Array is empty. Return -1.
  • Final output: [2, 6, -1]

Brute Force — Unsorted Array Operations — Watch how the unsorted array handles insert, extractMin (via linear scan), and deleteKey (via shifting). Notice the O(n) cost of finding the minimum each time.

Algorithm

insertKey(x):

  1. Append x to the end of the array

extractMin():

  1. If the array is empty, return -1
  2. Scan the entire array to find the index of the minimum element
  3. Store the minimum value
  4. Remove the element at that index (shift remaining elements)
  5. Return the stored minimum value

deleteKey(pos):

  1. If pos is out of bounds, return
  2. Remove the element at the given position (shift remaining elements)

Code

#include <vector>
using namespace std;

class MinHeap {
    vector<int> arr;

public:
    // Insert element at the end - O(1)
    void insertKey(int val) {
        arr.push_back(val);
    }

    // Scan entire array to find and remove minimum - O(n)
    int extractMin() {
        if (arr.empty()) return -1;

        int minIdx = 0;
        for (int i = 1; i < (int)arr.size(); i++) {
            if (arr[i] < arr[minIdx]) {
                minIdx = i;
            }
        }

        int minVal = arr[minIdx];
        arr.erase(arr.begin() + minIdx);
        return minVal;
    }

    // Remove element at given position - O(n)
    void deleteKey(int pos) {
        if (pos < 0 || pos >= (int)arr.size()) return;
        arr.erase(arr.begin() + pos);
    }
};
class MinHeap:
    def __init__(self):
        self.arr = []

    # Insert element at the end - O(1)
    def insertKey(self, val):
        self.arr.append(val)

    # Scan entire array to find and remove minimum - O(n)
    def extractMin(self):
        if not self.arr:
            return -1

        min_idx = 0
        for i in range(1, len(self.arr)):
            if self.arr[i] < self.arr[min_idx]:
                min_idx = i

        min_val = self.arr[min_idx]
        self.arr.pop(min_idx)
        return min_val

    # Remove element at given position - O(n)
    def deleteKey(self, pos):
        if pos < 0 or pos >= len(self.arr):
            return
        self.arr.pop(pos)
import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> arr = new ArrayList<>();

    // Insert element at the end - O(1)
    void insertKey(int val) {
        arr.add(val);
    }

    // Scan entire array to find and remove minimum - O(n)
    int extractMin() {
        if (arr.isEmpty()) return -1;

        int minIdx = 0;
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) < arr.get(minIdx)) {
                minIdx = i;
            }
        }

        int minVal = arr.get(minIdx);
        arr.remove(minIdx);
        return minVal;
    }

    // Remove element at given position - O(n)
    void deleteKey(int pos) {
        if (pos < 0 || pos >= arr.size()) return;
        arr.remove(pos);
    }
}

Complexity Analysis

Time Complexity:

  • insertKey: O(1) — simply append to the end of the array
  • extractMin: O(n) — must scan every element to find the minimum, then shift elements after removal
  • deleteKey: O(n) — removing an element at a given position requires shifting all subsequent elements

For Q queries, the worst case is O(Q × n) when most queries are extractMin on a large array.

Space Complexity: O(n)

We store all n currently-inserted elements in a dynamic array. No additional data structures are used.

Why This Approach Is Not Efficient

The brute force approach stores elements in an unsorted array. While insertion is a fast O(1) append, both extractMin and deleteKey require O(n) operations:

  • extractMin must scan every element to locate the minimum — with n elements in the heap, that is n comparisons every single time
  • deleteKey requires shifting elements after removal, costing up to O(n)

With up to Q = 10^4 queries and a heap that can grow to 10^4 elements, repeated extractMin calls on a large array yield O(Q × n) ≈ 10^8 operations. This is right at the edge of typical time limits and will likely cause Time Limit Exceeded on strict judges.

The fundamental problem is that an unsorted array retains no structural information about element ordering. Every time we need the minimum, we start from scratch with a full scan.

What we need: A data structure that maintains just enough ordering so the minimum is always instantly accessible at the root, while still supporting efficient insertions and deletions. A binary min-heap achieves exactly this — it is a complete binary tree where every parent is ≤ its children, guaranteeing O(log n) for all three operations instead of O(n).

Optimal Approach - Binary Min-Heap with Heapify

Intuition

What if we could keep the elements partially ordered — not fully sorted, but just ordered enough so the minimum is always instantly accessible?

A binary min-heap achieves exactly this. Picture a pyramid of numbers where every parent is smaller than or equal to its children. The smallest number naturally sits at the very top (the root). The heap is stored as an array where the parent-child relationships follow a simple formula:

  • Parent of index i → index ⌊(i-1)/2⌋
  • Left child of index i → index 2i + 1
  • Right child of index i → index 2i + 2

Insert (Heapify-Up): Place the new element at the end of the array (the next available leaf position). If it is smaller than its parent, swap them. Keep swapping upward until the element finds a parent that is smaller or it reaches the root. This "bubbling up" traverses at most one root-to-leaf path.

ExtractMin (Heapify-Down): The minimum is always at the root (index 0). Swap the root with the last element, remove the last element, then fix the root by comparing it with its children and swapping with the smaller child. Repeat downward until the element finds children that are both larger (or it reaches a leaf). This "sinking down" also traverses at most one path.

DeleteKey: Decrease the key at the target position to negative infinity (the smallest possible value), which causes it to bubble up to the root via heapify-up. Then call extractMin to remove it.

Since a complete binary tree with n nodes has height ⌊log₂(n)⌋, both heapify-up and heapify-down cost at most O(log n) — dramatically faster than the O(n) scanning in the brute force.

Min-heap shown as a tree with root 2, children 4 and 15, and grandchildren 10 and 7, mapped to array [2, 4, 15, 10, 7] with index formulas
Min-heap shown as a tree with root 2, children 4 and 15, and grandchildren 10 and 7, mapped to array [2, 4, 15, 10, 7] with index formulas

Step-by-Step Explanation

Let's trace through Example 1 with queries: insertKey(4), insertKey(2), extractMin(), insertKey(6), deleteKey(0), extractMin(), extractMin()

Step 1: insertKey(4)

  • Heap is empty. Place 4 at index 0 (root).
  • No parent exists, so heapify-up terminates immediately.
  • Heap: [4]

Step 2: insertKey(2) — Place at end

  • Place 2 at index 1 (left child of root).
  • Compare 2 with parent at index 0: value 4. Since 2 < 4, heap property is violated.
  • Heap before fix: [4, 2]

Step 3: Heapify-Up — Swap 2 and 4

  • Swap element at index 1 (value 2) with parent at index 0 (value 4).
  • Now root = 2 (the minimum), child = 4. Heap property restored.
  • Heap: [2, 4]

Step 4: extractMin() — Swap root with last

  • Minimum is at root: value 2.
  • Swap root (index 0, value 2) with last element (index 1, value 4).
  • Heap after swap: [4, 2]

Step 5: Remove last and heapify-down

  • Remove last element (now value 2 after swap). Heap: [4].
  • Heapify-down from root: only one element, no children to compare. Done.
  • Return 2. Output so far: [2]

Step 6: insertKey(6)

  • Place 6 at index 1 (left child of 4).
  • Compare 6 with parent 4: since 6 > 4, heap property is already satisfied. No swap needed.
  • Heap: [4, 6]

Step 7: deleteKey(0)

  • Decrease key at position 0 to −∞ (negative infinity): heap becomes [−∞, 6].
  • Heapify-up: −∞ is already at root (index 0), nothing to do.
  • Call extractMin(): swap −∞ (root) with last element (6), remove −∞.
  • Heapify-down: only element 6 remains, no children. Heap: [6]

Step 8: extractMin()

  • Root = 6, the only element. Remove it. Return 6.
  • Heap: []. Output: [2, 6]

Step 9: extractMin() — Empty heap

  • Heap is empty. No elements to extract. Return -1.
  • Final output: [2, 6, -1]

Min-Heap Operations — Insert, ExtractMin, and DeleteKey — Watch how the min-heap maintains its property through heapify-up (bubbling up on insert) and heapify-down (sinking down on extract), keeping all operations at O(log n).

Algorithm

insertKey(x):

  1. Append x to the end of the heap array
  2. Heapify-up: while the new element is smaller than its parent, swap them and move up

extractMin():

  1. If the heap is empty, return -1
  2. Store the root value (the minimum)
  3. Replace the root with the last element in the array
  4. Remove the last element (reduce size)
  5. Heapify-down from root: compare with both children, swap with the smaller child if it is smaller than the current element, repeat downward
  6. Return the stored minimum

deleteKey(pos):

  1. If pos is out of bounds, return
  2. Set heap[pos] to negative infinity (INT_MIN)
  3. Heapify-up from pos to bubble −∞ to the root
  4. Call extractMin() to remove the −∞ value from the root

Code

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

class MinHeap {
    vector<int> harr;

    // Bubble element up to restore min-heap property
    void heapifyUp(int idx) {
        while (idx > 0) {
            int parent = (idx - 1) / 2;
            if (harr[parent] > harr[idx]) {
                swap(harr[parent], harr[idx]);
                idx = parent;
            } else {
                break;
            }
        }
    }

    // Push element down to restore min-heap property
    void heapifyDown(int idx) {
        int n = harr.size();
        while (true) {
            int smallest = idx;
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;

            if (left < n && harr[left] < harr[smallest])
                smallest = left;
            if (right < n && harr[right] < harr[smallest])
                smallest = right;

            if (smallest == idx) break;

            swap(harr[idx], harr[smallest]);
            idx = smallest;
        }
    }

public:
    // Insert and bubble up - O(log n)
    void insertKey(int val) {
        harr.push_back(val);
        heapifyUp(harr.size() - 1);
    }

    // Swap root with last, remove, heapify down - O(log n)
    int extractMin() {
        if (harr.empty()) return -1;

        int root = harr[0];
        harr[0] = harr.back();
        harr.pop_back();

        if (!harr.empty())
            heapifyDown(0);

        return root;
    }

    // Decrease key to INT_MIN, bubble up, extract - O(log n)
    void deleteKey(int pos) {
        if (pos < 0 || pos >= (int)harr.size()) return;
        harr[pos] = INT_MIN;
        heapifyUp(pos);
        extractMin();
    }
};
class MinHeap:
    def __init__(self):
        self.harr = []

    def _heapify_up(self, idx):
        """Bubble element up to restore min-heap property."""
        while idx > 0:
            parent = (idx - 1) // 2
            if self.harr[parent] > self.harr[idx]:
                self.harr[parent], self.harr[idx] = (
                    self.harr[idx], self.harr[parent]
                )
                idx = parent
            else:
                break

    def _heapify_down(self, idx):
        """Push element down to restore min-heap property."""
        n = len(self.harr)
        while True:
            smallest = idx
            left = 2 * idx + 1
            right = 2 * idx + 2

            if left < n and self.harr[left] < self.harr[smallest]:
                smallest = left
            if right < n and self.harr[right] < self.harr[smallest]:
                smallest = right

            if smallest == idx:
                break

            self.harr[idx], self.harr[smallest] = (
                self.harr[smallest], self.harr[idx]
            )
            idx = smallest

    def insertKey(self, val):
        """Insert and bubble up - O(log n)."""
        self.harr.append(val)
        self._heapify_up(len(self.harr) - 1)

    def extractMin(self):
        """Swap root with last, remove, heapify down - O(log n)."""
        if not self.harr:
            return -1

        root = self.harr[0]
        self.harr[0] = self.harr[-1]
        self.harr.pop()

        if self.harr:
            self._heapify_down(0)

        return root

    def deleteKey(self, pos):
        """Decrease key to -inf, bubble up, extract - O(log n)."""
        if pos < 0 or pos >= len(self.harr):
            return
        self.harr[pos] = float('-inf')
        self._heapify_up(pos)
        self.extractMin()
import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> harr = new ArrayList<>();

    // Bubble element up to restore min-heap property
    private void heapifyUp(int idx) {
        while (idx > 0) {
            int parent = (idx - 1) / 2;
            if (harr.get(parent) > harr.get(idx)) {
                int temp = harr.get(idx);
                harr.set(idx, harr.get(parent));
                harr.set(parent, temp);
                idx = parent;
            } else {
                break;
            }
        }
    }

    // Push element down to restore min-heap property
    private void heapifyDown(int idx) {
        int n = harr.size();
        while (true) {
            int smallest = idx;
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;

            if (left < n && harr.get(left) < harr.get(smallest))
                smallest = left;
            if (right < n && harr.get(right) < harr.get(smallest))
                smallest = right;

            if (smallest == idx) break;

            int temp = harr.get(idx);
            harr.set(idx, harr.get(smallest));
            harr.set(smallest, temp);
            idx = smallest;
        }
    }

    // Insert and bubble up - O(log n)
    void insertKey(int val) {
        harr.add(val);
        heapifyUp(harr.size() - 1);
    }

    // Swap root with last, remove, heapify down - O(log n)
    int extractMin() {
        if (harr.isEmpty()) return -1;

        int root = harr.get(0);
        harr.set(0, harr.get(harr.size() - 1));
        harr.remove(harr.size() - 1);

        if (!harr.isEmpty())
            heapifyDown(0);

        return root;
    }

    // Decrease key to MIN_VALUE, bubble up, extract - O(log n)
    void deleteKey(int pos) {
        if (pos < 0 || pos >= harr.size()) return;
        harr.set(pos, Integer.MIN_VALUE);
        heapifyUp(pos);
        extractMin();
    }
}

Complexity Analysis

Time Complexity:

  • insertKey: O(log n) — the new element may bubble up at most from the last level to the root. A complete binary tree with n nodes has height ⌊log₂(n)⌋, so heapify-up performs at most log n swaps.
  • extractMin: O(log n) — after swapping the root with the last element, heapify-down sinks the new root at most from the top to the bottom level, again at most log n comparisons and swaps.
  • deleteKey: O(log n) — decreasing the key to −∞ causes at most log n swaps upward (heapify-up), followed by one extractMin call which is also O(log n). Total: O(log n).

For Q queries, the total time is O(Q × log n), which for Q = 10^4 and n = 10^4 gives approximately 10^4 × 14 ≈ 1.4 × 10^5 operations — extremely efficient.

Space Complexity: O(n)

We store all n elements in a single array. The heap uses no additional data structures beyond this array, making it memory-efficient. The array representation avoids the overhead of pointers that a tree-based implementation would require.