Heaps

A complete binary tree where each parent is ≤ (min-heap) or ≥ (max-heap) its children.

Intermediate

A heap is stored in an array: the children of index $i$ are at $2i+1$ and $2i+2$ .

import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappop(h)      # 1

Heaps implement priority queues — task schedulers, Dijkstra's algorithm and heap sort.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)