The Priority Queue: Why Some Lines Need to Prioritize

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 13.1 Free with a free account

The Priority Queue: Why Some Lines Need to Prioritize

Data Structures and Algorithms · Chapter 13: Priority Queues and HeapsSection 13.1 · lesson 52 of 8710 min · free with a free account

← Choosing the Right Tree: Layouts and ApplicationsNext lesson: Building a Priority Queue in Java, Step by Step →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Serving the most urgent element first instead of the earliest.

  • Distinguish a priority queue from FIFO queues and stacks
  • Use Java's PriorityQueue methods offer, poll, peek and remove correctly
  • Build min and max priority queues with comparators and tie-breakers
  • Recognize mistakes such as trusting printed order or changing priorities in place

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,322 words). Read along, or search it.

Opening Question

Who Matters Most Right Now

A hospital emergency room doesn't treat patients strictly in the order they arrive. A patient with a sprained ankle who came in first waits, while a patient with chest pain is seen at once. That waiting line isn't asking who has waited longest. It's asking who matters most, right now. Programs face the same situation: tasks compete for a processor, simulated events must happen in time order, and requests differ in urgency.

Limits of FIFO

A Plain Queue Ignores Urgency

A plain queue serves elements in the order they arrived. That's right for a bakery counter, where fairness means first come, first served. But a queue never looks at what an element is, so it can't tell an emergency from a routine visit. Picture eight patients, numbered by arrival, each with a severity from one, the most urgent, to five. Fay, with severity one, is the most urgent. She arrived sixth, so a first-in, first-out queue serves her sixth, after five less urgent patients. A program could search the queue before every removal, or keep a list sorted at all times. Both work, but each loads extra work onto one operation.

Abstract Data Type

Insert, Remove Min and Peek

A stack serves the element added last. A queue serves the element added first. A priority queue serves the element with the best priority, whenever it was added. Like a stack, it's defined by what its operations do, not by how it stores data. Insert adds an element with its priority. In Java, that's add or offer, and null is rejected. Remove min takes out the best element. Java's poll returns null on an empty queue, while remove throws. Peek returns the best without removing it: peek gives null when empty, and element throws. Is empty and size work as usual.

Worked Example

Mixing Insertions and Removals

Insertions and removals can be mixed freely. This program adds fifty and twenty, then polls. It gets twenty, the smaller of the two. Then it adds ten and sixty, and polls three more times: ten, fifty, sixty. Ten was added after fifty, but left before it. Each removal returns the best element inside at that moment, not the newest or the oldest.

Min Versus Max

Defining Which Element Is Best

Best has to be defined. In a min-priority queue, the smallest value is best. In a max-priority queue, the largest is. Severity one is most urgent, so triage needs min priority. A score or a bid, where bigger is better, needs max. A time stamp, where earlier comes first, needs min. Java's PriorityQueue is a min-priority queue by default. For max priority, pass a comparator that reverses the order. Both queues get forty, ten, thirty, twenty. Peek shows ten and forty, and peeking leaves the size at four. Emptying them returns sorted order: ascending for min, descending for max.

Quick Check

Poll, Add One, Poll Twice

Quick check. A default PriorityQueue gets eight, three and five. The program polls once, adds one, and then polls twice more. Which three values come out, in order? Pause and predict. It prints three, one, five. The first poll takes three, the smallest of eight, three and five. Then one arrives, and it's now the best inside, so the next poll returns it. Five comes after that. Three, five, eight ignores the one added later. And one, three, five would mean one was already inside at the first poll.

Worked Example

Ordering Patients With a Comparator

Real elements are rarely bare numbers. A patient has a name, a severity and an arrival number, and only some of these decide the order. Here, Patient is a Java record: a compact way to declare a type that only holds data. The comparator orders by severity first, and breaks ties with the arrival number. The eight patients go into a first-in, first-out queue and into the priority queue. The first line is arrival order. The second is triage order, and Fay moved from sixth to first. There's a price. Eli, with severity five, moved from fifth to eighth. A steady stream of urgent arrivals could keep a low-priority element waiting a very long time. That's why real systems often add a rule, such as raising the priority of elements that have waited long enough.

Tie-Breakers

Equal Severities Need a Tie-Breaker

Ana and Dee both have severity three. With the arrival tie-breaker, Ana, who came first, goes first. The third queue compares severity alone. In this run, Dee came out before Ana, and Gus before Cy. Without a tie-breaker, the order of equal elements isn't promised, and another Java version might differ. When equal priorities must be served fairly, add a tie-breaker.

Applications

Triage, Scheduling and Simulation

Three typical uses all rely on min priority. Hospital triage orders patients by severity. An operating system scheduler orders tasks by a priority number. And an event simulation orders future events by the time they happen.

Application

Scheduling Ready Tasks

A computer has more tasks ready than it can run at once. A scheduler keeps the ready tasks in a priority queue, and always runs the most important one next. In this sketch, a smaller number means a more important task. Some systems use the opposite convention, so always check the direction. The keyboard task runs first, then video, disk flush, and backup. Real schedulers are more elaborate, but the core question, which waiting task is next, is the one a priority queue answers.

Application

Event Simulation in Time Order

A simulation keeps a clock and a set of future events. Events are scheduled in any order, but must be handled in time order. A min-priority queue ordered by time does exactly that: remove the earliest event, set the clock to its time, handle it, and repeat. Handling an event can schedule new ones. When customer A arrives, the program schedules customer A leaves at time twenty-five. That event didn't exist when the run began. It was added while the queue was in use, and it still came out in the right place.

Quick Check

Serving the Highest Bid

Quick check. An auction program must always serve the highest bid first. It puts bids of seventy-two, ninety-five and eighty-eight into a new, default PriorityQueue. What does its first poll return? Pause, and decide. It returns seventy-two. A default PriorityQueue is a min-priority queue, so it hands out the smallest bid, silently. Ninety-five is what the auction wanted. It needs a max-priority queue, built with Comparator dot reverse order. And eighty-eight would come out of neither queue first: it's not the smallest or the largest.

Common Mistakes

Printed Order and Changed Priorities

A few mistakes are worth seeing run. First, adding fifty, forty, thirty, twenty, ten and printing the queue gives ten, twenty, forty, fifty, thirty. That's not sorted. Only poll is guaranteed to give the best element. Never read the printed form as an order. Second, an alert's priority changes from five to one after it's inserted. The queue doesn't notice, and peek still returns the email. The fix is to remove the element, change it, and add it again. Then the alert comes first. And an empty queue: poll and peek return null, while remove throws a no such element exception. Adding null throws a null pointer exception.

Looking Ahead

Two Simple Designs

So far, the priority queue has been a black box that keeps its promise: the best element comes out next. Two simple designs come to mind. An unsorted list, searched on every removal. Or a sorted list, kept in order on every insertion. Each is easy to write, and each makes one of the two main operations do much more work than the other.

Key Takeaways

Best Priority Comes Out Next

To sum up. A priority queue removes the element with the best priority next, whenever it was added. A FIFO queue looks only at arrival. Java's PriorityQueue is min-priority by default. Comparator dot reverse order gives max priority. A comparator picks the fields that decide the order. Add a tie-breaker when equal priorities must be fair. And the queue doesn't re-sort an element whose priority changes. Remove it, and add it again.

Think About It

A Low-Priority Patient Waits

Something to think about. A hospital orders patients by severity only. A severity-five patient arrives, and for hours a steady stream of severity one and two patients keeps coming. What happens to the first patient? Would a FIFO queue have the same problem, and what rule could protect low-priority patients?

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

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

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 UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks 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 The Priority Queue: Why Some Lines Need to Prioritize

What is a priority queue and how is it different from a regular queue?
A priority queue removes the element with the best priority next, no matter when it was added, while a regular FIFO queue serves elements strictly in arrival order. In a min-priority queue the smallest value is best; in a max-priority queue the largest is. For example, an emergency room sees the most severe patient first even if that patient arrived sixth, which a FIFO queue cannot do.
How do you make a max priority queue in Java?
Pass a reversing comparator to the constructor, as in PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()). Java's PriorityQueue is a min-priority queue by default, so without the comparator, poll returns the smallest value. For bids of 72, 95 and 88, a default queue's first poll returns 72, while the reversed queue returns 95. Both classes live in java.util.
What is the difference between poll and remove in Java's PriorityQueue?
Both take out the best element, but they differ on an empty queue: poll returns null, while remove throws a NoSuchElementException. The look-only pair works the same way: peek returns null when the queue is empty, and element throws. Separately, adding null with add or offer throws a NullPointerException, because PriorityQueue does not accept null elements.
Why does a PriorityQueue not reorder an element after its priority changes?
The queue places an element when it is added and does not watch the element's fields afterward, so changing a priority in place can leave the element in the wrong spot. If an alert's priority changes from 5 to 1 after insertion, peek can still return a different element. The fix is to remove the element, change it, and add it again, so the queue places it correctly.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

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.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →