AlgoViz
HomeHeap / Priority Queue

Heaps (Theory Video)

Easy

A complete tree stored as an array

Problem

Learn the binary heap: a complete tree kept as an array where each parent is <= (min-heap) or >= (max-heap) its children, giving O(log n) push/pop.

In simple words

A tournament bracket where the smallest (or largest) always bubbles to the top.

The idea

A binary heap keeps every parent smaller (or larger) than its children, which puts the extreme value at the root while leaving the rest only loosely ordered. Because the tree is complete it fits in an array with no pointers: the children of index i sit at 2i+1 and 2i+2.

The trick

  • Children of i are 2i+1 and 2i+2; the parent is (i-1)/2.
  • Insert and extract are O(log n); peeking at the root is O(1).
  • Building a heap from an array is O(n), not O(n log n) — heapify bottom-up.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
3
8
1
0
1
2
3

Step 1 of 2. Here's the example — push 5,3,8,1 Values: 5, 3, 8, 1.

1/2
Optimal
timeO(log n)spaceO(n)
1push: add at end, swim up while smaller than parent2pop: swap root with last, remove, sink down

Input

array
[5, 3, 8, 1]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
push 5,3,8,1
Output:
min at root = 1

Finished the walkthrough? Add it to your streak.