Heap Introduction
Imagine a priority queue at an airport: first-class passengers board before economy, regardless of arrival order. A heap is a specialized tree-based data structure that satisfies the heap property. It is used to implement priority queues efficiently.
A heap is a complete binary tree where each node's value is either ≥ or ≤ its children.
Types:
- Max-Heap – parent node value ≥ children. The root is the largest element.
- Min-Heap – parent node value ≤ children. The root is the smallest element.
Heaps are commonly implemented using arrays for compact storage and efficient indexing. For a node at index i:
- Left child index: 2*i + 1
- Right child index: 2*i + 2
- Parent index: (i-1)/2
Heaps are used in priority queues, heap sort, and graph algorithms (Dijkstra, Prim).
Two Minute Drill
- Heap is a complete binary tree with heap property.
- Max-heap: parent ≥ children; Min-heap: parent ≤ children.
- Implemented efficiently with arrays using index formulas.
- Provides O(log n) insertion and removal, O(1) peek.
Need more clarification?
Drop us an email at career@quipoinfotech.com