Skip to content
Lukas Polak

August 16, 2022

Priority Queue Data Structure

To create a Priority Queue, we can leverage a previously created Queue. Want to see more details? Check the article!

Introduction

Yesterday's article was about the Queue data structure. Today we will be looking at the Priority Queue data structure.

A priority Queue is very similar to a Queue. The difference is that the elements in the Priority Queue are ordered by priority.

To create a Queue, we will not only use the knowledge from the previous article but also the Queue factory function.

Priority Queue Operations

Priority Queue has the same operations as a Queue. The only difference is that the enqueue operation will accept a priority as a parameter.

Implementation

TypeScript definition

The TypeScript definition is almost the same as for Queue, The only difference is that enqueue operation will accept a priority (high or low) as a argument.

index.ts
type CreatePriorityQueueReturnType<T> = {  enqueue: (item: T, priority?: 'high' | 'low') => void  dequeue: () => void  isEmpty: () => boolean  length: number  peek: () => T}

Factory function implementation

index.ts
// `createPriorityQueue` factory function accepts generic `T` type variable// `T` type variable will be used within `CreatePriorityQueueReturnType` and inside of factory function// `T` type variable will be also passed down to the `createQueue` factory functionexport function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  // We need to create at least two queues: one for high priority and one for low priority items  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    enqueue() {},    dequeue() {},    isEmpty() {},    // we need to use `get` to access the latest `length` property of the queue    get length() {},    peek() {},  }}

Adding tests

As we have the createPriorityQueue function specified, as well as return types of factory function, we can write a test suite before implementing methods of that function.

index.test.ts
import { createPriorityQueue } from './priority-queue'
describe('priorityQueue', () => {  const priorityQueue = createPriorityQueue<string>()
  it('should be empty when created', () => {    expect(priorityQueue.isEmpty()).toBe(true)    expect(priorityQueue.length).toBe(0)  })
  it('should enqueue and dequeue in the priority order', () => {    // `priority` argument is optional, default value is 'low'    // 'First low priority item' will be added to the low priority queue    priorityQueue.enqueue('First low priority item', 'low')    // 'Second low priority item' will be added to the low priority queue    priorityQueue.enqueue('Second low priority item')
    expect(priorityQueue.peek()).toBe('First low priority item')    expect(priorityQueue.length).toBe(2)
    // 'First high priority item' will be added to the high priority queue    priorityQueue.enqueue('First high priority item', 'high')    // 'Second high priority item' will be added to the high priority queue    priorityQueue.enqueue('Second high priority item', 'high')
    expect(priorityQueue.peek()).toBe('First high priority item')    expect(priorityQueue.length).toBe(4)
    // dequeue (remove) the 'First high priority item' from the high priority queue    priorityQueue.dequeue()
    expect(priorityQueue.peek()).toBe('Second high priority item')    expect(priorityQueue.length).toBe(3)
    // dequeue (remove) the 'Second high priority item' from the high priority queue    priorityQueue.dequeue()
    expect(priorityQueue.peek()).toBe('First low priority item')    expect(priorityQueue.length).toBe(2)
    // dequeue (remove) the 'First low priority item' from the low priority queue    priorityQueue.dequeue()
    expect(priorityQueue.peek()).toBe('Second low priority item')    expect(priorityQueue.length).toBe(1)
    // dequeue (remove) the 'Second low priority item' from the low priority queue    priorityQueue.dequeue()    expect(priorityQueue.isEmpty()).toBe(true)    expect(priorityQueue.length).toBe(0)  })})

Implement enqueue

index.ts
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    // `priority` argument is optional, default value is 'low'    enqueue(item, priority = 'low') {      // check the priority and add the item to the appropriate queue      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    dequeue() {},    isEmpty() {},    get length() {},    peek() {},  }}

Implement dequeue

index.ts
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    // `priority` argument is optional, default value is 'low'    enqueue(item, priority = 'low') {      // check the priority and add the item to the appropriate queue      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    dequeue() {      // dequeue priority queue first, then dequeue low priority queue      if (!highPriorityQueue.isEmpty()) {        highPriorityQueue.dequeue()      } else {        lowPriorityQueue.dequeue()      }    },    isEmpty() {},    get length() {},    peek() {},  }}

Implement isEmpty

index.ts
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    // `priority` argument is optional, default value is 'low'    enqueue(item, priority = 'low') {      // check the priority and add the item to the appropriate queue      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    dequeue() {      // dequeue priority queue first, then dequeue low priority queue      if (!highPriorityQueue.isEmpty()) {        highPriorityQueue.dequeue()      } else {        lowPriorityQueue.dequeue()      }    },    isEmpty() {      // check if both queues are empty      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()    },    get length() {},    peek() {},  }}

Implement length getter

index.ts
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    // `priority` argument is optional, default value is 'low'    enqueue(item, priority = 'low') {      // check the priority and add the item to the appropriate queue      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    dequeue() {      // dequeue priority queue first, then dequeue low priority queue      if (!highPriorityQueue.isEmpty()) {        highPriorityQueue.dequeue()      } else {        lowPriorityQueue.dequeue()      }    },    isEmpty() {      // check if both queues are empty      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()    },    get length() {      // return the sum of the length of the high priority queue and the low priority queue      return highPriorityQueue.length + lowPriorityQueue.length    },    peek() {},  }}

Implement peek

index.ts
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    // `priority` argument is optional, default value is 'low'    enqueue(item, priority = 'low') {      // check the priority and add the item to the appropriate queue      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    dequeue() {      // dequeue priority queue first, then dequeue low priority queue      if (!highPriorityQueue.isEmpty()) {        highPriorityQueue.dequeue()      } else {        lowPriorityQueue.dequeue()      }    },    isEmpty() {      // check if both queues are empty      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()    },    get length() {      // return the sum of the length of the high priority queue and the low priority queue      return highPriorityQueue.length + lowPriorityQueue.length    },    peek() {      // if the high priority queue is not empty, return the peek of the high priority queue      // otherwise return the peek of the low priority queue      if (!highPriorityQueue.isEmpty()) {        return highPriorityQueue.peek()      } else {        return lowPriorityQueue.peek()      }    },  }}

Complete Implementation

index.ts
import { createQueue } from './queue'
type CreatePriorityQueueReturnType<T> = {  dequeue: () => void  enqueue: (item: T, priority?: 'high' | 'low') => void  isEmpty: () => boolean  length: number  peek: () => T}
export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {  const highPriorityQueue = createQueue<T>()  const lowPriorityQueue = createQueue<T>()
  return {    dequeue() {      if (!highPriorityQueue.isEmpty()) {        highPriorityQueue.dequeue()      } else {        lowPriorityQueue.dequeue()      }    },    enqueue(item, priority = 'low') {      if (priority === 'high') {        highPriorityQueue.enqueue(item)      } else {        lowPriorityQueue.enqueue(item)      }    },    isEmpty() {      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()    },    get length() {      return highPriorityQueue.length + lowPriorityQueue.length    },    peek() {      if (!highPriorityQueue.isEmpty()) {        return highPriorityQueue.peek()      } else {        return lowPriorityQueue.peek()      }    },  }}

Conclusion

In today's article, we've implemented the priority queue data structure. Our implementation is both type-safe and covered by tests, so we can build additional methods on top of our priority queue.

Have you found any bugs, or do you have any questions? Feel free to reach out on Twitter.

If you do not want to miss the next article, click on the follow button!

Share on X