Priority Queues

Priority queues are among the most useful of all collections.

The Basics

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.

Operations

Examples

Representations

Unsorted Array

Unsorted Linked List

Sorted Array

Sorted Linked List

Heap

What’s a heap, anyway?

Heaps

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.

heap1.png

Peek

Therefore, the smallest element, the one with the highest priority, is always on top, so peek() is $\Theta(1)$.

Add

To insert, add the new item to the last slot in the array and sift it up.

heapinsert.png

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.

Remove

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.

heapdelete.png

It should be pretty easy to prove that deletion is done in logarithmic time.

Heapify

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);
}
Exercise: Show this in action on the following array [33 41 7 15 55 86 28 22 94 9 11 10 8 99 16 27 51 83 2]

More on Heaps

By the way...

Exercise: Write a survey article on the different kinds of heaps.

Priority Queues in Java

There’s already a PriorityQueue class in the Java Core API. It implements the Queue interface, and has the following characteristics:

There’s also the PriorityBlockingQueue class.

Implementation From Scratch

We’re going to write a priority 1ueue class from scratch because:

We’ll develop this during class

Unit Testing

Here are some of the things we need to test:

Here is a rough unit test:

We’ll develop this during class

Priority Queues in Ruby

Here’s a binary heap-based, non-thread-safe, non-blocking, implementation in Ruby:

priorityqueue.rb
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
Exercise: Add methods 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.

priorityqueuetest.rb
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