16/03/2025, 15:52 Heaps - Data Structures
Heaps
Definition
A Heap is a specialized tree-based data structure that satisfies the heap property. It is
commonly used in priority queues and efficient sorting algorithms.
Types of Heaps
Min-Heap: The value of the parent node is less than or equal to its children.
Max-Heap: The value of the parent node is greater than its children.
Properties of a Heap
Typically a Complete Binary Tree: All levels of the tree are filled except possibly
the last, which is filled from left to right.
Root Node:
In a Min-Heap, the smallest value is always at the root.
In a Max-Heap, the largest value is at the root.
Common Uses of Heaps
Priority Queues
Heap Sort
Dijkstra’s Algorithm (for finding the shortest path in a graph)
Time Complexity
Operation Complexity
Insert O(log n)
Delete (root) O(log n)
Peek (root) O(1)
[Link] 1/6
16/03/2025, 15:52 Heaps - Data Structures
Heap Implementation in an Array
A heap can be implemented using an array where:
Parent node: (i - 1) / 2
Left child: 2 * i + 1
Right child: 2 * i + 2
i is the index of an element in the array.
Heap Operations
Insert Operation
Add the new element at the end of the array.
Bubble it up (swap with parent) until the heap property is restored.
Delete Operation (Removing Root)
Replace the root with the last element.
Remove the last element.
Heapify down from the root to maintain the heap property.
The last element is removed to maintain the complete binary tree structure.
Using heapq in Python
Python provides the heapq module for heap operations, which only supports Min-Heaps by
default.
Basic Heap Operations
import heapq
# Create a heap
data = [1, 2, 3, 4]
[Link](data) # Converts list into a valid heap
# Insert an element into the heap
[Link](data, 10)
# Remove and return the smallest element (root)
[Link](data) # Returns 1
# Current heap: [2, 3, 4, 10]
[Link] 2/6
16/03/2025, 15:52 Heaps - Data Structures
Heap Implementation in an Array
A heap can be implemented using an array where:
Parent node: (i - 1) / 2
Left child: 2 * i + 1
Right child: 2 * i + 2
i is the index of an element in the array.
Heap Operations
Insert Operation
Add the new element at the end of the array.
Bubble it up (swap with parent) until the heap property is restored.
Delete Operation (Removing Root)
Replace the root with the last element.
Remove the last element.
Heapify down from the root to maintain the heap property.
The last element is removed to maintain the complete binary tree structure.
Using heapq in Python
Python provides the heapq module for heap operations, which only supports Min-Heaps by
default.
Basic Heap Operations
import heapq
# Create a heap
data = [1, 2, 3, 4]
[Link](data) # Converts list into a valid heap
# Insert an element into the heap
[Link](data, 10)
# Remove and return the smallest element (root)
[Link](data) # Returns 1
# Current heap: [2, 3, 4, 10]
[Link] 3/6
16/03/2025, 15:52 Heaps - Data Structures
Max-Heap in Python
Since heapq only provides a Min-Heap, we can simulate a Max-Heap by pushing negative
values.
import heapq
max_heap = []
[Link](max_heap, -10) # Insert -10 (simulates max-heap)
For a Max-Heap, multiply values by -1 before inserting.
Using Tuples in Heaps
Tuples can be used in priority queues where the first element of the tuple determines the
order.
Example: Using Tuples in heapq
import heapq
tasks = [(3, "Task1"), (5, "Task2")]
[Link](tasks) # Convert list to heap
# Insert a new task
[Link](tasks, (20, "Task3"))
The first element of the tuple is used for ordering.
If the first elements are equal, the next elements are compared.
Queues
Definition
A Queue is a FIFO (First In, First Out) data structure, where elements are added to the
rear and removed from the front.
Types of Queues
Priority Queue - Elements are dequeued based on priority (implemented using a
Heap).
[Link] 4/6
16/03/2025, 15:52 Heaps - Data Structures
Deque (Double-Ended Queue) - Elements can be added and removed from both
ends.
Applications of Queues
Job Scheduling
Caching
Sliding Window Problems
Breadth-First Search (BFS) Traversal
Queue Operations
Operation Description
Enqueue Add an element to the rear
Dequeue Remove an element from the front
Peek View the first element
Performance Comparison
Deque (Double-Ended Queue): Adding & removing elements is O(1).
List (Python built-in list): pop(0) is O(n) (not efficient for large-scale queue
operations).
Using deque from collections in Python
Python provides the deque class for efficient queue operations.
from collections import deque
# Create a deque
d = deque()
# Add elements at the end
[Link](10)
[Link](20)
# Add element at the front
[Link](5)
# Remove and return element from the front
[Link] 5/6
16/03/2025, 15:52 Heaps - Data Structures
[Link]() # Removes 5 (left pop)
# Remove and return element from the back
[Link]() # Removes 20 (right pop)
[Link] 6/6
