What is a Max-Heap? Complete Guide with Examples

What is a max-heap?

A max heap is a useful binary tree data structure where each parent node is equal to or greater than its child nodes, making the maximum element always accessible at the root. We’ll explore how max heaps work, their key operations, and practical implementations with Python code examples.

Among the two main types of heaps—min heap and max heap—the max heap plays a particularly crucial role when we want to retrieve the largest element quickly and efficiently. This structural and ordering property makes max heaps ideal for scenarios where finding or removing the maximum element needs to be done rapidly, such as in priority queues, task scheduling, and sorting algorithms like heapsort.

Next, let’s see how max-heaps are represented in data structures.

Max-heap representation

While a max-heap is conceptually a binary tree, it is commonly implemented using a single-dimensional array. This is because of its complete structure, which allows for a very efficient and predictable mapping between tree nodes and array indices — avoiding the need for complex pointer-based tree structures.

In a 0-based array representation of a max-heap, the relationships between a node and its children or parent can be calculated using simple arithmetic.

Let a node be at index i:

These formulas are constant-time operations, contributing to the O(log n) time complexity of heap operations.

Here is a diagram that shows the array representation of a max-heap:

Now that we know how max-heaps are represented in data structures, let’s go through the basic operations that we can perform on a max-heap.

Basic max-heap operations

A max-heap supports three fundamental operations:

• Insertion
• Deletion
• Peek

These operations maintain the heap property through heapify, which is the process of rearranging a binary tree or array to satisfy the heap property — either for a max-heap (parent ≥ children) or a min-heap (parent ≤ children).

It is a core operation used to:

• Restore the heap after an insertion or deletion
• Build a heap from an unsorted array
• Maintain the heap structure during sorting (e.g., heapsort)

There are two types of heapify:

• Heapify up: Moves an element up the tree if it’s larger than its parent
• Heapify down: Moves an element down the tree if it’s smaller than its child

We’ll now examine each operation in detail.

Insertion

This operation inserts a new element into a max-heap.

Here is the algorithm for it:

1. Append the new element at the end of the array (maintains completeness)
2. Perform heapify up:
   • Compare the new element with its parent
   • If it’s greater than its parent, swap them
   • Repeat this process until the heap property is restored

This example shows how to insert elements one by one into an initially empty max-heap. Each new element is added to the end of the heap and then heapified up to its correct position to maintain the max-heap property:

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

# Example usage 
heap = [] 
insert(heap, 20) 
insert(heap, 15) 
insert(heap, 30) 
insert(heap, 10) 

print("Heap after insertions:", heap) 

Copy to clipboard
Copy to clipboard

The output will be:

Heap after insertions: [30, 15, 20, 10] 

Copy to clipboard
Copy to clipboard

Deletion

This operation deletes and returns the maximum element (the root of the heap).

Here is the algorithm for it:

1. Replace the root with the last element in the array
2. Remove the last element
3. Perform heapify down:
   • Compare the new root with its children
   • Swap with the larger child if necessary
   • Repeat until the heap property is restored

This example demonstrates how to remove the maximum element (the root) from a max-heap. After removing the root, the last element is moved to the top and then heapified down to restore the max-heap structure:

def extract_max(heap): 
    if not heap: 
        return None 
    if len(heap) == 1: 
        return heap.pop() 
    max_value = heap[0] 
    heap[0] = heap.pop()  # Replace root with last element 
    index = 0 
    while True: 
        left = 2 * index + 1 
        right = 2 * index + 2 
        largest = index 
        if left < len(heap) and heap[left] > heap[largest]: 
            largest = left 
        if right < len(heap) and heap[right] > heap[largest]: 
            largest = right 
        if largest == index: 
            break 
        heap[index], heap[largest] = heap[largest], heap[index] 
        index = largest 
    return max_value 

# Example usage 
heap = [50, 30, 40, 10, 5, 20] 
print("Initial heap:", heap) 
max_val = extract_max(heap) 
print("Extracted max value:", max_val) 
print("Heap after extraction:", heap) 

Copy to clipboard
Copy to clipboard

The output will be:

Initial heap: [50, 30, 40, 10, 5, 20] 
Extracted max value: 50 
Heap after extraction: [40, 30, 20, 10, 5] 

Copy to clipboard
Copy to clipboard

Peek

This operation returns the maximum element without modifying the max-heap.

Here is the algorithm for it:

1. Return the value at index 0 of the array if the heap is not empty.

This example illustrates how to simply look at the maximum element in a max-heap without removing it. This operation is constant-time because the maximum is always at index 0:

def peek(heap): 
    return heap[0] if heap else None 
  
# Example usage 
heap = [60, 25, 40, 10] 
print("Current heap:", heap) 
print("Maximum value (peek):", peek(heap)) 

Copy to clipboard
Copy to clipboard

The output will be:

Current heap: [60, 25, 40, 10] 
Maximum value (peek): 60 

Copy to clipboard
Copy to clipboard

With the basic max-heap operations covered, let’s check out the advantages and disadvantages of using max-heaps.

Advantages and disadvantages of using max-heaps

Max-heaps offer several key advantages:

• Efficient access to maximum element: The root node (index 0 in array representation) always contains the maximum element, allowing constant-time O(1) access.
• Efficient insertion and deletion: Both insertion and deletion (of the root) take O(log n) time due to the tree’s height-balanced nature.
• Memory efficient (Array-based storage): Max-heaps can be efficiently stored in arrays without the need for pointers, making them space-efficient, and cache-friendly.
• Useful in priority queues: Ideal for implementing max-priority queues where you frequently need to fetch the highest-priority element.

However, there are some disadvantages as well:

• Not ideal for searching arbitrary elements: Searching for an arbitrary element (other than the max) is inefficient, requiring O(n) time in the worst case.
• Not always balanced like BSTs: Unlike AVL or Red-Black Trees, max-heaps do not guarantee balanced binary search tree properties, making range queries or order-based operations inefficient.
• Only gives access to maximum: You can’t directly access the second-largest, third-largest, and more without removing elements or scanning the heap.
• Insertion may require heapify: Adding many elements in sequence may require repeated re-heapification, which could lead to performance hits if not managed carefully (e.g., via bulk heapify for large datasets)

Now let’s explore real-world applications of max-heaps.

Applications of max-heaps

Max-heaps are used in various real-world applications:

• Priority queues: Tasks with higher priority (larger key) are processed first.
• Heapsort: A comparison-based sorting technique with O(n log n) complexity.
• Real-time systems: Scheduling tasks by priority.
• Graph algorithms: Like Prim’s and Dijkstra’s algorithms when implemented with a priority queue.

These applications prove that max-heaps are an essential data structure in various scenarios.

Conclusion

Max-heaps are a powerful and versatile data structure. Their predictable structure and efficient operations make them suitable for a range of applications, from sorting to scheduling and graph algorithms. By mastering max-heaps, you gain a valuable tool for optimizing performance in many computational problems.

If you want to learn more about heaps, check out the Learn Complex Data Structures course on Codecademy.

Frequently asked questions

1. What is the difference between a max-heap and a min-heap?

A max-heap ensures that the parent node is always greater than or equal to its children, so the largest element is at the root. In contrast, a min-heap ensures the smallest element is at the root, with each parent smaller than its children.

2. Can a max-heap have duplicate values?

Yes, a max-heap can contain duplicate values. The heap property only requires that each parent is greater than or equal to its children, not that values be unique.

3. Is a max-heap the same as a binary search tree (BST)?

No, they are different:

• A max-heap only guarantees that parent nodes are greater than children.
• A BST guarantees that the left subtree contains smaller values, whereas the right subtree contains larger ones.

4. When should I use a max-heap?

Use a max-heap when you need to:

• Quickly retrieve the largest element (e.g., priority queues).
• Sort elements using heapsort.
• Implement task schedulers, bandwidth managers, or real-time data streams (like finding the top-k largest elements).

5. How is a max-heap used in heapsort?

In heapsort:

• A max-heap is built from the input array.
• The largest element (root) is swapped with the last item and removed from the heap.
• The heap is re-heapified.
• Repeat until the array is sorted.

This results in a sorted array in ascending order.