AlgoScope

Binary Heap

A complete tree where every parent outranks its children, stored in a plain array.

Data structures, data structure, intermediate
Sifting down from index 2, which holds 7. Both subtrees beneath it already satisfy the heap property.1489276current
Sifting down from index 2, which holds 7. Both subtrees beneath it already satisfy the heap property.1489276current

Binary Heap: Build a min heap

Step, step 2 of 12

Take 7, the parent at index 2. Everything below it is already a heap.

Cost

Insert
O(log n)
Extract top
O(log n)
Peek
O(1)
Build
O(n)
Space
O(n)

Before this

Variants

  • Min HeapSmallest element at the root.
  • Max HeapLargest element at the root.

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Heap covers these too, in the same run.