Max Heap

How Max Heap Works

A Max Heap is a complete binary tree where the parent node is always larger than or equal to its children. The root of the tree is always the maximum element in the heap.

Key operations:

• Insert: O(log n) - Add an element to the end and bubble up
• Extract Max: O(log n) - Remove the root, replace with last element, and bubble down
• Peek Max: O(1) - Return the root element without removing it

Max Heaps are commonly used in heap sort, finding the k largest elements, and in certain priority queue applications where the highest priority element needs to be processed first.

class MaxHeap:
    heap

    function insert(value):
        heap.append(value)
        heapifyUp(heap.length - 1)
        visualize()

    function extractMax():
        if heap is empty:
            return null
        max = heap[0]
        lastElement = heap.pop()
        if heap is not empty:
            heap[0] = lastElement
            heapifyDown(0)
        visualize()
        return max

    function heapifyUp(index):
        while index > 0 and heap[parent(index)] < heap[index]:
            swap heap[parent(index)] and heap[index]
            index = parent(index)

    function heapifyDown(index):
        maxIndex = index
        left = leftChild(index)
        right = rightChild(index)
        if left < heap.length and heap[left] > heap[maxIndex]:
            maxIndex = left
        if right < heap.length and heap[right] > heap[maxIndex]:
            maxIndex = right
        if maxIndex != index:
            swap heap[index] and heap[maxIndex]
            heapifyDown(maxIndex)

    function parent(i): return (i - 1) / 2
    function leftChild(i): return 2 * i + 1
    function rightChild(i): return 2 * i + 2