Heaps are specialized tree-based data structures that satisfy the heap property. A min-heap ensures that the parent node is smaller than its children, while a max-heap ensures that the parent node is larger than its children. Heaps are used to efficiently implement priority queues.
In Python, the built-in heapq module provides a min-heap implementation. Python doesn't have a built-in max-heap, but you can simulate it by inserting negative values.
✅ Basic Heap Operations in Python
🔸 Insertion (heapq.heappush)
python
import heapq
# Create a min-heap (empty list)
heap = []
# Inserting elements
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap) # Output: [3, 5, 7]
🔍 Extract Min (heapq.heappop)
python
# Extract the smallest element (min-heap property)
min_element = heapq.heappop(heap)
print(min_element) # Output: 3
print(heap) # Output: [5, 7]
🔑 Peek at Min (Get the smallest element without removing it)
python
# Peek the smallest element (without removal)
min_element = heap[0]
print(min_element) # Output: 5
🔸 Max-Heap Simulation (Insert Negative Values)
python
# Simulating a max-heap using negative values
max_heap = []
# Inserting negative of values
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)
# Extract max (negative of min)
max_element = -heapq.heappop(max_heap)
print(max_element) # Output: 7
⚙️ Use Cases of Heaps
- Priority Queues: For tasks like scheduling jobs with priorities.
- Efficient Sorting: Heapsort algorithm (in-place).
- Graph Algorithms: Dijkstra’s shortest path algorithm, Prim’s algorithm for MST.
- Median Finding: Maintaining a dynamic set of numbers.
💡 Example: Priority Queue Simulation
python
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
def insert(self, priority, item):
# Insert item with priority (min-heap)
heapq.heappush(self.heap, (priority, item))
def extract_min(self):
return heapq.heappop(self.heap)[1] # Return the item
def peek_min(self):
return self.heap[0][1] # Peek at the item with the smallest priority
# Test PriorityQueue
pq = PriorityQueue()
pq.insert(2, "Task A")
pq.insert(1, "Task B")
pq.insert(3, "Task C")
print(pq.extract_min()) # Output: Task B
print(pq.peek_min()) # Output: Task A
📝 Summary
OperationDescriptionTime ComplexityInsertInsert an element with its priorityO(log n)Extract Min/MaxRemove and return the min or max elementO(log n)PeekReturn the min or max element without removalO(1)
Heaps are an essential part of any programmer's toolkit, especially for tasks involving prioritized processing. With Python's heapq module, it's easy to incorporate priority queues into your programs, allowing for efficient handling of tasks with varying priorities.