Priority Queue data structure

June 25th, 2021/Share

fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

Priority Queue in real life

Priority Queue data structure:

mimics a queue of things in real life with different urgencies. The more urgent, the higher the priority. Example: a queue of patients in an emergency room.
Each element in the queue has its own priority. Example: ['a', 1] -> data 'a', (highest) priority 1.
Higher priority element gets out first. Elements with the same priority follow: First-In-First-Out (FIFO).
Example applications: wifi network bandwidth management, computer CPU time management, ...

Build Priority Queue data structure

lecture-9/priority-queue-data-structure.js

// build Priority Queue data structure
// naive approach (not the best optimal solution)
class PriorityQueue {
  constructor() {
    this.queue = []
  }

  // add data to the queue, O(n)
  // using `heap` data structure will give O(logn)
  enqueue(element) {
    // queue is empty, add element immediately
    if(this.queue === 0) {
      return this.queue.push(element)
    }

    // queue is not empty,
    // go through all existing element,
    // add element right after existing element which has the same priority
    // 1 is highest priority
    var added = false;
    for(let i = 0; i < this.queue.length; i ++) {
        if(element[1] < this.queue[i][1]) {
            this.queue.splice(i, 0, element);
            added = true;
            break;
        }
    }

    // went through all existing elements but they all have higher priority,
    // add the element to the end of the queue
    if(!added) { 
      this.queue.push(element)
    }

    return element
  }

  // remove first element in queue
  // Note: O(n) with this implementation (for simplicity),
  // If we use `heap` data structure, we'll have O(logn)
  dequeue() {
    return this.queue.shift()
  }

  // see queue size, O(1)
  size() {
    return this.queue.length
  }

  // see first element in line, O(1)
  peek() {
    return this.queue[0]
  }

  // see all data in the queue, O(1)
  print() {
    console.log(this.queue)
  }
}

// create a priority queue
const priorityQueue = new PriorityQueue()
priorityQueue.print() // []

$ node priority-queue-data-structure.js
[]

How to insert/delete/access/search data

lecture-9/priority-queue-data-structure.js

// insert
console.log(priorityQueue.enqueue(['c', 3])) // [ 'c', 3 ]
console.log(priorityQueue.enqueue(['b', 2])) // [ 'b', 2 ]
priorityQueue.print() // [ [ 'b', 2 ], [ 'c', 3 ] ]

console.log(priorityQueue.enqueue(['a', 1])) // [ 'a', 1 ]
priorityQueue.print() // [ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ] ]

console.log(priorityQueue.enqueue([{'zyz': 123 }, 4])) // [ { zyz: 123 }, 4 ]
priorityQueue.print() // [ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]

console.log(priorityQueue.enqueue(['d', 2])) // [ 'd', 2 ]
priorityQueue.print() // [ [ 'a', 1 ], [ 'b', 2 ], [ 'd', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]

// delete 
console.log(priorityQueue.dequeue()) // [ 'a', 1 ]
priorityQueue.print() // [ [ 'b', 2 ], [ 'd', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]

// peek
console.log(priorityQueue.peek()) // [ 'b', 2 ]

// size
console.log(priorityQueue.size()) // 4

$ node priority-queue-data-structure.js
[ 'c', 3 ]
[ 'b', 2 ]
[ [ 'b', 2 ], [ 'c', 3 ] ]
[ 'a', 1 ]
[ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ] ]
[ { zyz: 123 }, 4 ]
[ [ 'a', 1 ], [ 'b', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]
[ 'd', 2 ]
[ [ 'a', 1 ], [ 'b', 2 ], [ 'd', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]
[ 'a', 1 ]
[ [ 'b', 2 ], [ 'd', 2 ], [ 'c', 3 ], [ { zyz: 123 }, 4 ] ]
[ 'b', 2 ]
4

How fast to insert/delete/access/search data

Data Structure	Insert	Delete	Access	Search
Priority Queue	O(logn): `enqueue`	O(logn): `dequeue`	N/A	N/A

⬆️ Time complexity (worst case) per operation

Real life interview questions

What is the Priority Queue data structure usually used for? Give 3 different examples.
What is the distinct feature of Priority Queue compared to a normal Queue ?
Write your own Priority Queue data structure with these operations: enqueue, dequeue, peek, size, print.
How do you insert/delete/access/search with Priority Queue data structure?
What is the Time Complexity of Priority Queue data structure on insert/delete/access/search operation?
Implement real life emergency room queue:
- Input:
- patients with different priorities.
- Output:
- patients with more serious injuries are served first.
- the priority of a patient who is in the queue first, but does not get out before a patient who gets in the queue later, will be increased by 1 every time that event occurs, this increase capped at priority 2.