Today I’ll be looking at Priority Queues! It’s a very useful data structure (one of my favorites) used to hold elements in a order based on some ranking of those elements. After explaining what they are and how to use them, I’ll walkthrough how to solve this problem — Maximum Number of Eaten Apples.
Priority Queues
What are they?
A data structure that follows the FIFO (first-in-first-out) nature of a queue while giving precedence to elements with higher priorities. Here’s an example in pseudocode:
## PSEUDOCODE ##priority_queue = new PriorityQueue()# entries: [ priority, element ]priority_queue.add( [ #2 , 5 ] )
priority_queue.add( [ #1 , 2 ] )
priority_queue.add( [ #1 , 4 ] )priority_queue.pop() # => 2
priority_queue.pop() # => 4
priority_queue.pop() # => 5
As you can see, the entry with the higher priority — in this case, #1 is the highest priority — is popped before the entry with priority #2 even though it was added after. Then, just as a normal queue, it pops the element 2 before the element 4 because it was added in first.
How to implement them?
On way to implement them is to use a heap. You can use the priority as the key for adding to the heap so that it will pop off the element with the highest priority.
In python, you can use the heapq library to implement a priority queue. All you need to do is pass in entries as tuples with the priority value as the first element. Here’s an example:
heap = []
heapq.heappush(heap, (4 , 2) )
heapq.heappush(heap, (1 , 3) )heapq.heappop() # => (1 , 3)
heapq.heappop() # => (4 , 2)
Remember that heapq creates a min-heap. If you want to use a max-heap for your priority queue, then you can negate the priority value when pushing into the queue.
When to use?
- Need to maintain a list of “next-bests” or “next-greatest” or “next-up” elements to pop from.
- Tracking end-times or expiration dates
Additional Resources
WilliamFiset: Priority Queue Introduction
Python docs: Heap queue algorithms (Section on Priority Queues)
Maximum Number of Eaten Apples
Link to the problem: Maximum Number of Eaten Apples
Problem Summary
You are given two arrays: 1) an array apples that holds the number of apples grown on day i and 2) an array days that holds the number of days it takes for apples grown on day i to expire. If you can only eat one apple a day, what is the maximum number of apples you can eat?
Problem Exploration
Here are my initial thoughts:
- I will always eat an apple if any are available so this isn’t a problem of choice.
- I will always eat the apple that is going to expire first because I will be more likely to eat the other apples on another day.
#1 — This eliminates some other algorithms to use that involve making choices at each day.
#2 — This is the key to solving the problem. This logic is the how you would treat your own fridge: you always eat the food that will expire first because you want to minimize the food that gets wasted. In this case, we need know which apples are “next-to-expire” so we can pick the best apple to eat.
Any time you need a “next-something”, you can think about using a priority queue. For this problem, we can use the expiration date of the apple as the key and store the number of apples expiring on that day as the value. Then on each day, we take one apple from the group of apples that will expire first until we aren’t growing any more apples and we run out of apples to eat.
Algorithm
- We instantiate our priority queue, a count of apples —
num_apples— and a counter —i— for the day we are on. - On each day, get the number of apples —
apples[i]— and use the expiration day —i + days[i]— as the priority key to push to our queue. - If there are apples available in the queue, pop off the our queue, add to
num_applesand then push back to queue if there are apples left in that group. - Go until we stop growing new apples —
i >= len(apples)— and we run out of apples — our priority queue is empty.
Time and Space Complexity
Time: O(n log(n))
At each day — O(n) — a new entry is added to the queue — O(log n) — so the final time complexity is O(n log n).
Space: O(n)
Maximum size of the heap is n elements so final space complexity is O(n).
Code
Finally, here’s the code:
Conclusion
Priority queues — and heaps — are among my favorite data structures to use because they can help solve tons of real world problems. Be sure to keep them in mind when solving your next algorithms!