binary heap
A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
In more detail
Because the tree is complete, the children of index i sit at 2i + 1 and 2i + 2, with no pointers needed. Insert and remove-root each cost O(log n), and reading the root costs O(1). Heap sort builds a heap and then removes the root n times, O(n log n) with no extra memory.
Related terms
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- heap property — The rule that every parent in a heap is ordered before its children: no larger than them in a min-heap.
- sift-up and sift-down — The two heap repair operations: sift-up moves a new item up past larger parents, and sift-down moves a displaced root down past smaller children.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
- priority queue — A collection where each item has a priority and the item removed next is always the one with the highest priority, not the oldest.
- complete binary tree — A binary tree in which every level is full except possibly the last, which is filled from the left with no gaps.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers