Python heapq #1

Alysia Alfi

5 min read

·

Jun 20, 2025

--

Listen

Share

this writing is part of #AlfiLearnsToCompetitiveProgramming

Heapq. What kind of food is that? Exactly what I thought before getting into competitive programming.

Until one day, I did a LeetCode Network Delay Time which by any chance, Heapq is more than “kind of food”.

Now, let’s see why Heapq is powerful. Imagine you have a list, and you need to return the smallest value in the list. My intuition will definitely goes for sort()

numbers = [3, 1, 4, 1, 5, 9, 2]
numbers.sort()
print(numbers[0]) // Output: 1

And here’s when using heapq

import heapq

numbers = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(numbers)
smallest = heapq.heappop(numbers)
print(smallest) // Output: 1

Longer, but faster. Yes, heapq has time complexity of O(log n) compared to O(n²) for sort(). This happens cause heapq uses a simple and strict tree structure for one specific job called priority queues, while sorted() uses a complex and adaptive designed to be the fastest possible general-purpose sort for the types of data people use in the real world, which mostly are not that long.

Priority Queue

A heap queue, or a heap, is a way of organizing data in a list that makes it really fast to find the smallest item. Imagine a list where the first item is always the smallest one. That’s the main idea of a min-heap.

Priority queue is where the smallest is always at the front. With a heap, the item at index 0 is always the smallest. This is helpful when we constantly need to know what the minimum value in the list is.

Heapify

heapq uses binary tree under the hood, it will do the top-down operation with bottom-up order. Meaning it will start the operation from the last parent up to the first parent node while guarantee the first element heap[0] is the smallest item in the list (min-heap).

As to flash back, binary tree has parent and child nodes. A node with one or two children is a parent, and the nodes connected below are its children.

For this list [3, 1, 4, 1, 5, 9, 2], we can have this imaginary binary tree

          3(0)
         /    \
        /      \
      1(1)     4(2)
     /    \      / \
   1(3)  5(4)  9(5) 2(6)

To convert a regular list into a min-heap, heapq provides a function called heapify(). Let’s take a look on how heapify() works with the list above. Remember the rule: parent must be smaller than or equal to its children.

The process:

a. Start from the last parent node (remember bottom-up, we’ll go way up to the root afterwards).

  4
 / \
9   2

• Current list: [3, 1, 4, 1, 5, 9, 2]
• Check: Is 4 smaller than its children 9 and 2? No.
• Action: Swap 4 with its smallest child, 2.
• Current list: [3, 1, 2, 1, 5, 9, 4]

  2
 / \
9   4

b. Next up, second last parent node

  1
 / \
1   5

• Current list: [3, 1, 2, 1, 5, 9, 4]
• Check: Is 1 smaller than or equal to its children (1 and 5)? Yes. The heap property keep it as is.
• Action: No swap needed.
• Current list: [3, 1, 2, 1, 5, 9, 4]

  1
 / \
1   5

c. Lastly, the first parent or the root

  3
 / \
1   2

• Current list: [3, 1, 2, 1, 5, 9, 4]
• Check: Is 3 smaller than its children 1 and 2? No.
• Action: Swap 3 with its smallest child, 1.
• Current list: [1, 3, 2, 1, 5, 9, 4]

  1
 / \
3   2

At this point, we don’t continue to the next parent or finish up (if the binary tree happens to be completely scanned). Since it’s the root or first parent, which has several parent-child groups below, the heapify() will have internal looping or sift-down for making sure that those parent-child groups don’t violate the rule (parent must be smaller than or equal to its children).

Now, current binary tree looks like this

          1(0)
         /    \
        /      \
      3(1)     2(2)
     /    \      / \
   1(3)  5(4)  9(5) 4(6)

We can see that second last parent [3, 1, 2] violates the rule, thus heapify() will swap it up and continue the check, does any other parent-child group that violate it. Thus, here’s the current heapified list[1, 1, 2, 3, 5, 9, 4] and the binary tree:

       1(0)
      /    \
     /      \
   1(1)     2(2)
  /    \      / \
 3(3)  5(4)  9(5) 4(6)

Heappop

Refers to Python docs, heappop is an operation to remove and return the smallest item from the heap, maintaining the heap unchanged. The heappop() function always does two things:

1. Removes and returns the smallest item (which is always at the root, index 0).
2. Restores the heap property by fixing the binary tree structure.

For our heapified list [1, 1, 2, 3, 5, 9, 4], we can conclude that heappop will give us 1 as the smallest item, but how does it restructure the binary tree? Let’s see how it does under the hood

The process

a. Remove the Root

The smallest element is always at index 0. The function takes this element and sets it aside to be returned to the program at the very end.

• Return: 1
• The heap now has a temporary empty spot at the root.

     [EMPTY](0)
      /    \
     /      \
   1(1)     2(2)
  /    \      / \
 3(3)  5(4)  9(5) 4(6)

b. Move the Last Element to the Root

To fill the empty spot at the root,heapq takes the very last element in the list and moves it to index 0.

• Last element: 4 (at index 6)
• Action: Move 4 to the root position.

The list now looks like this [4, 1, 2, 3, 5, 9], so does the binary tree

       4(0)
      /    \
     /      \
   1(1)     2(2)
  /    \      |
 3(3)  5(4)  9(5)

c. Sift the New Root Down

Since current binary tree violates the rule, heapq fix the tree by sifting the new root (4) down until it's in a valid position. This is the exact same sift-down logic we used before.

• Node: 4 (at index 0)
• Children: 1 (at index 1) and 2 (at index 2)
• Check: Is 4 smaller than its children? No.
• Action: Swap 4 with its smallest child, which is 1.

The list now looks like this [1, 4, 2, 3, 5, 9], so does the binary tree

       1(0)
      /    \
     /      \
   4(1)     2(2)
  /    \      |
 3(3)  5(4)  9(5) 

Not finished yet, still have children to check up

• Node: 4 (at index 1)
• Children: 3 (at index 3) and 5 (at index 4)
• Check: Is 4 smaller than its children? No.
• Action: Swap 4 with its smallest child, which is 3.

Finally, The list is now [1, 3, 2, 4, 5, 9] following the binary tree

       1(0)
      /    \
     /      \
   3(1)     2(2)
  /    \      |
 4(3)  5(4)  9(5)

Yay! Everything is in its order, now the heappop can leave the room 🚪.

Conclusion

heapify() and heappop() work together to create and maintain a priority queue called min-heap.

• heapify is the constructor, it builds the queue.
• heappop is the operator, it provides the queue by delivering the next priority item and ensuring the queue remains valid for the next operation.

heapify() establishes the smallest-item-first guarantee, and heappop() keep that guarantee after every operation, ensuring that program always have immediate, efficient access to the minimum value for list.