How to Create Max Heap in Python: Simple Guide with Examples

Python's heapq module only supports min heaps by default. To create a max heap, you can invert the values by multiplying them by -1 before pushing them into the heap, then invert again when popping.

Syntax

Python's heapq module provides functions to work with heaps, but it only supports min heaps. To simulate a max heap, you store negative values.

• heapq.heappush(heap, item): Adds an item to the heap.
• heapq.heappop(heap): Removes and returns the smallest item.

For max heap, push -item and pop then invert the sign again.

python

import heapq

heap = []
heapq.heappush(heap, -10)  # Push negative to simulate max heap
heapq.heappush(heap, -20)
heapq.heappush(heap, -15)

max_item = -heapq.heappop(heap)  # Pop and invert sign
print(max_item)

Output

20

Example

This example shows how to create a max heap from a list of numbers by pushing their negative values and popping the largest values correctly.

python

import heapq

def max_heapify(nums):
    max_heap = []
    for num in nums:
        heapq.heappush(max_heap, -num)  # Push negative values
    result = []
    while max_heap:
        max_val = -heapq.heappop(max_heap)  # Pop and invert sign
        result.append(max_val)
    return result

numbers = [5, 3, 17, 10, 84, 19, 6, 22, 9]
print(max_heapify(numbers))

Output

[84, 22, 19, 17, 10, 9, 6, 5, 3]

Common Pitfalls

One common mistake is to try using heapq directly as a max heap without negating values, which will give incorrect results because it always treats the smallest value as the root.

Another pitfall is forgetting to invert the sign when popping, which leads to wrong output.

python

import heapq

# Wrong way: pushing values directly (min heap behavior)
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
heapq.heappush(heap, 15)
print(heapq.heappop(heap))  # Outputs 10, not max

# Right way: push negative values
heap = []
heapq.heappush(heap, -10)
heapq.heappush(heap, -20)
heapq.heappush(heap, -15)
print(-heapq.heappop(heap))  # Outputs 20, max value

Output

10
20

Quick Reference

• Use heapq for heap operations in Python.
• Invert values by multiplying by -1 to simulate max heap.
• Remember to invert sign back when popping.
• Min heap is default behavior of heapq.

Key Takeaways

Python's heapq module only supports min heaps by default.

Create a max heap by pushing negative values and popping with sign inversion.

Always invert the sign back when retrieving values from the heap.

Forgetting to invert signs causes incorrect heap behavior.

heapq.heappush and heapq.heappop are the main functions to manage heaps.