Max Heap

A Max Heap is a specialized tree-based data structure that is heavily used to implement Priority Queues. It is always a complete binary tree, meaning every level is fully filled except possibly the last one, which is filled strictly from left to right.

The Array Magic

Because a Heap is a complete tree, we do not need to create Node objects with "left" and "right" pointers in memory. We can flatten the entire tree into a standard Array. The relationships are calculated using simple math on the indices.

If a parent node is located at index $i$:

• Its Left Child is at index: $2i + 1$
• Its Right Child is at index: $2i + 2$
• Its Parent can be found at: $\lfloor(i - 1) / 2\rfloor$

Core Operations

1. Insertion (Bubble Up / Sift Up)

When you insert a new value, it is first added to the very end of the array (the bottom-right of the tree). Then, it compares itself to its parent. If it is larger, they swap. This "bubbling up" continues until the Heap Property is restored.

def insert(heap, value):
    heap.append(value)
    index = len(heap) - 1
    
    # Bubble Up
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] > heap[parent]:
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break

2. Extract Max (Bubble Down / Sift Down)

Removing the maximum value (the Root) creates a hole at the top of the tree. To fix this:

• Take the very last element of the heap and move it to the Root.
• Compare this new Root with its two children.
• Swap it with the larger of the two children.
• Repeat this "bubbling down" process until it is larger than both children or it reaches the bottom.

3. Arbitrary Deletion

Deleting a specific value anywhere in the heap combines both mechanics. First, we must search for the value and swap it with the last element in the array. Once the last element takes the target's place, it might violate the heap property in either direction!

• If the new value is greater than its new parent, it must Bubble Up.
• If the new value is smaller than its new children, it must Bubble Down.

def delete_value(heap, value):
    try:
        index = heap.index(value) # O(n) search
    except ValueError:
        return # Value not found

    last_index = len(heap) - 1
    if index != last_index:
        # Swap target with the last element
        heap[index], heap[last_index] = heap[last_index], heap[index]
        heap.pop() # Remove the target

        # Check if we need to Bubble Up or Bubble Down
        parent = (index - 1) // 2
        if index > 0 and heap[index] > heap[parent]:
            bubble_up(heap, index)
        else:
            bubble_down(heap, index)
    else:
        heap.pop() # Target was already the last element

Complexity Analysis