Heap (data structure)
A heap is a specialized tree-based data structure that satisfies the heap property: in a max-heap, each parent node is greater than or equal to its children; in a min-heap, each parent is less than or equal to its children. Heaps are typically implemented as complete binary trees stored in arrays, enabling O(1) access to the minimum or maximum element. They are the underlying structure of priority queues and are used in heap sort and Dijkstra's shortest path algorithm.
Heap Operation Complexities
| Operation | Min-Heap | Max-Heap | Notes |
|---|---|---|---|
| Find Min/Max | O(1) | O(1) | Always at root |
| Insert | O(log n) | O(log n) | Sift up after insert |
| Delete Min/Max | O(log n) | O(log n) | Sift down after removal |
| Heapify (build) | O(n) | O(n) | Bottom-up construction |
| Merge Two Heaps | O(n) | O(n) | Fibonacci heap: O(1) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Priority Queue
A priority queue is an abstract data type similar to a regular queue or stack but where each element has an associated priority; elements are served in order of their priority rather than their insertion order. It supports at minimum the operations of inserting an element and extracting the element with the highest (or lowest) priority. Priority queues are commonly implemented using binary heaps, and they are essential in algorithms such as Dijkstra's shortest path, A* search, Prim's minimum spanning tree, and task scheduling in operating systems.
Binary Tree
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is one of the most fundamental structures in computer science, forming the basis for more specialized trees like binary search trees and heaps. Binary trees are widely used in expression parsing, Huffman coding, and database indexing.
Binary Search Tree
A binary search tree (BST) is a binary tree in which every node satisfies the property that all keys in its left subtree are less than the node's key and all keys in its right subtree are greater. This ordering property makes search, insertion, and deletion operations efficient, averaging O(log n) for balanced trees. BSTs are foundational in database indexing, symbol tables, and dynamic set operations.
The term "heap" in this context was coined by J. W. J. Williams in 1964 when he introduced heap sort. The word "heap" reflects the informal notion of a pile where the largest (or smallest) item is always on top and accessible.