Min-heaps

In brief

Article summary

In this article, you will learn about min-heaps, which are data structures that have particular properties. They will be very useful to use in Dijkstra’s algorithm.

Main takeaways

• Min-heaps are data structures in which data are popped using a reference value.

• It can be used to easily implement Dijkstra’s algorithm.

• There are many ways to program a min-heap, some better than others.

• In Python, heapq provides a good implementation for min-heaps.

Article contents

1 — Video

Please check the video below. You can also read the transcripts if you prefer.

Here are a few important remarks on this video:

• In this video, we have used the terms “key” (the thing we want to store) and “value” (its importance in the heap). Other terminologies exist! The only important aspect is that remove should return the minimum element from the heap. Beware how this minimum is computed though!

• In the video, you are presented a possible implementation of Dijkstra’s algorithm, that uses a function called add_or_replace. Here, we just explain you what the function does but do not provide its code. When implementing the algorithm in Python, you will need to create such a function, or to think otherwise…

To go further

2 — A naive implementation of a min-heap using a list

A simple (yet quite inefficient) way to implement a in-heap is to use a list. This list stores pairs (key, value). Here, we show how to create a min-heap using a list.

Let’s create a class for our naive min-heap. This will allow to create a new min-heap, and to perform operations on it:

class ListBasedMinHeap ():

In the constructor of our class, we create an attribute to store the elements. In this implementation, we simply create an empty list:

def __init__ (self):

    # We create an attribute to store the elements
    self.elements = []

Now, we need to define the two methods presented in the video: add_or_replace, and remove. Let’s start with the first one.

We are going to to as follows:

• First, we check if the list contains the key we want to add.
• If it is the case, and the associated value is higher than the value we want to add, we remove it.
• Finally, we add the pair (key, value) we want to store if needed.

This corresponds to the following code:

def add_or_replace (self, key, value):
    
    # We check if the key is already in the heap
    index = None
    for i in range(len(self.elements)):
        if self.elements[i][0] == key:
            index = i
            break
    
    # If the key is already in the heap, we remove the previous element if the new value is lower
    add_new_element = True
    if index is not None:
        if value < self.elements[index][1]:
            del self.elements[index]
        else:
            add_new_element = False

    # We add the new element
    if add_new_element:
        self.elements.append((key, value))

In terms of complexity, this implementation needs to go through the whole list of elements. As that list can contain up to $n$ elements, where $n$ is the number of vertices in the graph, it is of complexity $O(n)$.

Now, to remove an element, let’s just compare values of all elements in the list, and return the one with lowest value:

def remove (self):

    # We find the element with the smallest value
    min_index = 0
    for i in range(1, len(self.elements)):
        if self.elements[i][1] < self.elements[min_index][1]:
            min_index = i

    # We remove the element with the smallest value
    key, value = self.elements[min_index]
    del self.elements[min_index]

    # We return the key and value of the element removed
    return key, value

In terms of complexity, this implementation is of complexity $O(n)$ for the same reasons as above.

Let’s test our min-heap using the same example as in the video:

# Create a min-heap
heap = ListBasedMinHeap()

# Add elements to the heap
heap.add_or_replace("A", 50)
heap.add_or_replace("B", 22)
heap.add_or_replace("C", 10)

# Show the elements of the heap
print("Heap initial state:", heap.elements)

# Remove the element with the smallest value
key, value = heap.remove()
print("Removed:", key, value)
print("Heap after remove():", heap.elements)

# Add a new element to the heap
heap.add_or_replace("B", 45)
print("Heap after add_or_replace(B, 45):", heap.elements)

# Add a new element to the heap
heap.add_or_replace("A", 35)
print("Heap after add_or_replace(A, 35):", heap.elements)

# Remove the element with the smallest value
key, value = heap.remove()
print("Removed:", key, value)
print("Heap after remove():", heap.elements)

Here is the produced output:

Heap initial state: [('A', 50), ('B', 22), ('C', 10)]
Removed: C 10
Heap after remove(): [('A', 50), ('B', 22)]
Heap after add_or_replace(B, 45): [('A', 50), ('B', 22)]
Heap after add_or_replace(A, 35): [('B', 22), ('A', 35)]
Removed: B 22
Heap after remove(): [('A', 35)]

Want to try it yourself? Here is an implementation of that class.

3 — A better implementation

Well, $n$ operations for adding an element, and $n$ operations for removing one, is not super effective. Thus, the complexity of the naive implementation of add_or_replace has an impact on the code performance and energy consumption.

It is pretty obvious that we can do better, for instance by keeping the list sorted, so that remove always needs to return the first element. With such adaptation, remove would have a complexity of $O(1)$, at the cost of a computational overhead in add_or_replace.

In practice, there are even better solutions, based on more complex data structures. In Python, we can use a library called heapq. This library provides you two methods:

• heappush, that adds an element to the min-heap.
• heappop, that removes the minimum element from the min-heap.

Let’s see what happens with the same example as in the video:

# Import heapq
import heapq

# Create a min-heap
heap = []

# Add elements to the heap
heapq.heappush(heap, ("A", 50))
heapq.heappush(heap, ("B", 22))
heapq.heappush(heap, ("C", 10))

# Show the elements of the heap
print("Heap initial state:", heap)

# Remove the element with the smallest value
key, value = heapq.heappop(heap)
print("Removed:", key, value)
print("Heap after heappop():", heap)

# Add a new element to the heap
heapq.heappush(heap, ("B", 45))
print("Heap after heappush(B, 45):", heap)

# Add a new element to the heap
heapq.heappush(heap, ("A", 35))
print("Heap after heappush(A, 35):", heap)

# Remove the element with the smallest value
key, value = heapq.heappop(heap)
print("Removed:", key, value)
print("Heap after heappop():", heap)

Seems pretty similar to what we got before, right? Well, let’s see the output:

Heap initial state: [('A', 50), ('B', 22), ('C', 10)]
Removed: A 50
Heap after heappop(): [('B', 22), ('C', 10)]
Heap after heappush(B, 45): [('B', 22), ('C', 10), ('B', 45)]
Heap after heappush(A, 35): [('A', 35), ('B', 22), ('B', 45), ('C', 10)]
Removed: A 35
Heap after heappop(): [('B', 22), ('C', 10), ('B', 45)]

Doesn’t seem quite right after all. In fact, what this library does is that it returns the minimum element among those that were added. Here, elements are pairs, so heapq will determine which pair is the minimum by thecking their contents in lexicographic order, i.e., the first element of the pair, then the second. In the example above, comparisons are made on "A", "B" and "C" rather than on the numeric values, which are used only when there is an equality on the first entry.

Let’s correct it by flipping the keys and values:

# Import heapq
import heapq

# Create a min-heap
heap = []

# Add elements to the heap
heapq.heappush(heap, (50, "A"))
heapq.heappush(heap, (22, "B"))
heapq.heappush(heap, (10, "C"))

# Show the elements of the heap
print("Heap initial state:", heap)

# Remove the element with the smallest value
value, key = heapq.heappop(heap)
print("Removed:", key, value)
print("Heap after heappop():", heap)

# Add a new element to the heap
heapq.heappush(heap, (45, "B"))
print("Heap after heappush(45, B):", heap)

# Add a new element to the heap
heapq.heappush(heap, (35, "A"))
print("Heap after heappush(35, A):", heap)

# Remove the element with the smallest value
value, key = heapq.heappop(heap)
print("Removed:", key, value)
print("Heap after heappop():", heap)

Let’s see the output:

Heap initial state: [(10, 'C'), (50, 'A'), (22, 'B')]
Removed: C 10
Heap after heappop(): [(22, 'B'), (50, 'A')]
Heap after heappush(45, B): [(22, 'B'), (50, 'A'), (45, 'B')]
Heap after heappush(35, A): [(22, 'B'), (35, 'A'), (45, 'B'), (50, 'A')]
Removed: B 22
Heap after heappop(): [(35, 'A'), (50, 'A'), (45, 'B')]

Better already, but it seems that heappop doesn’t perform a replace operation when the key already exists. Indeed, it only appends elements to a structure, and has no real notion of “keys” or “values”. It just has the property to return the minimum element when asked.

So, how can we use this to implement Dijkstra’s algorithm? In fact, it is possible to simply adapt the algorithm you saw in the course. Indeed, when a vertex is popped from the min-heap, you know that you have found the shortest path to that vertex. Thus, if you later pop the same vertex, you know that this is a longer path to it, therefore you can just ignore it!

Well, that does not tell us if this solution is better than the naive solution. As a matter of fact, heapq is a binary heap, and both heappush and heappop have a complexity of $O(log_2(n))$, which is lower than $O(n)$. See more details below if you wish.

4 — Implementation using a balanced binary tree

4.1 — Definitions

Let us start with a few definitions. You should already know what a tree is, and what we call its root. A vertex in a tree is a “node” if it has neighbors farther from the tree root (which we call children). If not, it is a “leaf”.

The “depth” of a tree is the length of the longest shortest path starting from the root. A tree is “balanced” if all its shortest paths starting from the root have the same length, $\pm 1$.

4.2 — The tree model

Instead of using a list, it is proposed to use a balanced binary tree with the following properties:

• Each node of the tree is associated with a couple (key, value). This property makes it possible to link the tree to the elements to be stored/extracted.
• Every parent node has two children, unless the total number of elements in the priority queue is even, in which case a single node has only one child and all the others have two.
• The tree is balanced. This property ensures that the tree does not have a shape similar to a long chain, by making a kind of list, thus losing all the interest of using trees.
• A parent’s value is always smaller than that of his children. This essential property ensures that the minimum value node is always at the root.

4.3 — Creation

To initialize such a priority queue, simply return an empty tree.

4.4 — Insertion

To insert a couple (key, value) into the tree, proceed as follows:

1. The couple (key, value) is added at the end of the tree, i.e.:

• If all parent nodes have two children, a leaf of minimum depth is transformed into a parent of this node.
• If a parent node has only one child, it is added as a second child this node.

2. If the value of this new node is smaller than that of its parent, the couples (key, value) of the node and its parent are exchanged.

3. We continue by going back up the tree as much as necessary.

Since we are only replacing elements in the tree with ones of smaller values, the resulting tree keeps the stated properties if the original one had them.

4.5 — Extraction

To retrieve an element, proceed as follows:

1. The couple (key, value) associated with the root of the tree is returned.
2. We replace it with one leaf of maximum depth of the tree.
3. If the new root has a value larger than one of its children, the couple (key, value) is exchanged with the child with smallest value.
4. We start again by going down as much as necessary.

Here again, it is easy to check that the resulting tree respects the stated properties if the starting tree also respects them.

4.6 — Complexity

The complexity of insertion and extraction operations requires to go from the root to a leaf of maximum depth in the worst case. The tree being binary, this represents $log_2(n)$ operations, where $n$ is the number of elements in the queue. We are therefore much less complex than with a naive implementation using a list (where the number of operations was at least linear in $n$).

To go beyond

• A more complete list of priority structures.

  The min-heap is only an example of particular data structures that give particular importance to some elements.

• Priority structures help developing heuristics for visiting neighbors.

  The A* algorithm is something that you may want to try in the project.