What is a heap data structure? How do you implement it in Python?

Python Data Structures - Interview Questions and Answers

Heap Data Structure in Python

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

In a min-heap, the parent node is always smaller than its children.
In a max-heap, the parent node is always greater than its children.

Heaps are commonly used for priority queues, sorting algorithms (Heap Sort), and graph algorithms (Dijkstra’s Algorithm, Prim’s Algorithm, etc.).

1. Types of Heaps

Min-Heap: The smallest element is always at the root.
Max-Heap: The largest element is always at the root.

2. Implementing a Heap in Python

Python provides the heapq module, which implements a min-heap by default.

Min-Heap Implementation (Using `heapq`)

import heapq

# Create an empty heap
heap = []

# Insert elements into the heap
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)
heapq.heappush(heap, 7)

print(heap)  # Output: [5, 7, 15, 10] (Heap structure, not sorted)

# Remove and return the smallest element
print(heapq.heappop(heap))  # Output: 5
print(heap)  # Output: [7, 10, 15]

* heappush() and heappop() run in O(log n) time.
* Always dequeues the smallest element first (Min-Heap).

3. Implementing a Max-Heap

Since heapq only supports min-heaps, we can simulate a max-heap by inserting negative values.

import heapq

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -15)
heapq.heappush(max_heap, -7)

print(-heapq.heappop(max_heap))  # Output: 15 (Largest element first)

* By pushing negative values, the smallest negative becomes the largest positive.

4. Building a Heap from a List

We can convert an existing list into a heap using heapq.heapify(), which runs in O(n) time.

import heapq

arr = [10, 5, 15, 7]
heapq.heapify(arr)

print(arr)  # Output: [5, 7, 15, 10] (Min-Heap order)
print(heapq.heappop(arr))  # Output: 5

* heapify() transforms a list into a valid heap in O(n) time.

5. Using a Heap as a Priority Queue

Example: Using Tuples for Priority

import heapq

pq = []
heapq.heappush(pq, (2, "Task B"))  # Priority 2
heapq.heappush(pq, (1, "Task A"))  # Priority 1 (Highest)
heapq.heappush(pq, (3, "Task C"))  # Priority 3

print(heapq.heappop(pq))  # Output: (1, 'Task A')

* The lowest priority number is dequeued first.

6. Implementing a Heap Manually

If you want to implement a heap from scratch, you can use a binary tree with an array.

Manual Min-Heap Implementation

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left_child(self, i):
        return 2 * i + 1

    def right_child(self, i):
        return 2 * i + 2

    def insert(self, value):
        self.heap.append(value)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, index):
        parent = self.parent(index)
        if index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._heapify_up(parent)

    def pop(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return root

    def _heapify_down(self, index):
        smallest = index
        left = self.left_child(index)
        right = self.right_child(index)

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)

# Example Usage
heap = MinHeap()
heap.insert(10)
heap.insert(5)
heap.insert(15)
heap.insert(7)

print(heap.pop())  # Output: 5
print(heap.pop())  # Output: 7

* Implements min-heap from scratch.
* Uses array representation of a binary tree.

7. When to Use Heaps?

Use Case	Why Heaps?
Priority Queues	Efficient O(log n) insertion/removal.
Heap Sort	Sorting in O(n log n) time.
Graph Algorithms	Dijkstra’s & Prim’s Algorithm use heaps.
Finding k Largest/Smallest Elements	`heapq.nlargest()` and `heapq.nsmallest()` are efficient.