UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 13.2 Free with a free account
Building a Priority Queue in Java, Step by Step
Data Structures and Algorithms · Chapter 13: Priority Queues and HeapsSection 13.2 · lesson 53 of 8712 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Heaps: A Complete Binary Tree That Keeps Priority Order →← The Priority Queue: Why Some Lines Need to PrioritizeNext lesson: Heaps: A Complete Binary Tree That Keeps Priority Order →
In this lesson
Unsorted and sorted list priority queues, comparators and Java's PriorityQueue.
- Define a priority queue interface whose entries pair keys with values
- Implement unsorted-list and sorted-list priority queues using a comparator
- Analyze and measure why both list versions cost order n squared overall
- Use Java's PriorityQueue with tie-breakers and for keeping the top k items
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,659 words). Read along, or search it.
Opening Question
Building a Queue That Serves Small Keys
A priority queue always serves the most important entry first, whatever order the entries arrived in. But how would you build one? Here, a smaller key means a higher priority, so key one is served before key five. We'll write one interface, then two simple versions behind it: an unsorted list, and a sorted list. Then we'll measure what each one really costs, and finish with Java's ready-made PriorityQueue.
Data Model
Entries Pair a Key With a Value
Real waiting lines carry two things: what's being waited for, and how urgent it is. So the queue stores entries. Each entry pairs a key, the priority, with a value, the payload, such as a task name. The queue looks only at keys to decide who goes first. And to string prints an entry as key, colon, value.
Interface
The PQueue Operations
The interface says what the queue can do, and nothing yet about how. Insert adds an entry. Min returns the entry with the smallest key, and leaves it in place. Remove min takes it out. Size and is empty work as usual. For now, an empty queue answers null, a temporary rule that keeps the code simple. The type parameters K and V let one interface serve integer priorities with string tasks, or dates with reports. And code that uses only PQueue can swap in a faster version later.
Comparators
Comparing Keys Through a Comparator
To find the smallest key, the queue must compare keys. Keys might be words, dates or objects, where less-than doesn't exist. So every decision goes through a comparator, whose compare method returns negative when a comes first, zero for a tie, and positive when a comes after. This program sorts five words four ways. By length is a class that implements Comparator. The arrow form, a lambda, is shorthand for the same thing. The two length orders match, and pear stays before kiwi: both have four letters, and the sort keeps tied items in their original order. Reverse order flips the natural order. That's how a largest-first queue comes from smallest-first code: only the comparator changes, never the queue.
Common Mistake
Subtraction Overflows in Compare
One warning. Never write compare as a subtraction. For extreme values, a minus b overflows. The smallest int, minus one, comes out as the largest int: a huge positive number, claiming the smallest value comes after one. Integer compare always gives the right sign, minus one here. Use it for numbers.
Version One
An Unsorted List Scans on Removal
Version one keeps the entries in a list, in whatever order they arrive. Inserting is easy: add the new entry at the end. That's constant work. The price comes when the smallest entry is wanted. Nothing is in order, so index of min must look at every entry. It replaces its best position only for a strictly smaller key. So among tied keys, the earliest arrival is kept, and equal keys leave in arrival order. Min and remove min both call index of min, so each of them examines the whole list.
Version Two
A Sorted List With the Minimum Last
Version two does the work at insertion time instead, keeping the entries sorted, so the smallest is always at a known position. A small trick makes removal cheap. The list is sorted with the largest key first, so the smallest is at the end, and removing the last item needs no shifting. Insertion walks from the front, skipping every entry with a bigger key, then places the new entry in the gap, shifting the rest along. The test is strictly bigger. So a new entry goes before entries with an equal key. Earlier equal keys stay nearer the end, and leave first, just as in version one.
Worked Example
Five Tasks Through Both Versions
Now both versions run the same drill. Five tasks go in: report with key three, outage one, email two, desk five, and client, also with key one. The unsorted list stores them in arrival order. Its removal order is outage before client, a tie on key one settled by arrival, then two, three and five. The sorted list stores the largest first, but its minimum and its removal order are identical. And remove min on an empty queue gives null, in both.
Quick Check
Storage Order in a Sorted List
Quick check. A sorted-list queue gets four a, two b, four c, and one d, in that order. Then it's printed. How are the entries stored? Pause and predict. It prints four c, four a, two b, one d. The largest keys come first, and the smallest, one d, sits at the end. When four c arrived, the walk stopped at four a, because four isn't strictly bigger than four. So four c went in front of it. Four a before four c would need a bigger-or-equal test. And one d first is ascending order, but this list keeps its minimum at the end.
Cost Analysis
Moving Work Between Operations
Now count. Let n be the number of entries. The unsorted list inserts in constant time, but min and remove min are order n. The sorted list is the mirror image: insert is order n, and min and remove min are constant. Over a whole life of n inserts and n removals, each list adds up to order n squared. The work was moved from one operation to the other, not removed. Java's PriorityQueue is order log n for insert and remove, constant for a look at the minimum, and n log n for the whole run.
Measurement Tool
A Comparator That Counts
A table of formulas is easy to doubt, so let's measure it. This Counting class wraps another comparator. Every comparison passes through its compare method, which adds one to a count, and then asks the wrapped comparator for the answer.
Measured Results
Doubling n Quadruples Comparisons
The experiment inserts n random keys and then removes them all, for the two lists and for Java's own queue, at five sizes. Doubling n from eight hundred to sixteen hundred roughly quadruples the comparisons for both lists. That's the signature of n squared. The unsorted count is exactly n times n minus one, over two: for two thousand entries, one million, nine hundred ninety-nine thousand. The sorted list needs about half as many, because a new key walks past half the entries on average. But half of n squared still grows like n squared. Java's column grows far more slowly: fewer than forty thousand comparisons at two thousand entries.
Measured Results
Where Each Version Does Its Work
Splitting the two phases, for a thousand entries, shows where the work happens. The unsorted list does all its work during the removals: four hundred ninety-nine thousand, five hundred comparisons, and none for the inserts. The sorted list does all its work during the inserts, and none during the removals. They're mirror images.
Quick Check
Many Inserts, Few Removals
Quick check. A logging system performs half a million inserts, and between them, only twenty removals. Which version should it use? Pause, and decide. The unsorted list. Each of its inserts costs constant time, so half a million of them are cheap, and twenty order-n removals are affordable. The sorted list would pay order n on every one of the half a million inserts. And n squared describes n inserts with n removals. Here the removals are rare, so the totals are very different.
Java Library
Offer, Peek and Poll
In real programs, you rarely write one yourself. Java's PriorityQueue keeps the same promises, with different names: offer to insert, peek to look, and poll to remove. Thirty, ten and twenty go in. Peek shows ten, and the polls return ten, twenty, thirty. Poll on an empty queue returns null, just like our version. Passing reverse order to the constructor gives largest first: nine, then seven. And our entries fit too, with a comparator that looks only at the key: outage, email, report.
Fairness
Breaking Ties With Arrival Numbers
When two entries have equal keys, Java's PriorityQueue makes no promise about which leaves first. Seven jobs, a to g, all get priority one. The plain queue compares the key alone. The fair queue breaks ties with an arrival number. With the key alone, they come out a, g, f, e, d, c, b: not arrival order, and not something to depend on. With the arrival number compared second, the order is exactly a to g. When fairness among equal priorities matters, store a sequence number, and compare it second.
Application
Keeping the Three Largest
A priority queue can also keep only the best few items from a very long stream. Say we want the three largest numbers. Use the default smallest-first queue, and whenever it grows beyond three, discard its smallest entry. At most three numbers are ever stored, and what remains are the three largest: forty-two, sixty-one, ninety-nine. The direction is easy to get backwards. To keep the largest, the entry you discard is the smallest of those kept, so the queue must be smallest-first.
Limits
When Neither List Is Good Enough
Both list versions are correct, short and easy to read. For a few dozen entries, either is fine. With many inserts and very few removals, the unsorted list wins. With entries loaded once, then mostly removed, the sorted list wins. But a scheduler, an event simulation or a route search mixes thousands of inserts with thousands of removals. It needs both operations cheap at the same time. A better structure reaches order log n for both. It isn't a list at all. It keeps entries only partly ordered, which is enough to find the smallest, and cheaper to maintain than a full sort.
Common Mistakes
Printing, Ties, Contains and Null
A few more mistakes to avoid. Printing a PriorityQueue to check its order: the text isn't sorted. Only the poll order is guaranteed. Using the wrong comparison in the sorted insert sends equal keys out in the wrong order. Decide the tie rule first, then pick the operator. Calling contains, or remove of an object, on a PriorityQueue scans every entry. And never insert null: that's a failure at run time.
Key Takeaways
Two Lists and Java's Queue Compared
To sum up. A priority queue stores entries, each pairing a key with a value, and a comparator decides what smallest means. The unsorted list inserts in constant time, but scans to remove. The sorted list is the mirror image. Either way, n inserts and n removals cost order n squared, as the counts showed. Java's PriorityQueue stays near n log n. And ties have no promised order: add an arrival number when fairness matters.
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Building a Priority Queue in Java, Step by Step
What are the costs of an unsorted list versus a sorted list priority queue?
When should you use an unsorted list instead of a sorted list for a priority queue?
How do you keep the k largest numbers from a stream with a priority queue?
How do you make Java's PriorityQueue break ties in arrival order?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →