PrevNext
Not Frequent
 0/8

Priority Queues

Authors: Darren Yao, Benjamin Qi, Jeffrey Hu, Shreyas Thumathy, Nathan Gong

A data structure that supports insert, query max, and pop max.

Edit This Page

Introduction

Resources
CSA
Heaps

A priority queue (or heap) supports the following operations: insertion of elements, deletion of the element considered highest priority, and retrieval of the highest priority element, all in O(log⁡N)\mathcal{O}(\log N) time according to the number of elements in the priority queue. Priority queues are simpler and faster than sets, so you should use them instead whenever possible.

C++

C++

priority_queue<int> pq;
pq.push(7);                // [7]
pq.push(2);                // [2, 7]
pq.push(1);                // [1, 2, 7]
pq.push(5);                // [1, 2, 5, 7]
cout << pq.top() << endl;  // 7
pq.pop();                  // [1, 2, 5]
pq.pop();                  // [1, 2]
pq.push(6);                // [1, 2, 6]

Java

Java

In Java (unlike in C++), we delete and retrieve the lowest element.

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(7);                      // [7]
pq.add(2);                      // [7, 2]
pq.add(1);                      // [7, 2, 1]
pq.add(5);                      // [7, 5, 2, 1]
System.out.println(pq.peek());  // 1
pq.poll();                      // [7, 5, 2]
pq.poll();                      // [7, 5]
pq.add(6);                      // [7, 6, 5]

Python

Python

In Python (unlike in C++), we delete and retrieve the lowest element.

Note that Python's priority queue is not encapsulated; heapq operates on a provided list directly by turning it into a heap, then doing operations on the heap.

Warning!

Because of a heap's structure, printing out pq will not print out the elements in sorted order in Python; instead, it will print out the list. The comments below are a representation of what the heap contains, not what the contents of pq actually are.

import heapq


pq = []


"""
The following line is not necessary since pq starts as an empty list. However,
for lists of length greater than 1, heapify is required to turn the list into a
heap.
"""
heapq.heapify(pq)

Example

Room Allocation
CSES - Normal

Focus Problem – try your best to solve this problem before continuing!

Solution

In this problem, we're asked the minimum number of rooms needed to accommodate nn customers, who arrive and leave on set days. Let's sort each customer by their start time so that we do not have a customer arriving at say, time 3, occupying a room before a customer that arrives at time 2.

Now, we can iterate through the customers while maintaining a minimum priority queue that stores the departure times of customers we've already processed. For each customer, we check to see if the minimum element in the priority queue is less than the arrival time of the new customer.

  • If this is true, that means a room previously occupied has opened up, so we remove the minimum element from the priority queue and replace it with the new customer's departure time. The new customer will be allocated to the same room as the customer who departed.
  • Otherwise, all the rooms are full, so we need to allocate another room for the customer and add it to the priority queue.

We can determine kk by finding the maximum size the priority queue reaches as we iterate through the customers.

Implementation

Time Complexity: O(nlog⁡n)\mathcal{O}(n\log n)

C++

Implementation Note: Similarly to what was done in an earlier module, we can use greater<>() to create a min-heap instead of a max-heap.

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;


int main() {
	int N;
	cin >> N;


	vector<int> ans(N);

Java

Warning!

Input classes like Scanner and BufferedReader are too slow for this problem, so we have to use FastIO (which reads bytes directly from an input stream) instead.

import java.io.*;
import java.util.*;


public class RoomAllocation {
	public static void main(String[] args) {
		FastIO io = new FastIO();


		int n = io.nextInt();
		Customer[] customers = new Customer[n];
		for (int i = 0; i < n; i++) {

Problems

Sorted Sets

Sorted sets support all the operations of priority queues and more; however, they are rarely required for Silver and their constant factor is worse. Only one practice problem from the sorted sets module (Milk Measurement) comes from USACO Silver.

StatusSourceProblem NameDifficultyTags
Silver
Convention II
Normal
Show TagsPriority Queue, Sorting
CF
William and Robot
Normal
Show TagsPriority Queue
AC
Packing Under Range Regulations
Normal
Show TagsPriority Queue, Sorting
Silver
Why Did the Cow Cross the Road
Normal
Show TagsPriority Queue, Sorting
LC
IPO
Normal
Show TagsGreedy, Priority Queue, Sorting
CSES
Stick Division
Hard
Show TagsGreedy, Priority Queue
CF
Survival of the Weakest (easy version)
Hard
Show TagsPriority Queue, Sorting

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum
PrevNext