A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority. The basic operations are:
add(x)
: add item $x$
remove
: remove the highest priority item
peek
: return the highest priority item (without removing it)
size
: return the number of items in the priority queue
isEmpty
: return whether the priority queue has no items
You will find priority queues used to model:
For an unsorted array:
For an unsorted linked list:
For a sorted array:
For a sorted linked list:
For the amazing heap:
What’s a heap, anyway?
A heap is a complete binary tree in which the value of a node is less than all the values in its subtrees. By convention, the smallest element is the one with the highest priority.
Therefore, the smallest element, the one with the highest priority, is always on top, so peek()
is $\Theta(1)$.
To insert, add the new item to the last slot in the array and sift it up.
Since the tree is complete, it has minimum height, and the worst case number of moves up is logarithmic in the heap size. So cool.
To remove, return the value at the top, replace the top node with the value of the last slot, destroy the last slot, and sift down.
It should be pretty easy to prove that deletion is done in logarithmic time.
A cool operation you’ll sometimes see is called heapify — it turns a random array into a heap:
for (int i = a.length/2; i >= 0; i--) { siftdown(i); }
By the way:
There’s already a PriorityQueue class in the Java Core API. It implements the Queue interface, and has the following characteristics:
add()
, offer()
, poll()
,
and remove()
run in $\Theta(\log n)$ time.
peek()
, element()
, and size()
run in $\Theta(1)$ time.
remove(Object)
and
contains(Object)
run in Θ(n) time.
There’s also the PriorityBlockingQueue class.
We’re going to write a priority queue class from scratch because:
We’ll develop this during class
Here are some of the things we need to test:
NoSuchElementException
NoSuchElementException
Here is a rough unit test:
We’ll develop this during class
Here’s a binary heap-based, non-thread-safe, non-blocking, implementation in Ruby:
class PriorityQueue def initialize @heap = [] end def add!(x) @heap << x sift_up(@heap.length - 1) self end def peek @heap[0] end def remove!() raise RuntimeError, "Empty Queue" if @heap.length == 0 if @heap.length == 1 @heap = [] else @heap[0] = @heap.pop sift_down(0) end self end def to_s @heap.to_s end private # Sift up the element at index i def sift_up(i) parent = (i - 1) / 2 if parent >= 0 and @heap[parent] > @heap[i] @heap[parent], @heap[i] = @heap[i], @heap[parent] sift_up(parent) end end # Sift down the element at index i def sift_down(i) child = (i * 2) + 1 return if child >= @heap.length child += 1 if child + 1 < @heap.length and @heap[child] > @heap[child+1] if @heap[i] > @heap[child] @heap[child], @heap[i] = @heap[i], @heap[child] sift_down(child) end end end
heapify
, empty?
, and size
.
And here’s a starter unit test (it only tests that add and remove work; it does not test any low-level details of sifting.
require 'minitest/autorun' require './priorityqueue.rb' class PriorityQueueTest < MiniTest::Test def test_new q = PriorityQueue.new assert_equal(q.peek, nil) assert_raises(RuntimeError) {q.remove!} end # Add 1..100 in at random, they should come out in order def test_adds_and_removes q = PriorityQueue.new (1..100).to_a.sort_by {rand}.each {|x| q.add!(x)} 1.upto(100) do |i| assert_equal(q.peek, i) q.remove! end end end
We’ve covered: