Heaps
Continuing our material on advanced data structures, we will learn about heaps in this lesson.
A heap is a datastructure to hold elements. A priority is associated with every element in the heap, elements with higher priority will be the first returned.
An example might be your tasks for today. You start your morning with three tasks: grocery shopping, go for a walk, pick up room, all with the same priority. Later in the day your friend asks you to pick them up as their car suddenly failed. This is a high priority item, and so it moves to the front of the heap.
When we write our code for a heap, we need to make sure that depending on an elements priority, it is positioned before elements with lower priority, and after elements of the same or higher priority.
There are a few underlying data structures we can use for this, lists, linked lists, or trees being most common. Most implementations will use trees due to their better performance, however to keep things simple, we will use lists.
We start by making an object to store an item's content and its priority. Different implementations of heaps will use the content itself as priority, or to use a tuple and indexing to get the content and priority. We choose this method for greater flexibility and readibility.
Next we build our heap. The methods for string formatting,
getting an element, popping, and checking if empty are very similar to
stacks and heaps. What's different is how we push.
Notice how we can't just push to either the front or back of our data structure. We need to somehow find what index the element should be inserted before we can actually do so. Since we are using lists, we need to iterate through the heap each time to find this position. Since we've built a max heap, we need to find the first element that has a lower priority than the item to be inserted. If there is no element smaller, or the heap is empty, we should insert at the end of the heap.
To peek or pop, we assume the element at the
beginning of the heap is the highest priority item.
Notice how the elements pushed to the heap are not in the same order as printed, this is because higher priority elements move to the front. Additionally we make an assumption that elements of the same priority should be presented in the order they were pushed.
With a few assumptions, it's possible to use an array as a stack, queue, or heap, pretty nifty!
Practice Question
Alter the following code to change it from a Max Heap to a Min Heap. What this means is elements with a lower value priority should have 'higher' priority and be positioned at the front of the heap.