168e6c3455ca9fe82a864ad93fb61e3e894397a5
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) {
35 * Enqueue data into the priority queue.
37 * @param data - Data to enqueue.
38 * @param priority - Priority of the data. Lower values have higher priority.
39 * @returns The new size of the priority queue.
41 public enqueue (data
: T
, priority
?: number): number {
42 priority
= priority
?? 0
44 for (const [index
, node
] of this.nodeArray
.entries()) {
45 if (node
.priority
> priority
) {
46 this.nodeArray
.splice(index
, 0, { data
, priority
})
52 this.nodeArray
.push({ data
, priority
})
54 return this.incrementSize()
58 * Dequeue data from the priority queue.
60 * @returns The dequeued data or `undefined` if the priority queue is empty.
62 public dequeue (): T
| undefined {
66 return this.nodeArray
.shift()?.data
70 * Peeks at the first data.
71 * @returns The first data or `undefined` if the priority queue is empty.
73 public peekFirst (): T
| undefined {
74 return this.nodeArray
[0]?.data
78 * Peeks at the last data.
79 * @returns The last data or `undefined` if the priority queue is empty.
81 public peekLast (): T
| undefined {
82 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
86 * Clears the priority queue.
88 public clear (): void {
95 * Increments the size of the deque.
97 * @returns The new size of the deque.
99 private incrementSize (): number {
101 if (this.size
> this.maxSize
) {
102 this.maxSize
= this.size