Priority Queue Data Structure

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 has the same operations as a Queue. The only difference is that the enqueue operation will accept a priority as a parameter.

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.

1type CreatePriorityQueueReturnType<T> = {
2  enqueue: (item: T, priority?: 'high' | 'low') => void
3  dequeue: () => void
4  isEmpty: () => boolean
5  length: number
6  peek: () => T
7}

1// `createPriorityQueue` factory function accepts generic `T` type variable
2// `T` type variable will be used within `CreatePriorityQueueReturnType` and inside of factory function
3// `T` type variable will be also passed down to the `createQueue` factory function
4export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
5  // We need to create at least two queues: one for high priority and one for low priority items
6  const highPriorityQueue = createQueue<T>()
7  const lowPriorityQueue = createQueue<T>()
8
9  return {
10    enqueue() {},
11    dequeue() {},
12    isEmpty() {},
13    // we need to use `get` to access the latest `length` property of the queue
14    get length() {},
15    peek() {},
16  }
17}

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.

1import { createPriorityQueue } from './priority-queue'
2
3describe('priorityQueue', () => {
4  const priorityQueue = createPriorityQueue<string>()
5
6  it('should be empty when created', () => {
7    expect(priorityQueue.isEmpty()).toBe(true)
8    expect(priorityQueue.length).toBe(0)
9  })
10
11  it('should enqueue and dequeue in the priority order', () => {
12    // `priority` argument is optional, default value is 'low'
13    // 'First low priority item' will be added to the low priority queue
14    priorityQueue.enqueue('First low priority item', 'low')
15    // 'Second low priority item' will be added to the low priority queue
16    priorityQueue.enqueue('Second low priority item')
17
18    expect(priorityQueue.peek()).toBe('First low priority item')
19    expect(priorityQueue.length).toBe(2)
20
21    // 'First high priority item' will be added to the high priority queue
22    priorityQueue.enqueue('First high priority item', 'high')
23    // 'Second high priority item' will be added to the high priority queue
24    priorityQueue.enqueue('Second high priority item', 'high')
25
26    expect(priorityQueue.peek()).toBe('First high priority item')
27    expect(priorityQueue.length).toBe(4)
28
29    // dequeue (remove) the 'First high priority item' from the high priority queue
30    priorityQueue.dequeue()
31
32    expect(priorityQueue.peek()).toBe('Second high priority item')
33    expect(priorityQueue.length).toBe(3)
34
35    // dequeue (remove) the 'Second high priority item' from the high priority queue
36    priorityQueue.dequeue()
37
38    expect(priorityQueue.peek()).toBe('First low priority item')
39    expect(priorityQueue.length).toBe(2)
40
41    // dequeue (remove) the 'First low priority item' from the low priority queue
42    priorityQueue.dequeue()
43
44    expect(priorityQueue.peek()).toBe('Second low priority item')
45    expect(priorityQueue.length).toBe(1)
46
47    // dequeue (remove) the 'Second low priority item' from the low priority queue
48    priorityQueue.dequeue()
49    expect(priorityQueue.isEmpty()).toBe(true)
50    expect(priorityQueue.length).toBe(0)
51  })
52})

1export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
2  const highPriorityQueue = createQueue<T>()
3  const lowPriorityQueue = createQueue<T>()
4
5  return {
6    // `priority` argument is optional, default value is 'low'
7    enqueue(item, priority = 'low') {
8      // check the priority and add the item to the appropriate queue
9      if (priority === 'high') {
10        highPriorityQueue.enqueue(item)
11      } else {
12        lowPriorityQueue.enqueue(item)
13      }
14    },
15    dequeue() {},
16    isEmpty() {},
17    get length() {},
18    peek() {},
19  }
20}

1export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
2  const highPriorityQueue = createQueue<T>()
3  const lowPriorityQueue = createQueue<T>()
4
5  return {
6    // `priority` argument is optional, default value is 'low'
7    enqueue(item, priority = 'low') {
8      // check the priority and add the item to the appropriate queue
9      if (priority === 'high') {
10        highPriorityQueue.enqueue(item)
11      } else {
12        lowPriorityQueue.enqueue(item)
13      }
14    },
15    dequeue() {
16      // dequeue priority queue first, then dequeue low priority queue
17      if (!highPriorityQueue.isEmpty()) {
18        highPriorityQueue.dequeue()
19      } else {
20        lowPriorityQueue.dequeue()
21      }
22    },
23    isEmpty() {},
24    get length() {},
25    peek() {},
26  }
27}

1export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
2  const highPriorityQueue = createQueue<T>()
3  const lowPriorityQueue = createQueue<T>()
4
5  return {
6    // `priority` argument is optional, default value is 'low'
7    enqueue(item, priority = 'low') {
8      // check the priority and add the item to the appropriate queue
9      if (priority === 'high') {
10        highPriorityQueue.enqueue(item)
11      } else {
12        lowPriorityQueue.enqueue(item)
13      }
14    },
15    dequeue() {
16      // dequeue priority queue first, then dequeue low priority queue
17      if (!highPriorityQueue.isEmpty()) {
18        highPriorityQueue.dequeue()
19      } else {
20        lowPriorityQueue.dequeue()
21      }
22    },
23    isEmpty() {
24      // check if both queues are empty
25      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()
26    },
27    get length() {},
28    peek() {},
29  }
30}

1export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
2  const highPriorityQueue = createQueue<T>()
3  const lowPriorityQueue = createQueue<T>()
4
5  return {
6    // `priority` argument is optional, default value is 'low'
7    enqueue(item, priority = 'low') {
8      // check the priority and add the item to the appropriate queue
9      if (priority === 'high') {
10        highPriorityQueue.enqueue(item)
11      } else {
12        lowPriorityQueue.enqueue(item)
13      }
14    },
15    dequeue() {
16      // dequeue priority queue first, then dequeue low priority queue
17      if (!highPriorityQueue.isEmpty()) {
18        highPriorityQueue.dequeue()
19      } else {
20        lowPriorityQueue.dequeue()
21      }
22    },
23    isEmpty() {
24      // check if both queues are empty
25      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()
26    },
27    get length() {
28      // return the sum of the length of the high priority queue and the low priority queue
29      return highPriorityQueue.length + lowPriorityQueue.length
30    },
31    peek() {},
32  }
33}

1export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
2  const highPriorityQueue = createQueue<T>()
3  const lowPriorityQueue = createQueue<T>()
4
5  return {
6    // `priority` argument is optional, default value is 'low'
7    enqueue(item, priority = 'low') {
8      // check the priority and add the item to the appropriate queue
9      if (priority === 'high') {
10        highPriorityQueue.enqueue(item)
11      } else {
12        lowPriorityQueue.enqueue(item)
13      }
14    },
15    dequeue() {
16      // dequeue priority queue first, then dequeue low priority queue
17      if (!highPriorityQueue.isEmpty()) {
18        highPriorityQueue.dequeue()
19      } else {
20        lowPriorityQueue.dequeue()
21      }
22    },
23    isEmpty() {
24      // check if both queues are empty
25      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()
26    },
27    get length() {
28      // return the sum of the length of the high priority queue and the low priority queue
29      return highPriorityQueue.length + lowPriorityQueue.length
30    },
31    peek() {
32      // if the high priority queue is not empty, return the peek of the high priority queue
33      // otherwise return the peek of the low priority queue
34      if (!highPriorityQueue.isEmpty()) {
35        return highPriorityQueue.peek()
36      } else {
37        return lowPriorityQueue.peek()
38      }
39    },
40  }
41}

1import { createQueue } from './queue'
2
3type CreatePriorityQueueReturnType<T> = {
4  dequeue: () => void
5  enqueue: (item: T, priority?: 'high' | 'low') => void
6  isEmpty: () => boolean
7  length: number
8  peek: () => T
9}
10
11export function createPriorityQueue<T>(): CreatePriorityQueueReturnType<T> {
12  const highPriorityQueue = createQueue<T>()
13  const lowPriorityQueue = createQueue<T>()
14
15  return {
16    dequeue() {
17      if (!highPriorityQueue.isEmpty()) {
18        highPriorityQueue.dequeue()
19      } else {
20        lowPriorityQueue.dequeue()
21      }
22    },
23    enqueue(item, priority = 'low') {
24      if (priority === 'high') {
25        highPriorityQueue.enqueue(item)
26      } else {
27        lowPriorityQueue.enqueue(item)
28      }
29    },
30    isEmpty() {
31      return highPriorityQueue.isEmpty() && lowPriorityQueue.isEmpty()
32    },
33    get length() {
34      return highPriorityQueue.length + lowPriorityQueue.length
35    },
36    peek() {
37      if (!highPriorityQueue.isEmpty()) {
38        return highPriorityQueue.peek()
39      } else {
40        return lowPriorityQueue.peek()
41      }
42    },
43  }
44}

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