This lesson's interactive features are locked, please to keep using them

Heaps

Click to play video

Before we can improve our priority queue, we need to learn about heaps. A heap data structure is optimized for retrieving the largest or smallest element in a collection.

In the case of a max heap, it's a balanced tree where the value of each node is always greater than or equal to the value of its children. A min heap is the opposite, where the value of each node is less than or equal to the value of its children. This property is called the heap property.

That means the root node is either the largest or smallest element in the tree, so finding the min or max (depending on the type of heap) is a blazingly fast operation.

Min heap: the root node is the smallest element
Max heap: the root node is the largest element

Min Heap Visualization

A list can be used to represent a heap. This may seem tricky, but by doing some math with the indexes in the list, we can keep track of the tree structure.

The min heap above can be represented like so:

[8, 10, 9, 21, 31, 27, 12, 58, 99, 42, 33, 39]

Assignment

Our min heap will need several methods. For now, complete the push and bubble_up methods.

self.elements is a list of tuples where the first index is the priority (a number) and the second index is the value of the element, in our case a street name.

push(self, priority: int, value: str) -> None

Append a new tuple representing the input to self.elements.
Call self.bubble_up, passing in the index of the element you just appended.

bubble_up(self, index: int) -> None

If the given index is the root, you're done.
Calculate the index of the parent node of the given index. Try to figure out the formula for this based on the visualization and the list above.
If the parent's priority is greater than the child's priority:
1. Swap the parent and child.
2. Recursively bubble_up the parent's index.

Tip

The formula for finding the index of the parent node:

parent_index = (index - 1) // 2