How to Get Max Heap in Python

1. Get Max Heap With Numbers in Python
2. Get Max Heap With Tuples in Python
3. References

The heap is the data structure of choice for implementing a priority queue. Unlike a binary search tree, a heap is not fully ordered; there is no definite order between siblings or cousins.

In Python, the heapq module implements the heap queue algorithm. However, heapq only provides the Min Heap implementation, in which the value of any parent node is less than or equal to either of its children’s values.

The main function, heappop(), returns the smallest element of the heap.

This article will discuss implementing the Max Heap behavior in Python by combining heapq with some custom code.

Get Max Heap With Numbers in Python

The most common strategy when dealing with numbers is multiplying the list’s elements with -1. The heapq functions can take care of the heap.

After popping the smallest value, we need to again multiply the output by -1 to get the maximum value.

Example Code:

# import the heapq module.
import heapq

# Max Heap With Numbers

# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)

# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)

# Make the heap.
heapq.heapify(x_inv)

# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)

Output:

print(x)
[5, 4, 3, 6, 8, 7, 2, 1]

print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]

-1 * heapq.heappop(x_inv)
Out[8]: 8

-1 * heapq.heappop(x_inv)
Out[9]: 7

-1 * heapq.heappop(x_inv)
Out[10]: 6

Get Max Heap With Tuples in Python

We may want to implement a priority queue with tuples rather than just numbers. Since Python’s tuples are immutable, this is a challenge to the task of multiplying the priority number with -1.

The solution lies in first converting each tuple to a list, modifying the first element of these sub-lists by -1, converting them back to tuples, and simultaneously creating a new list with these tuples. The new list is then converted to a heap using heapify().

To pop the maximum value, we use heappop() on the heap, convert the tuple to a list, modify the first element to get a positive value, then convert the list back to a tuple.

Example Code:

# Max Heap With Tuples

# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l

# Create an empty list to hold modified tuples.
l_max = []

# Populate the list with modified tuples.
for i in range(len(l)):
    j = list(l[i])
    j[0] = -1 * j[0]
    l_max.append(tuple(j))

# View the modified list.
l_max

# Create the min heap.
heapq.heapify(l_max)

# View the min-heap.
l_max

# Create a function that uses meappop and
# changes the number back to a positive value.


def maxpop(mh):
    l = list(heapq.heappop(mh))
    l[0] = -1 * l[0]
    return tuple(l)


# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)

Output:

l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]

l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]

heapq.heapify(l_max)

l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]

maxpop(l_max)
Out[19]: (7, 'D')

maxpop(l_max)
Out[20]: (6.5, 'E')

maxpop(l_max)
Out[21]: (5, 'B')

Other needed heap functions can be implemented using the same techniques.

References

See the documentation of the heapq module of Python for more details and examples.

The Python development team has decided not to implement max heap functions. You can read the feature request and the response here.