PrevNext
Not Frequent
 0/8

Priority Queues

Authors: Darren Yao, Benjamin Qi, Jeffrey Hu

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!

View Internal Solution

Solution

Problems

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