Heap: Min-Heap and Max-Heap Operations – A Complete Guide
Author: Admin | Website: codetocareer.blogspot.com
Introduction
Heaps are fundamental data structures forming the backbone of efficient algorithms in many real-world applications such as priority queues, graph algorithms, and sorting[1][2]. This comprehensive article delves into heaps—focusing on min-heap and max-heap, exploring their properties, real-world uses, standard operations, and providing optimized, SEO-friendly content to help you master or review the concept for interviews or advanced competitive programming. Every explanation and code is original and referenced from trusted sources while being worded uniquely for best SEO impact.
Heap Basics
A heap is a specialized complete binary tree structure that follows the heap property — for min-heaps, every parent node is less than or equal to its children; for max-heaps, every parent is greater than or equal to its children[1][4][5][6]. Removing or adding elements maintains this underlying order, enabling fast access to the minimum or maximum element at the root in constant time.
Types of Heaps
- Min-Heap: The smallest element is at the root. All descendants of a node are greater or equal to the node itself.
- Max-Heap: The largest element is at the root. All descendants are less or equal to their parent node.
Heap Representation
Though conceptually a binary tree, heaps are almost always implemented using arrays because the indexes make parent/child access direct:[10][15][11]
- Root at index
0 - Left child at
2i + 1 - Right child at
2i + 2 - Parent at
(i - 1) // 2
Index: 0 1 2 3 4 5 6
Array: [18, 6, 13, 5, 4, 7, 12]
Heap Properties
- Always a complete binary tree: All levels are filled except maybe the last, which is left-filled only.
- Provides O(1) access to the min (min-heap) or max (max-heap) element, and O(log n) insertion/deletion.
- Heap is not a sorted structure; it's a partial order.
Core Heap Operations
Heaps support several fundamental operations efficiently[4][5][9][10][13][15]:
Insertion
- Add the new node at the next available position (end of the array).
- Reheapify "up" (bubble up or sift-up): Compare the new node to its parent and swap if heap property is violated; repeat until heap property is restored or root is reached.
- O(log n) time complexity.
Deletion
- Delete/Extract-min (or max): Remove the root node.
- Swap the last element into the root position.
- Reheapify "down" (bubble down or sift-down): Swap the new root with its smallest (min-heap) or largest (max-heap) child if the heap property is violated; continue until heap property is restored.
- O(log n) time complexity.
Peek & Heapify
- Peek: Return the root (min or max, depending on heap type) in O(1) time.
- Heapify: Turn any array/subtree into a heap. Widely used to build a heap from an unsorted array or after a major update. Runs in O(log n) when applied to a node; O(n) for a whole array.
Other Useful Operations
- Replace: Remove the root, insert a new key in its place, and heapify (O(log n))—useful for fixed-size heaps.
- Decrease-key/Increase-key: Decrease or increase a node’s key and reheapify up or down as appropriate.
- Merge/Meld: Combine two heaps (depends on heap variant; O(n) generally).
Heap Algorithms: Step-by-Step
Insertion Algorithm (Pseudocode for Min-Heap):
function insertMinHeap(array, key):
array.append(key)
i = length(array) - 1
while i > 0 and array[parent(i)] > array[i]:
swap(array[parent(i)], array[i])
i = parent(i)
Deletion/Extract-Min (Pseudocode for Min-Heap):
function extractMin(array):
if length == 0: return null
min = array[0]
array[0] = array[length - 1]
array.pop()
heapifyDown(array, 0)
return min
function heapifyDown(array, i):
smallest = i
left = 2*i + 1
right = 2*i + 2
if left < n and array[left] < array[smallest]: smallest = left
if right < n and array[right] < array[smallest]: smallest = right
if smallest != i:
swap(array[i], array[smallest])
heapifyDown(array, smallest)
Heapify (Converting Array to Heap):
function buildHeap(array):
for i from floor(n/2) downto 0:
heapifyDown(array, i)
Applications of Min-Heap and Max-Heap
- Priority queues (OS scheduling, simulation engines)
- Dijkstra's shortest path (min-heap)
- Heapsort (internal use of heap)
- Huffman coding (data compression)
- Median finding (using two heaps)
- K'th Largest/Smallest Element in Array
Implementing Heap in Code
Python Example: Min-Heap
class MinHeap:
def __init__(self):
self.heap = []
def insert(self, val):
self.heap.append(val)
i = len(self.heap) - 1
while i > 0 and self.heap[(i-1)//2] > self.heap[i]:
self.heap[(i-1)//2], self.heap[i] = self.heap[i], self.heap[(i-1)//2]
i = (i-1)//2
def extract_min(self):
if not self.heap: return None
root = self.heap[0]
last = self.heap.pop()
if self.heap:
self.heap[0] = last
self.heapify_down(0)
return root
def heapify_down(self, i):
n = len(self.heap)
while True:
left, right = 2*i+1, 2*i+2
smallest = i
if left < n and self.heap[left] < self.heap[smallest]: smallest = left
if right < n and self.heap[right] < self.heap[smallest]: smallest = right
if smallest == i: break
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
Python Example: Max-Heap
class MaxHeap:
def __init__(self):
self.heap = []
def insert(self, val):
self.heap.append(val)
i = len(self.heap) - 1
while i > 0 and self.heap[(i-1)//2] < self.heap[i]:
self.heap[(i-1)//2], self.heap[i] = self.heap[i], self.heap[(i-1)//2]
i = (i-1)//2
def extract_max(self):
if not self.heap: return None
root = self.heap[0]
last = self.heap.pop()
if self.heap:
self.heap[0] = last
self.heapify_down(0)
return root
def heapify_down(self, i):
n = len(self.heap)
while True:
left, right = 2*i+1, 2*i+2
largest = i
if left < n and self.heap[left] > self.heap[largest]: largest = left
if right < n and self.heap[right] > self.heap[largest]: largest = right
if largest == i: break
self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
i = largest
Best Practices & Optimization
- Use heapify (bottom up approach) to build a heap from an array in O(n) time, instead of inserting all elements one by one.
- Avoid using pointers for tree structure – use array representation for better cache locality and performance.
- Choose min-heap or max-heap based on which element you want fast access to (smallest or largest).
- For dynamic real-time priority updates, use the decrease-key/increase-key operations.
- Use
heapqin Python for built-in functionality and optimized implementations in real code.
Conclusion
Heaps are a core data structure with simple yet powerful properties, enabling a range of computationally hard problems to be solved efficiently. Mastering heaps—including min-heap and max-heap operations, and understanding their implementation details—will provide an edge in technical interviews as well as in solving real-world system design problems. Implement them from scratch to build your foundational understanding, and then leverage language libraries for real-world projects.
0 Comments