Priority Queue Implementation Notes

in

You might have heard of them before, but if not, let me break it down for you: a priority queue is like a regular old line at the grocery store, except instead of people just standing there waiting their turn, they’ve all got little numbers on their foreheads that determine who gets to go next based on how important their groceries are.

Now, if you’re thinking “duh, I already knew this,” then congratulations! You’re a coding genius and probably don’t need this guide anyway. But for the rest of us mere mortals, Let’s jump right into some implementation notes that might make your life easier when working with priority queues in code.

First things first: how do you actually implement one? Well, there are many ways to skin a cat (or a data structure), but we’re going to focus on the most common method: using an array and keeping track of two indices one for the front of the queue (let’s call it “front”) and another for the back (“back”).

Here’s some sample code in Python that does just that:

# This class represents a priority queue data structure
class PriorityQueue:
    # This method initializes the queue with an empty array and sets the front and back indices
    def __init__(self):
        self.items = [] # array to store items in the queue
        self.front = 0 # index for the front of the queue
        self.back = -1 # index for the back of the queue
    
    # ... other methods for enqueueing, dequeuing, etc...
    
    # This method checks if the queue is empty by comparing the length of the array to 0
    def is_empty(self):
        return len(self.items) == 0

Now, you might be wondering: “Why do we need to keep track of both the front and back indices? Can’t we just use one?” And the answer is yes… sort of. If all your items have equal priority (i.e., they’re not actually a priority queue), then using only one index would work fine. But if you want to maintain the correct order based on priority, you need both indices.

Here’s why: when we add an item with higher priority than everything currently in the queue, we need to insert it at the front (i.e., move all the items ahead of it up one position). This is called “bubbling” or “percolating,” and it can be a bit tricky to implement efficiently without using both indices.

But don’t worry we’ve got you covered! Here’s an example method for adding an item with higher priority than everything currently in the queue:

# This function adds an item to the queue with higher priority than everything currently in the queue
def enqueue(self, item):
    # Append the item to the end of the queue
    self.items.append(item)
    # Call the _percolate_up function to ensure the item is in the correct position
    self._percolate_up()


def _percolate_up(self):
    # Set the current index to the last item in the queue
    current = len(self.items) - 1
    
    # Loop until the current index is greater than the front index and the parent item is less than the current item
    while current > self.front and self.items[self._parent(current)] < self.items[current]:
        # Swap the parent item with the current item
        self.items[self._parent(current)], self.items[current] = self.items[current], self.items[self._parent(current)]
        
        # Update the current index to the parent index
        current = self._parent(current)

# This function calculates the parent index of a given index
def _parent(self, index):
    # The parent index is calculated by dividing the given index by 2 and rounding down
    return index // 2

This method appends the new item to the end of the array, and then calls a helper function called `_percolate_up()`. This function starts at the newly added item (which is now at the back), and compares it with its parent. If the parent has lower priority than the child, we swap them. We keep doing this until either we reach the front of the queue or we find an item that has higher priority than our new item.

Now, you might be wondering: “Why do we need to compare against the parent’s priority instead of just comparing against all items ahead of us?” And again, the answer is efficiency by only comparing with parents, we can avoid unnecessary comparisons and swaps that would slow down our code.

But don’t worry if you still have questions or concerns about priority queues (or any other data structure) there are plenty of resources out there to help you learn more! Just remember: coding is like a grocery store line, but with numbers on your forehead instead of groceries in your cart.

SICORPS