Python heapq

heapq is a library in Python that provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. A heap is a complete binary tree that satisfies the heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.

Here are some examples of using the heapq library in Python:

1. Creating a heap

To create a heap, you can use the heapify() function, which converts a regular list to a heap. For example:

import heapq

# Convert a regular list to a heap
heap = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(heap)

print(heap)  # Output: [0, 1, 2, 6, 3, 5, 4, 7, 8, 9]

The heapify() function rearranges the list so that it satisfies the heap property, with the smallest element at the root.

2. Pushing elements onto the heap

To add an element to the heap, you can use the heappush() function. For example:

import heapq

# Add an element to the heap
heap = [1, 3, 5]
heapq.heappush(heap, 2)

print(heap)  # Output: [1, 3, 5, 2]

The heappush() function adds the element to the end of the list and then rearranges the list to maintain the heap property.

3. Popping elements from the heap

To remove the smallest element from the heap, you can use the heappop() function. For example:

import heapq

# Remove the smallest element from the heap
heap = [1, 3, 5, 2]
smallest = heapq.heappop(heap)

print(smallest)  # Output: 1
print(heap)      # Output: [2, 3, 5]

The heappop() function removes the first element from the list (which is the smallest element, since the list is a heap) and then rearranges the remaining elements to maintain the heap property.

Get M Haque’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

4. Retrieving the smallest element from the heap

To retrieve the smallest element from the heap without removing it, we can use the heap[0] index. For example:

import heapq

# Retrieve the smallest element from the heap
heap = [1, 3, 5, 2]
smallest = heap[0]

print(smallest)  # Output: 1
print(heap)      # Output: [1, 3, 5, 2]

5. Replacing an element in the heap

To replace an element in the heap with a new element, we can use the heapreplace() function. For example:

import heapq

# Replace an element in the heap
heap = [1, 3, 5, 2]
new_element = heapq.heapreplace(heap, 4)

print(new_element)  # Output: 2
print(heap)         # Output: [1, 3

The time complexity of the heapq library in Python depends on the specific function we are using. Here is a summary of the time complexity of the main functions in the heapq library:

• heapify(): O(n)
• heappush(): O(log n)
• heappop(): O(log n)
• heapreplace(): O(log n)

The time complexity of heapify() is O(n), since it needs to rearrange all the elements in the list to satisfy the heap property. The time complexity of heappush(), heappop(), and heapreplace() is O(log n), since these functions only need to rearrange a small part of the heap to maintain the heap property.

The space complexity of the heapq library is O(n), since the heap is stored in a list and the size of the list grows as elements are added to the heap.

It’s important to note that the time complexity of the heapq library is only amortized, meaning that the average time complexity over a long sequence of operations may be different from the worst-case time complexity. In particular, the worst-case time complexity of heappush() and heappop() is O(n), since these functions may need to rearrange the entire heap if the element being added or removed is much larger or smaller than the other elements in the heap. However, the average time complexity of these operations is still O(log n), making the heapq library a good choice for implementing a priority queue.