Heap Operations: Insert, Delete, and Heapify

Key Insights

Heaps use a simple array representation where parent-child relationships are calculated through index arithmetic, making them memory-efficient and cache-friendly compared to pointer-based trees.
The heapify operation is the foundation of all heap operations—master it once, and insert, delete, and build operations become straightforward variations of the same principle.
Building a heap from an unsorted array takes O(n) time using bottom-up heapify, not O(n log n)—this counterintuitive result comes from the fact that most nodes are near the bottom where heapify does minimal work.

Introduction to Heaps

A heap is a complete binary tree stored in an array that satisfies the heap property: every parent node is smaller than its children (min-heap) or larger than its children (max-heap). This structure gives you O(1) access to the minimum or maximum element while maintaining O(log n) insertions and deletions.

The array representation is elegant. For any element at index i, you can find its parent at (i - 1) / 2, its left child at 2i + 1, and its right child at 2i + 2. No pointers needed.

class MinHeap:
    def __init__(self):
        self.data = []
    
    def parent(self, i: int) -> int:
        return (i - 1) // 2
    
    def left_child(self, i: int) -> int:
        return 2 * i + 1
    
    def right_child(self, i: int) -> int:
        return 2 * i + 2
    
    def has_left(self, i: int) -> bool:
        return self.left_child(i) < len(self.data)
    
    def has_right(self, i: int) -> bool:
        return self.right_child(i) < len(self.data)
    
    def swap(self, i: int, j: int) -> None:
        self.data[i], self.data[j] = self.data[j], self.data[i]
    
    def peek(self) -> int:
        if not self.data:
            raise IndexError("Heap is empty")
        return self.data[0]

This representation works because heaps are complete binary trees—every level is fully filled except possibly the last, which is filled left to right. This property guarantees no gaps in the array.

The Heapify Operation

Heapify-down (also called sift-down or percolate-down) is the core operation that restores the heap property when a node violates it by being larger than one of its children. You compare the node with its children, swap with the smaller child if necessary, and repeat until the node settles into its correct position.

def heapify_down(self, i: int) -> None:
    """
    Restore heap property by moving element at index i down the tree.
    Time complexity: O(log n) - at most the height of the tree.
    """
    while self.has_left(i):
        # Find the smaller child
        smaller_child = self.left_child(i)
        
        if self.has_right(i) and self.data[self.right_child(i)] < self.data[smaller_child]:
            smaller_child = self.right_child(i)
        
        # If heap property is satisfied, we're done
        if self.data[i] <= self.data[smaller_child]:
            break
        
        # Otherwise, swap and continue
        self.swap(i, smaller_child)
        i = smaller_child

The time complexity is O(log n) because the element can travel at most from root to leaf—the height of the tree. In a complete binary tree with n elements, the height is floor(log₂ n).

Heapify-down is used after removing the root element and when building a heap from an unsorted array. Understanding this single operation unlocks the rest of heap manipulation.

Insertion Operation

Inserting into a heap follows a simple two-step process: append the new element to the end of the array (maintaining the complete tree property), then bubble it up to restore the heap property.

Heapify-up (or sift-up) is the inverse of heapify-down. You compare the element with its parent and swap if the element is smaller, repeating until the element reaches its correct position.

def heapify_up(self, i: int) -> None:
    """
    Restore heap property by moving element at index i up the tree.
    Time complexity: O(log n) - at most the height of the tree.
    """
    while i > 0:
        parent_idx = self.parent(i)
        
        # If heap property is satisfied, we're done
        if self.data[parent_idx] <= self.data[i]:
            break
        
        # Otherwise, swap and continue
        self.swap(i, parent_idx)
        i = parent_idx

def insert(self, value: int) -> None:
    """
    Insert a new element into the heap.
    Time complexity: O(log n)
    """
    self.data.append(value)
    self.heapify_up(len(self.data) - 1)

Let’s trace through an example. Starting with heap [2, 4, 8, 5, 7], we insert 1:

Step 1: Append to end
[2, 4, 8, 5, 7, 1]
         2
       /   \
      4     8
     / \   /
    5   7 1

Step 2: Compare 1 with parent 8 (index 2), swap
[2, 4, 1, 5, 7, 8]

Step 3: Compare 1 with parent 2 (index 0), swap
[1, 4, 2, 5, 7, 8]

Final heap:
         1
       /   \
      4     2
     / \   /
    5   7 8

The element bubbles up until it finds its correct position. Worst case, it travels from the last position to the root—O(log n) swaps.

Deletion Operation (Extract Min/Max)

Extracting the minimum element from a min-heap requires removing the root. The trick is to maintain the complete tree property: swap the root with the last element, remove the last element, then heapify-down from the root.

def extract_min(self) -> int:
    """
    Remove and return the minimum element.
    Time complexity: O(log n)
    """
    if not self.data:
        raise IndexError("Heap is empty")
    
    min_value = self.data[0]
    
    # Move last element to root
    self.data[0] = self.data[-1]
    self.data.pop()
    
    # Restore heap property (if heap isn't empty)
    if self.data:
        self.heapify_down(0)
    
    return min_value

Tracing through extraction from [1, 4, 2, 5, 7, 8]:

Step 1: Save min value (1), move last element (8) to root
[8, 4, 2, 5, 7]

Step 2: Heapify-down from root
Compare 8 with children 4 and 2, swap with smaller (2)
[2, 4, 8, 5, 7]

Step 3: 8 has no children at new position, done
Final heap: [2, 4, 8, 5, 7]

For deleting an arbitrary element at index i, the approach is similar but requires a choice: after swapping with the last element, you might need to heapify-up or heapify-down depending on whether the replacement is smaller or larger than the original.

def delete_at(self, i: int) -> int:
    """
    Delete element at arbitrary index.
    Time complexity: O(log n)
    """
    if i >= len(self.data):
        raise IndexError("Index out of bounds")
    
    deleted_value = self.data[i]
    last_value = self.data[-1]
    self.data.pop()
    
    if i < len(self.data):
        self.data[i] = last_value
        
        # Determine direction to heapify
        if i > 0 and self.data[i] < self.data[self.parent(i)]:
            self.heapify_up(i)
        else:
            self.heapify_down(i)
    
    return deleted_value

Building a Heap from an Array

The naive approach inserts elements one by one, yielding O(n log n) time. But there’s a better way: start from the last non-leaf node and heapify-down each node working backward to the root.

def build_heap(self, arr: list) -> None:
    """
    Build heap from unsorted array in O(n) time.
    Uses bottom-up heapify starting from last non-leaf node.
    """
    self.data = arr.copy()
    
    # Start from last non-leaf node (parent of last element)
    start = self.parent(len(self.data) - 1)
    
    # Heapify each node from bottom to top
    for i in range(start, -1, -1):
        self.heapify_down(i)

Why is this O(n) instead of O(n log n)? The key insight is that most nodes are near the bottom of the tree where heapify-down does very little work.

Consider a heap with n nodes:

n/2 nodes are leaves (heapify cost: 0)
n/4 nodes are one level up (heapify cost: at most 1 swap)
n/8 nodes are two levels up (heapify cost: at most 2 swaps)
And so on…

The total work is: n/4 × 1 + n/8 × 2 + n/16 × 3 + … = O(n)

This is a geometric series that converges to approximately 2n operations—linear time.

# Example: Building heap from [5, 3, 8, 1, 2, 9, 4]
# Last non-leaf index: (7-1)//2 = 3 (value 1)
# But 1 has no children in this array, so start at index 2

# Index 2 (value 8): children are 9, 4 → swap with 4
# [5, 3, 4, 1, 2, 9, 8]

# Index 1 (value 3): children are 1, 2 → swap with 1
# [5, 1, 4, 3, 2, 9, 8]

# Index 0 (value 5): children are 1, 4 → swap with 1
# [1, 5, 4, 3, 2, 9, 8]
# Continue: 5's children are 3, 2 → swap with 2
# [1, 2, 4, 3, 5, 9, 8]

# Final min-heap: [1, 2, 4, 3, 5, 9, 8]

Time Complexity Summary and Practical Applications

Operation	Time Complexity	Notes
peek	O(1)	Direct array access
insert	O(log n)	Append + heapify-up
extract_min/max	O(log n)	Swap + heapify-down
delete_at	O(log n)	Swap + heapify (either direction)
build_heap	O(n)	Bottom-up heapify

Heaps power several important algorithms. Dijkstra’s shortest path uses a min-heap to always process the closest unvisited node. Heap sort achieves O(n log n) in-place sorting. The median-finding problem uses two heaps to track running median in O(log n) per element.

Here’s a complete priority queue implementation:

class PriorityQueue:
    """Priority queue backed by a min-heap."""
    
    def __init__(self):
        self.heap = MinHeap()
    
    def push(self, priority: int, item: any) -> None:
        self.heap.insert((priority, item))
    
    def pop(self) -> any:
        priority, item = self.heap.extract_min()
        return item
    
    def peek(self) -> any:
        priority, item = self.heap.peek()
        return item
    
    def is_empty(self) -> bool:
        return len(self.heap.data) == 0


# Usage: Task scheduling
pq = PriorityQueue()
pq.push(3, "low priority task")
pq.push(1, "urgent task")
pq.push(2, "medium priority task")

while not pq.is_empty():
    print(pq.pop())
# Output: urgent task, medium priority task, low priority task

The heap’s guarantee of O(log n) insertion and extraction with O(1) access to the extreme element makes it the right choice whenever you need to repeatedly find and remove the minimum or maximum from a dynamic collection. When you find yourself sorting a list just to grab the smallest element, reach for a heap instead.