AlgoScope

Priority Queue

Always hands back the highest-priority item, usually by keeping a binary heap underneath.

Data structures, data structure, intermediate
The value reached the root and is the smallest in the heap.94811027current
The value reached the root and is the smallest in the heap.94811027current

Binary Heap: Insert climbs to the root

Step, step 5 of 6

It reached the root, so it is the smallest value in the heap.

How binary heap works

Cost

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

Depends on representation. Bounds shown are for a binary heap.

Leads to

Topics that need this one first.

Taught by the same lesson

Binary Heap covers these too, in the same run.