Priority queue examples

These examples use smaller numbers for more urgent incidents. The JavaScript example includes a minimal binary-heap implementation because JavaScript has no built-in priority queue.

Python

import heapq


def print_label_value(label, value):
    print(f"\033[1;36m{label}:\033[0m {value}")


def describe(item):
    priority, sequence, value = item
    return f"{value} (priority {priority})"


urgent_incidents = []
next_sequence = 0


def enqueue(value, priority):
    global next_sequence
    heapq.heappush(urgent_incidents, (priority, next_sequence, value))
    next_sequence += 1


enqueue("Season reward missing", 3)
print_label_value("1. Add Season reward missing (priority 3)", "queued")

enqueue("Matchmaking unavailable", 1)
print_label_value("2. Add Matchmaking unavailable (priority 1)", "queued")

enqueue("Login queue unstable", 2)
print_label_value("3. Add Login queue unstable (priority 2)", "queued")

print_label_value("4. Remove highest priority", describe(heapq.heappop(urgent_incidents)))
print_label_value("5. Remove next priority", describe(heapq.heappop(urgent_incidents)))
print_label_value("6. Remove final priority", describe(heapq.heappop(urgent_incidents)))
print_label_value("7. Queue status", "empty" if not urgent_incidents else "has incidents")

JavaScript

function printLabelValue(label, value) {
  console.log(`\x1b[1;36m${label}:\x1b[0m`, value);
}

class PriorityQueue {
  constructor() {
    this.items = [];
    this.nextSequence = 0;
  }

  isHigherPriority(left, right) {
    if (left.priority !== right.priority) {
      return left.priority < right.priority;
    }
    return left.sequence < right.sequence;
  }

  enqueue(value, priority) {
    const item = { value, priority, sequence: this.nextSequence };
    this.nextSequence += 1;
    this.items.push(item);

    let index = this.items.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (!this.isHigherPriority(this.items[index], this.items[parentIndex])) {
        break;
      }
      [this.items[index], this.items[parentIndex]] = [
        this.items[parentIndex],
        this.items[index],
      ];
      index = parentIndex;
    }
  }

  dequeue() {
    if (this.items.length === 0) {
      throw new Error("cannot dequeue from an empty priority queue");
    }

    const first = this.items[0];
    const last = this.items.pop();
    if (this.items.length > 0) {
      this.items[0] = last;
      let index = 0;

      while (true) {
        const leftIndex = index * 2 + 1;
        const rightIndex = index * 2 + 2;
        let bestIndex = index;

        if (
          leftIndex < this.items.length &&
          this.isHigherPriority(this.items[leftIndex], this.items[bestIndex])
        ) {
          bestIndex = leftIndex;
        }
        if (
          rightIndex < this.items.length &&
          this.isHigherPriority(this.items[rightIndex], this.items[bestIndex])
        ) {
          bestIndex = rightIndex;
        }
        if (bestIndex === index) {
          break;
        }

        [this.items[index], this.items[bestIndex]] = [
          this.items[bestIndex],
          this.items[index],
        ];
        index = bestIndex;
      }
    }
    return first;
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

function describe(item) {
  return `${item.value} (priority ${item.priority})`;
}

const urgentIncidents = new PriorityQueue();
urgentIncidents.enqueue("Season reward missing", 3);
printLabelValue("1. Add Season reward missing (priority 3)", "queued");

urgentIncidents.enqueue("Matchmaking unavailable", 1);
printLabelValue("2. Add Matchmaking unavailable (priority 1)", "queued");

urgentIncidents.enqueue("Login queue unstable", 2);
printLabelValue("3. Add Login queue unstable (priority 2)", "queued");

printLabelValue("4. Remove highest priority", describe(urgentIncidents.dequeue()));
printLabelValue("5. Remove next priority", describe(urgentIncidents.dequeue()));
printLabelValue("6. Remove final priority", describe(urgentIncidents.dequeue()));
printLabelValue("7. Queue status", urgentIncidents.isEmpty() ? "empty" : "has incidents");

Expected output

1. Add Season reward missing (priority 3): queued
2. Add Matchmaking unavailable (priority 1): queued
3. Add Login queue unstable (priority 2): queued
4. Remove highest priority: Matchmaking unavailable (priority 1)
5. Remove next priority: Login queue unstable (priority 2)
6. Remove final priority: Season reward missing (priority 3)
7. Queue status: empty