Heap Data Structure
A Heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property. It is the most efficient way to implement a Priority Queue.
1. The Heap Property
- Max-Heap: For any given node
I, the value ofIis greater than or equal to the values of its children. The largest element is at the root. - Min-Heap: For any given node
I, the value ofIis less than or equal to the values of its children. The smallest element is at the root.
2. Array Representation
Heaps are usually implemented using arrays because they are complete binary trees (filled from left to right). This allows for efficient access without pointers.
For a node at index i:
- Parent:
(i - 1) // 2 - Left Child:
(2 * i) + 1 - Right Child:
(2 * i) + 2
3. Common Operations
Insertion (Heapify Up)
- Add the element to the bottom level of the heap (end of array).
- Compare the added element with its parent; if they are in the wrong order, swap them.
- Repeat step 2 until the heap property is satisfied.
Extraction (Heapify Down)
Usually, we extract the root (Max or Min).
- Replace the root with the last element in the heap.
- Remove the last element.
- Compare the new root with its children; if they are in the wrong order, swap with the smaller (Min-Heap) or larger (Max-Heap) child.
- Repeat step 3 until the heap property is satisfied.
4. Time Complexity
- Get Min/Max: $O(1)$
- Insert: $O(\log n)$
- Delete (Extract): $O(\log n)$
- Heap Sort: $O(n \log n)$
5. Usage: Priority Queues
Heaps are the standard implementation for Priority Queues, where elements are dequeued based on priority rather than insertion order.
import heapq
# Python's heapq is a Min-Heap by default
pq = []
heapq.heappush(pq, 10)
heapq.heappush(pq, 1)
heapq.heappush(pq, 5)
print(heapq.heappop(pq)) # 1 (Smallest)
print(heapq.heappop(pq)) # 5