cf4fb150e1e1caba20ff9e9d579128c110c40e73
4 interface PriorityQueueNode
<T
> {
12 * @typeParam T - Type of priority queue data.
15 export class PriorityQueue
<T
> {
16 private nodeArray
!: Array<PriorityQueueNode
<T
>>
17 /** Prioritized bucket size. */
18 private readonly k
: number
19 /** The size of the priority queue. */
21 /** The maximum size of the priority queue. */
22 public maxSize
!: number
25 * Constructs a k-priority queue.
27 * @param k - Prioritized bucket size.
29 public constructor (k
= Infinity) {
30 if (k
!== Infinity && !Number.isSafeInteger(k
)) {
31 throw new TypeError('k must be an integer')
34 throw new RangeError('k must be greater than or equal to 1')
41 * Enqueue data into the priority queue.
43 * @param data - Data to enqueue.
44 * @param priority - Priority of the data. Lower values have higher priority.
45 * @returns The new size of the priority queue.
47 public enqueue (data
: T
, priority
?: number): number {
48 priority
= priority
?? 0
50 this.k
=== Infinity || this.nodeArray
.length
/ this.k
< 1
52 : Math.trunc(this.nodeArray
.length
/ this.k
) * this.k
54 for (let index
= startIndex
; index
< this.nodeArray
.length
; index
++) {
55 if (this.nodeArray
[index
].priority
> priority
) {
56 this.nodeArray
.splice(index
, 0, { data
, priority
})
62 this.nodeArray
.push({ data
, priority
})
64 return this.incrementSize()
68 * Dequeue data from the priority queue.
70 * @returns The dequeued data or `undefined` if the priority queue is empty.
72 public dequeue (): T
| undefined {
76 return this.nodeArray
.shift()?.data
80 * Peeks at the first data.
81 * @returns The first data or `undefined` if the priority queue is empty.
83 public peekFirst (): T
| undefined {
84 return this.nodeArray
[0]?.data
88 * Peeks at the last data.
89 * @returns The last data or `undefined` if the priority queue is empty.
91 public peekLast (): T
| undefined {
92 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
96 * Clears the priority queue.
98 public clear (): void {
105 * Increments the size of the deque.
107 * @returns The new size of the deque.
109 private incrementSize (): number {
111 if (this.size
> this.maxSize
) {
112 this.maxSize
= this.size