What is a Heap Data Structure and How to Use It in Python

A heap is a binary tree-based data structure that satisfies the heap property:

Min-Heap: Every parent node is less than or equal to its children.
Max-Heap: Every parent node is greater than or equal to its children.

**Heaps are not sorted, but they guarantee that the smallest (or largest) element is always at the top/root.

1. Visualizing a Heap (Min-Heap)

Given input: [5, 3, 8, 1, 2]

It turns into a binary tree like this:

And stored in array like: [1, 2, 8, 5, 3]
Each node at index i:
Left child = index 2i + 1
Right child = index 2i + 2

2. Real-World Uses of Heaps

1) Priority queues
2) Scheduling systems
3) Dijkstra’s shortest path
4) Top K elements
5) Heap sort

3. Python Support: heapq Module

Python’s built-in heapq module implements a Min-Heap by default. (To simulate a Max-Heap, just store negative numbers!)

4. Python Example: Min-Heap

[min_heap.py]

import heapq

# Create a heap from a list
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)
print("Min-Heap:", nums)  # The smallest item is at index 0

[output]
Min-Heap: [1, 2, 8, 5, 3]

Note: The heap is a binary heap stored as a list — it's not fully sorted, just structured to maintain the heap property.

5. Heap Operations

1) heapq.heappush(heap, item)

[Add an element to the heap.]

heapq.heappush(nums, 0)
print(nums)  # [0, 2, 1, 5, 3, 8]

2) heapq.heappop(heap)

[Remove and return the smallest element.]

smallest = heapq.heappop(nums)
print("Smallest:", smallest)  # 0
print("Heap after pop:", nums)

3) heapq.heappushpop(heap, item)

[Push a new item on the heap, then pop and return the smallest item.]

result = heapq.heappushpop(nums, 4)
print("Result:", result)  # returns the smallest

4) heapq.nsmallest(n, iterable)

[Return the n smallest elements without modifying the heap.]

heapq.nsmallest(3, nums)  # [1, 2, 3]

6. Problem: Find the Top K Largest (or Smallest) Elements

Given a list of numbers, find the k largest (or smallest) elements efficiently.

Using heapq.nlargest() and heapq.nsmallest()

Python makes this super easy:

import heapq

nums = [4, 1, 7, 3, 8, 5, 10, 2]

# Top 3 largest numbers
top_k_largest = heapq.nlargest(3, nums)

# Top 3 smallest numbers
top_k_smallest = heapq.nsmallest(3, nums)

print("Top 3 Largest:", top_k_largest)
print("Top 3 Smallest:", top_k_smallest)

[Output]
Top 3 Largest: [10, 8, 7]
Top 3 Smallest: [1, 2, 3]

These are super efficient under the hood:

nlargest(k, iterable) uses a Min-Heap of size k
nsmallest(k, iterable) uses a Max-Heap of size k (by negating values)

Manually Build a Top-K Heap (for practice)

Let’s say we want to find the Top 3 Largest manually using a Min-Heap of size k.

import heapq

def top_k_largest(nums, k):
	min_heap = nums[:k]
    heapq.heapify(min_heap)  # Convert first k elements into a min-heap

    for num in nums[k:]:
        if num > min_heap[0]:  # Only insert if it's larger than the smallest in heap
            heapq.heappushpop(min_heap, num)

    return sorted(min_heap, reverse=True)

nums = [4, 1, 7, 3, 8, 5, 10, 2]
top3 = top_k_largest(nums, 3)
print("Top 3 largest:", top3)

[Output]
Top 3 largest: [10, 8, 7]