DataTerminology.comNEW
Also known as: Binary Heap
A specialized tree-based data structure that maintains the heap property to support efficient priority queue operations.
DESCRIPTION
A heap organizes elements so that the minimum or maximum is always at the root, enabling O(log n) insert and extract operations. Binary heaps are common, represented as arrays for cache efficiency. Heaps support heapsort and are used in graph algorithms like Dijkstra’s and Prim’s. Variants such as d-ary and Fibonacci heaps trade constant factors and theoretical bounds for practical performance.
ALTERNATIVE DEFINITIONS
Wikipedia
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property.
Concise emphasis on the heap property.
Princeton Algorithms
A priority queue is a data type in which each element has a priority. The basic implementation is the binary heap.
Connects heaps to priority queues and practical implementation.
RELATED TERMS
Priority Queue Min-Heap Max-Heap D-ary Heap Binary Search Tree Heapsort Graph Algorithms Dijkstra’s Algorithm Scheduling
COMPETING TERMS
Fibonacci Heap Balanced Binary Search Tree
KNOWLEDGE AREAS
Software Engineering Mathematics Data Modeling Data Storage & Operations
TARGET AUDIENCE
Software Developer Data Engineer Software Architect Full Stack Developer
EXTERNAL SOURCES
- Wikipedia - Heap (data structure)
- Princeton Algorithms - Priority queues and binary heaps
- CP-Algorithms - Heap operations and usage
TOP QUESTIONS
When should I use a heap?
Use heaps for priority queues, scheduling tasks, or selecting top-k elements efficiently.
Category: How-to
What is the heap property?
In a min-heap, every node is less than or equal to its children; in a max-heap, greater than or equal.
Category: Example
What are common heap pitfalls?
Forgetting to reheapify after updates breaks the property. Use sift-up and sift-down operations correctly.
Category: Mistakes
How does heapsort work?
Build a heap and repeatedly extract the root, restoring the heap each time to produce a sorted array.
Category: How-to
Are heaps cache-friendly?
Array-based binary heaps are cache-friendly compared to pointer-based trees, aiding performance.
Category: Requirements
What’s the complexity of heap operations?
Insert and extract are O(log n); find-min/max is O(1) in binary heaps.
Category: Requirements
How do heaps compare to balanced BSTs?
Heaps are better for priority access; BSTs support ordered iteration and search by key.
Category: Alternatives
When use Fibonacci heaps?
They offer better theoretical bounds for decrease-key, useful in some graph algorithms, but have higher constants.
Category: Opinion
What’s a practical example of heap usage?
Scheduling jobs by earliest deadline or merging k sorted lists with a min-heap.
Category: Example