SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Min-Heap Extract Visualizer

The minimum is always the root. Remove it, move the last value to the root, and let it sink down to the smaller child until the heap is valid.

Start the Min-Heap Extract simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(log n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. This is a min-heap of your values. Pop the minimum until it is empty.
  2. The minimum is the root, 20.
  3. Remove 20. Move the last value, 65, to the root.
  4. 30 is the smaller child, so swap. 65 sinks down.
  5. 35 is the smaller child, so swap. 65 sinks down.
  6. 50 is the smaller child, so swap. 65 sinks down.
  7. 65 is not bigger than its children. The heap is valid again.
  8. The minimum is the root, 30.
  9. Remove 30. Move the last value, 65, to the root.
  10. 35 is the smaller child, so swap. 65 sinks down.
  11. 40 is the smaller child, so swap. 65 sinks down.
  12. 65 is not bigger than its children. The heap is valid again.
  13. The minimum is the root, 35.
  14. Remove 35. Move the last value, 80, to the root.
  15. 40 is the smaller child, so swap. 80 sinks down.
  16. 50 is the smaller child, so swap. 80 sinks down.
  17. 80 is not bigger than its children. The heap is valid again.
  18. The minimum is the root, 40.
  19. Remove 40. Move the last value, 70, to the root.
  20. 50 is the smaller child, so swap. 70 sinks down.
  21. … 14 more steps …
  22. Remove 70. Move the last value, 80, to the root.
  23. 80 is not bigger than its children. The heap is valid again.
  24. The minimum is the root, 80.
  25. Done. The values came out sorted: 20, 30, 35, 40, 50, 60, 65, 70, 80.

Try it with your own input →

Min-heap extract in Java, Python, C++, C and JavaScript

int pop() {
  int min = heap.get(0);
  int last = heap.remove(heap.size() - 1);
  if (!heap.isEmpty()) {
    heap.set(0, last);
    int i = 0;
    while (true) {
      int l = 2 * i + 1, r = 2 * i + 2, s = i;
      if (l < heap.size() && heap.get(l) < heap.get(s)) s = l;
      if (r < heap.size() && heap.get(r) < heap.get(s)) s = r;
      if (s == i) break;
      swap(heap, i, s);
      i = s;
    }
  }
  return min;
}
def pop(heap):
    min_v = heap[0]
    last = heap.pop()
    if heap:
        heap[0] = last
        i = 0
        while True:
            l, r, s = 2 * i + 1, 2 * i + 2, i
            if l < len(heap) and heap[l] < heap[s]:
                s = l
            if r < len(heap) and heap[r] < heap[s]:
                s = r
            if s == i:
                break
            heap[i], heap[s] = heap[s], heap[i]
            i = s
    return min_v
int pop(vector<int>& heap) {
  int mn = heap[0];
  int last = heap.back(); heap.pop_back();
  if (!heap.empty()) {
    heap[0] = last;
    int i = 0, n = heap.size();
    while (true) {
      int l = 2 * i + 1, r = 2 * i + 2, s = i;
      if (l < n && heap[l] < heap[s]) s = l;
      if (r < n && heap[r] < heap[s]) s = r;
      if (s == i) break;
      swap(heap[i], heap[s]);
      i = s;
    }
  }
  return mn;
}
int pop(int heap[], int* size) {
  int min = heap[0];
  int last = heap[--(*size)];
  if (*size > 0) {
    heap[0] = last;
    int i = 0, n = *size;
    while (1) {
      int l = 2 * i + 1, r = 2 * i + 2, s = i;
      if (l < n && heap[l] < heap[s]) s = l;
      if (r < n && heap[r] < heap[s]) s = r;
      if (s == i) break;
      int t = heap[i]; heap[i] = heap[s]; heap[s] = t;
      i = s;
    }
  }
  return min;
}
function pop(heap) {
  const min = heap[0];
  const last = heap.pop();
  if (heap.length > 0) {
    heap[0] = last;
    let i = 0;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let s = i;
      if (l < heap.length && heap[l] < heap[s]) s = l;
      if (r < heap.length && heap[r] < heap[s]) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  }
  return min;
}

In an interview

Popping every value gives them in sorted order. That is heap sort, and the reason a heap gives O(n log n) "sorted stream" answers.

More trees