Priority Queue Data Structure

August 16, 2022

Data Structures and Algorithms in TypeScript (4 part series)Data Structures and Algorithms in TypeScript - What to Expect Queue Data Structure Priority Queue Data Structure Stack Data Structure

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 function
export 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 this post on Twitter