SimuVedaAlgorithms Lab Open in the lab

Trees / Intermediate

Min-Heap Insert Visualizer

Add the new value at the end of the array, then let it bubble up while it is smaller than its parent.

Start the Min-Heap Insert 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(1)
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. Insert the values one by one into an empty min-heap.
  2. Add 50 at the end, index 0.
  3. Add 30 at the end, index 1.
  4. Compare 30 with its parent 50.
  5. 30 is smaller, so it swaps up.
  6. 30 reached the root.
  7. Add 70 at the end, index 2.
  8. Compare 70 with its parent 30.
  9. 30 ≤ 70, so the heap is valid. Stop.
  10. Add 20 at the end, index 3.
  11. Compare 20 with its parent 50.
  12. 20 is smaller, so it swaps up.
  13. Compare 20 with its parent 30.
  14. 20 is smaller, so it swaps up.
  15. 20 reached the root.
  16. Add 40 at the end, index 4.
  17. Compare 40 with its parent 30.
  18. 30 ≤ 40, so the heap is valid. Stop.
  19. Add 60 at the end, index 5.
  20. Compare 60 with its parent 70.
  21. … 11 more steps …
  22. Add 65 at the end, index 8.
  23. Compare 65 with its parent 35.
  24. 35 ≤ 65, so the heap is valid. Stop.
  25. Done. The smallest value, 20, is at the root.

Try it with your own input →

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

void push(int val) {
  heap.add(val);
  int i = heap.size() - 1;
  while (i > 0) {
    int p = (i - 1) / 2;
    if (heap.get(p) <= heap.get(i)) break;
    swap(heap, i, p);
    i = p;
  }
}
def push(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0:
        p = (i - 1) // 2
        if heap[p] <= heap[i]:
            break
        heap[i], heap[p] = heap[p], heap[i]
        i = p
void push(vector<int>& heap, int val) {
  heap.push_back(val);
  int i = heap.size() - 1;
  while (i > 0) {
    int p = (i - 1) / 2;
    if (heap[p] <= heap[i]) break;
    swap(heap[i], heap[p]);
    i = p;
  }
}
void push(int heap[], int* size, int val) {
  heap[(*size)++] = val;
  int i = *size - 1;
  while (i > 0) {
    int p = (i - 1) / 2;
    if (heap[p] <= heap[i]) break;
    int t = heap[i]; heap[i] = heap[p]; heap[p] = t;
    i = p;
  }
}
function push(heap, val) {
  heap.push(val);
  let i = heap.length - 1;
  while (i > 0) {
    const p = Math.floor((i - 1) / 2);
    if (heap[p] <= heap[i]) break;
    [heap[i], heap[p]] = [heap[p], heap[i]];
    i = p;
  }
}

In an interview

Java’s PriorityQueue is a min-heap. It is the tool for "top k", "k-th largest" and "merge k sorted lists".

More trees