Heap
A binary heap is an almost complete binary tree in which each parent satisfies an ordering property relative to its children, enabling efficient access to a minimum or maximum element.
Advanced Algorithms and Data Structures
A binary heap is a complete binary-tree-based priority queue in which each node has priority at least as high as every node in its subtree.
- How it is used
- Implements a priority queue for processing tasks or other elements by priority.
- How deep it goes
- Develops array invariants, index formulas, repair operations, bottom-up construction, and time–space costs.
- Examples
- Uses prioritized tasks, tree-to-array diagrams, heapification steps, the k-largest-elements problem, and shortest paths.
- What you can do after
- Build it from scratch with array indexing, heap-property repair, and bottom-up heapify; evaluate lookup and branching-factor trade-offs.
Read how Advanced Algorithms and Data Structures explains heap →
Grokking Data Structures
A binary heap is a heap represented as a binary, almost complete tree in which each node satisfies the heap ordering property relative to its children.
- How it is used
- Implements a priority queue that removes the highest-priority item rather than the earliest inserted item.
- How deep it goes
- Works through tree properties, array storage, insertion, removal, and bottom-up heap construction, without a formal height proof.
- Examples
- Uses a bug queue and the insertion of a high-priority broken-login report to illustrate bubble-up.
- What you can do after
- Build it from scratch with a Python list, including insert, top, and linear-time heapify.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
A binary heap is a tree-shaped priority-queue implementation that maintains an ordering relationship between parents and children.
- How it is used
- Uses a priority queue to select the next A* frontier state by lowest estimated total cost.
- How deep it goes
- Defines heap-backed priority queues and operation costs but defers the heap's internal implementation.
- Examples
- Demonstrates heap-backed ordering through Swift A* maze searches using node cost and Manhattan distance.
- What you can do after
- Apply it via SwiftPriorityQueue when implementing A* frontier selection.
Related concepts
- priority queueimplements · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
- min-heapincludes · A min-heap is a heap-ordered tree in which each parent has no greater priority than its children, so a minimum-priority element is at the root.
- max heapincludes · A max heap is a heap-ordered data structure in which each parent is no smaller than its children, making a maximum element available at the root.
- arrayuses · An array is an indexed, ordered collection of elements arranged in one or more dimensions, with elements accessed by position.
- binary treekind of · A binary tree is a tree data structure in which each node has at most two children.
- heapifyproduced by · Heapify is the process of rearranging an unordered collection to satisfy the invariant of a valid heap.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.