Priority Queues

Updated: 27 March 2024

APIs and Elementary Implementations

A variant of sorting that generalizes the idea to create a data structure that can be used for more general problems

Priority Queue

Different types of collections:

• Stack: remove the most recently added
• Queue: remove the item least recently added
• Randomized Queue: remove a random item
• Priority Queue: remove the largest (or smallest) item

API

Similar to Stack/Queue but we want to have generic items that are comparable:

The API definition looks like so:

1
export interface PriorityQueue<T> {
2
  insert(value: T): void
3
  delMax(): T
4

5
  empty(): boolean
6
  size(): number
7
}

There are lots of different algorithms for implementing the priority queue

• Event driven simulation
• Numerical computation
• Data compression
• Graph searching
• Number theory
• AI
• Statistics
• Operating systems
• Discrete filtering
• Spam filtering

Generalizes the idea of a stack, queue, and randomized queue

Usecase

Say we want to store the largest M (large) items in a stream of N (huge) items. We can only afford to store M items, e.g. due to memory constraints

Ther are some approaches we can use:

Elementary Implementation

We could implement this simply using two methods:

• Keep an unordered list, we can add every new item to the end, to remove the max we scan through and remove it from the list
• Keep an ordered list, we can put the new item in it’s new location and move the larger items, to remove we can just take the last item

Below is a simple example of an unordered elementary implementation

1
import { Comparison, type Compare } from '../sorting/definition'
2
import type { PriorityQueue } from './definition'
3

4
export class UnorderedMaxPQ<T> implements PriorityQueue<T> {
5
  private N = 0
6
  private pq: T[]
7

8
  constructor(private compare: Compare<T>, capacity: number = 10) {
9
    this.pq = new Array(capacity)
10
  }
11

12
  private swap(i: number, j: number) {
13
    const replaced = this.pq[i]
14
    this.pq[i] = this.pq[j]
15
    this.pq[j] = replaced
16
  }
17

18
  public insert(value: T): void {
19
    this.pq[this.N++] = value
20
  }
21

22
  public delMax(): T {
23
    let m = 0
24
    for (let i = 0; i < this.N; i++) if (this.less(m, i)) m = i
25

26
    this.swap(m, this.N)
27
    return this.pq[this.N--]
28
  }
29

30
  public size(): number {
31
    return this.N
32
  }
33

34
  public empty(): boolean {
35
    return this.N === 0
36
  }
37

38
  private less(i: number, j: number) {
39
    return this.compare(this.pq[i], this.pq[j]) === Comparison.Less
40
  }
41
}

The above version uses a capacity but we could also define this as some other kind of array implementation

Investigating the two above options we have the following time complexities:

The two options to us are not great since they are at N for either one of the cases we need to be efficient in

Our goal is to define a O(log N) solution for the insert and delete operations

Binary Heap

• Binary tree - Empty or notde with links to left and right binary trees
• Complete binary tree - perfectly balanced except for the bottom level

For a complete binary tree, the height of a tree with N nodes is the nearest integer less than floor(lg N) since the height only increases when N is a power of 2

The priority queue can be implemented using a binary tree

Array Representation

The Binary heap is a representation of a heap-ordered complete binary tree

A heap-ordered binary tree has:

• Keys in nodes
• Parent’s key no smaller than children’s keys

Array representation:

• Indices start at 1 (this simplifies some further computation)
• Take nodes in level order
• No explicit links needed

By representing a binary tree as an array we can associate each index based on it’s position in the tree

• Largest key is a[1] which is the root of the binary tree
• Can use indices to move through the structure:
  • Parent of a node at k is at k/2
  • Children of node at k are at 2k and 2k+1

Promotion in a Heap

Given a scenario that a child’s key becomes larger than it’s parent key we need to do the following to fix the tree:

1. Exchange then key in the child with the key in the parent
2. Repeat until heap order is restored

We refer to this operation as the swim operation as the item swims up the tree and looks like so:

1
import { Comparison, type Compare } from '../sorting/definition'
2
import { swap } from '../sorting/swap'
3

4
/**
5
 * Swims the value at the index `k` up the binary tree inplace
6
 *
7
 * @param array A 1-based array representing a complete binary tree with
8
 * position `k` out of order
9
 *
10
 * @param k The index of the item that is out of order
11
 */
12
export const swim = <T>(compare: Compare<T>, array: T[], k: number) => {
13
  const less = (i: number, j: number) =>
14
    compare(array[i], array[j]) === Comparison.Less
15

16
  const p = (i: number) => Math.floor(i / 2)
17

18
  while (k > 1 && less(p(k), k)) {
19
    swap(array, k, p(k))
20
    k = p(k)
21
  }
22
}

Using this means that we can insert as follows:

1. Insert node at end of array
2. Swim the node up to it’s correct position

This implementation has the complexity of 1 + lg N since the swim operation is at most lg N

Demotion in a Heap

Given the scenario where a parent’s key becomes smaller than one or both of its children

To restore the state from this position:

1. Exchange key in parent with key in larger child
2. Repeat until heap order is restored

This is referred to as the sink operation which we can implement as such:

1
import { Comparison, type Compare } from '../sorting/definition'
2
import { swap } from '../sorting/swap'
3

4
/**
5
 * Sinks the value at the index `k` down a binary tree as far as needed
6
 * prefering to promote the child with the higher value
7
 *
8
 * @param array A 1-based array representing a complete binary tree with
9
 * position `k` out of order
10
 *
11
 * @param N Number of items in the heap (length -1)
12
 *
13
 * @param k The index of the item that is out of order
14
 */
15
export const sink = <T>(
16
  compare: Compare<T>,
17
  array: T[],
18
  N: number,
19
  k: number
20
) => {
21
  const less = (i: number, j: number) =>
22
    compare(array[i], array[j]) === Comparison.Less
23

24
  while (2 * k <= N) {
25
    // First child index
26
    let j = 2 * k
27

28
    // Make sure we are still in the heap and increase j if right child is larger
29
    if (j < N && less(j, j + 1)) j++
30

31
    // If k is greater than the child we are comparing then we are done
32
    if (!less(k, j)) break
33

34
    // Swap k with the larger child j
35
    swap(array, k, j)
36

37
    // Assign k to the value it was swapped to j
38
    k = j
39
  }
40
}

Delete the Maximum in a Heap

To delete the maximum in a heap we need to do the following:

1. Exchange the root with the node at the end
2. Remove the end node
3. Sink down root to restore order

In code this will look something like:

1
max =  pq[1]
2
swap(1, N--)
3
sink(1)
4

5
pq[N+1] = null // prevent loitering reference
6

7
return max

Complete Implementation

We can combine the above sink and swim functions into the final implementation

1
import { Comparison, type Compare } from '../sorting/definition'
2
import { sink } from './binary-heap-sink'
3
import { swim } from './binary-heap-swim'
4
import type { PriorityQueue } from './definition'
5

6
export class BinaryHeapPQ<T> implements PriorityQueue<T> {
7
  private N = 0
8
  private pq: Array<T>
9

10
  constructor(private compare: Compare<T>, capacity: number = 10) {
11
    this.pq = new Array<T>(capacity + 1)
12
  }
13

14
  private swap(i: number, j: number) {
15
    const replaced = this.pq[i]
16
    this.pq[i] = this.pq[j]
17
    this.pq[j] = replaced
18
  }
19

20
  private swim(k: number) {
21
    swim(this.compare, this.pq, k)
22
  }
23

24
  private sink(k: number) {
25
    sink(this.compare, this.pq, this.N, k)
26
  }
27

28
  public insert(value: T): void {
29
    this.pq[++this.N] = value
30
    this.swim(this.N)
31
  }
32

33
  public delMax(): T {
34
    const max = this.pq[1]
35
    this.swap(1, this.N--)
36

37
    this.sink(1)
38

39
    // Remove the reference to the element
40
    delete this.pq[this.N + 1]
41

42
    return max
43
  }
44

45
  public size(): number {
46
    return this.N
47
  }
48

49
  public empty(): boolean {
50
    return this.N === 0
51
  }
52
}

Analysis

From what we have, we can see that the insert operation is log N and delete max is log N. There are also improvements that can be made to further improve this algorithm such as the D-ary heap and the Fibonacci implementations

Considerations

• It is important to keep in mind that this implementation assumes that the client does not change the keys while on the PQ. The way to avoid this is by ensuring keys are immutable
• It is also possible that someone deletes when the PQ is empty and we need to handle that appropriately. Depending on our implementation we will also realistically want to have the array be an automatically growing array
• We can create a minimum oriented queue by replacing less with greater, in our implementation this also applies to the implementation we have for the swim and sink functions
• We can also provide other operations such as changing the priority of an item - we can use the sink and swim operations to do this

Heapsort

Take advantage of a Binary Heap to implement a clever sorting algorithm

Algorithm

• Create a max-heap with all N keys
• Repeatedly remove the max key

Implementation

We will build the heap bottom-up and right-to-left and then tear the heap back down afterwards, by doing this we will have ensured that the array is sorted

The implementation is mostly the same as the MaxHeapPQ above but has been adjusted to be 0-indexed so that we can iterate through the array without the need for an extra starting element for offsetting the index calculation

Analysis

• During construction - <= 2N compares and exchanges
• During sort - <= 2 N lg N compares and exchanges

This is an in-place algorithm that is inplace and N log N in the worst case, this is relevant in comparison with Mergesort which requires extra space and Quicksort which is in place but can be quadratic in the worst case

Heapsort is optimal for both time and space but:

1. Inner loop is longer than quicksort - generally more work to do than quicksort
2. Makes poor use of cache memory since memory references are all over the place - quicksort refers to things that are close to each other
3. Not stable

Event Driven Simulation

Sometimes we want to be able to simulate particles for scientific or other reasons

We use a model called a Hard disk model

• Moving particles collide with each other and walls
• Each particle is a disk with known position, velocity, mass, and radius
• No other forces

Now what happens when two balls bump into each other and how can we do this efficiently? If we have lots of balls this can be a very big combination

A time driven simulation where we check if there is an overlap every iteration of time

• Lots of checks (N^2)
• Simulation too slow if dt is small
• May miss collision if dt is large

Instead of this we use something called an Event Driven Simulation

• Focus on time only when a collision will happen based on the velocity of different particles
• Predict when a particle will collide
• Use this time as a key in a priority queue
• We run our simulation based on which are the most likely collisions