Min-Heap

Insert and extract-min on a binary min-heap. New values sift up until their parent is smaller; extracting the root moves the last leaf to the top and sifts it back down. Only local parent/child comparisons are ever made, yet the smallest value is always at the root — which is what makes priority queues fast.

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(n)