Time Complexity of Heap Operations Explained Simply

The main heap operations have these time complexities: insert and extract-min/max run in O(log n) time, where n is the number of elements. Building a heap from an unordered list takes O(n) time. Accessing the top element is O(1).

Syntax

Here are the common heap operations and their typical usage:

• insert(value): Add a new value to the heap.
• extract_min() or extract_max(): Remove and return the smallest or largest value.
• peek(): Return the top value without removing it.
• build_heap(array): Create a heap from an unordered array.

Each operation maintains the heap property, which keeps the smallest (min-heap) or largest (max-heap) element at the top.

python

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

    def insert(self, val):
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)

    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        last_val = self.heap.pop()
        if self.heap:
            self.heap[0] = last_val
            self._bubble_down(0)
        return min_val

    def peek(self):
        return self.heap[0] if self.heap else None

    def build_heap(self, array):
        self.heap = array[:]
        for i in reversed(range(len(self.heap)//2)):
            self._bubble_down(i)

    def _bubble_up(self, index):
        parent = (index - 1) // 2
        while index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            index = parent
            parent = (index - 1) // 2

    def _bubble_down(self, index):
        child = 2 * index + 1
        size = len(self.heap)
        while child < size:
            right = child + 1
            if right < size and self.heap[right] < self.heap[child]:
                child = right
            if self.heap[index] <= self.heap[child]:
                break
            self.heap[index], self.heap[child] = self.heap[child], self.heap[index]
            index = child
            child = 2 * index + 1

Example

This example shows inserting values into a min-heap, extracting the minimum, and building a heap from an array.

python

heap = MinHeap()
heap.insert(10)
heap.insert(4)
heap.insert(15)
heap.insert(20)
print("Min after inserts:", heap.peek())
print("Extract min:", heap.extract_min())
print("Min after extract:", heap.peek())

array = [9, 5, 6, 2, 3]
heap.build_heap(array)
print("Heap built from array, min:", heap.peek())

Output

Min after inserts: 4
Extract min: 4
Min after extract: 10
Heap built from array, min: 2

Common Pitfalls

Common mistakes when working with heaps include:

• Assuming insert or extract are O(1) instead of O(log n). Each operation may move elements up or down the tree.
• Not maintaining the heap property after insertions or removals, which breaks the heap structure.
• Using build_heap inefficiently by inserting elements one by one instead of using the optimized O(n) heapify method.

Example of inefficient build:

python

# Inefficient build by inserting one by one
heap = MinHeap()
for val in [9, 5, 6, 2, 3]:
    heap.insert(val)  # Each insert is O(log n), total O(n log n)

# Efficient build using build_heap
heap2 = MinHeap()
heap2.build_heap([9, 5, 6, 2, 3])  # O(n) time

Quick Reference

Summary of time complexities for heap operations:

Operation	Time Complexity
Insert	O(log n)
Extract Min/Max	O(log n)
Peek (Top Element)	O(1)
Build Heap (Heapify)	O(n)

Key Takeaways

Heap insert and extract operations run in O(log n) time due to tree height.

Accessing the top element of a heap is O(1) since it's always at the root.

Building a heap from an unordered array can be done efficiently in O(n) time.

Avoid inserting elements one by one when building a heap; use heapify instead.

Maintaining the heap property after each operation is essential for correct behavior.