2023-02-23 15:35:45 +01:00
|
|
|
/**
|
|
|
|
|
* KeyPriorityQueue is a priority queue based on a Minimum Binary Heap.
|
|
|
|
|
*
|
|
|
|
|
* Minimum Binary Heaps are binary trees which are filled level by level
|
|
|
|
|
* and then from left to right inside a depth level.
|
|
|
|
|
* Their main property is that any parent node has a smaller or equal priority to all of its children,
|
|
|
|
|
* hence the root of the tree always has the smallest priority of all nodes.
|
|
|
|
|
*
|
|
|
|
|
* This implementation of the Minimum Binary Heap allows for nodes to be associated to both a key,
|
|
|
|
|
* which can be any datatype, and a priority.
|
|
|
|
|
*
|
|
|
|
|
* The heap is represented by an array with nodes ordered
|
|
|
|
|
* from root-to-leaf, left-to-right.
|
|
|
|
|
* Therefore, the parent-child node relationship is such that
|
|
|
|
|
* * the children nodes positions relative to their parent are: (parentPos * 2 + 1) and (parentPos * 2 + 2)
|
|
|
|
|
* * the parent node position relative to either of its children is: Math.floor((childPos - 1) / 2)
|
|
|
|
|
*
|
|
|
|
|
* More information and visuals on Binary Heaps can be found here: https://www.geeksforgeeks.org/binary-heap/
|
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
// Priority Queue Helper functions
|
2023-10-03 23:08:19 +02:00
|
|
|
const getParentPosition = (position) => Math.floor((position - 1) / 2)
|
|
|
|
|
const getChildrenPositions = (position) => [2 * position + 1, 2 * position + 2]
|
2023-02-23 15:35:45 +01:00
|
|
|
|
|
|
|
|
class KeyPriorityQueue {
|
|
|
|
|
// Priority Queue class using Minimum Binary Heap
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor() {
|
2023-02-23 15:35:45 +01:00
|
|
|
this._heap = []
|
|
|
|
|
this.priorities = new Map()
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Checks if the heap is empty
|
|
|
|
|
* @returns boolean
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
isEmpty() {
|
2023-02-23 15:35:45 +01:00
|
|
|
return this._heap.length === 0
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Adds an element to the queue
|
|
|
|
|
* @param {*} key
|
|
|
|
|
* @param {number} priority
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
push(key, priority) {
|
2023-02-23 15:35:45 +01:00
|
|
|
this._heap.push(key)
|
|
|
|
|
this.priorities.set(key, priority)
|
|
|
|
|
this._shiftUp(this._heap.length - 1)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Removes the element with least priority
|
|
|
|
|
* @returns the key of the element with least priority
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
pop() {
|
2023-02-23 15:35:45 +01:00
|
|
|
this._swap(0, this._heap.length - 1)
|
|
|
|
|
const key = this._heap.pop()
|
|
|
|
|
this.priorities.delete(key)
|
|
|
|
|
this._shiftDown(0)
|
|
|
|
|
return key
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Checks whether a given key is present in the queue
|
|
|
|
|
* @param {*} key
|
|
|
|
|
* @returns boolean
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
contains(key) {
|
2023-02-23 15:35:45 +01:00
|
|
|
return this.priorities.has(key)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Updates the priority of the given element.
|
|
|
|
|
* Adds the element if it is not in the queue.
|
|
|
|
|
* @param {*} key the element to change
|
|
|
|
|
* @param {number} priority new priority of the element
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
update(key, priority) {
|
2023-02-23 15:35:45 +01:00
|
|
|
const currPos = this._heap.indexOf(key)
|
|
|
|
|
// if the key does not exist yet, add it
|
|
|
|
|
if (currPos === -1) return this.push(key, priority)
|
|
|
|
|
// else update priority
|
|
|
|
|
this.priorities.set(key, priority)
|
|
|
|
|
const parentPos = getParentPosition(currPos)
|
|
|
|
|
const currPriority = this._getPriorityOrInfinite(currPos)
|
|
|
|
|
const parentPriority = this._getPriorityOrInfinite(parentPos)
|
|
|
|
|
const [child1Pos, child2Pos] = getChildrenPositions(currPos)
|
|
|
|
|
const child1Priority = this._getPriorityOrInfinite(child1Pos)
|
|
|
|
|
const child2Priority = this._getPriorityOrInfinite(child2Pos)
|
|
|
|
|
|
|
|
|
|
if (parentPos >= 0 && parentPriority > currPriority) {
|
|
|
|
|
this._shiftUp(currPos)
|
|
|
|
|
} else if (child1Priority < currPriority || child2Priority < currPriority) {
|
|
|
|
|
this._shiftDown(currPos)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
_getPriorityOrInfinite(position) {
|
2023-02-23 15:35:45 +01:00
|
|
|
// Helper function, returns priority of the node, or Infinite if no node corresponds to this position
|
2023-10-03 23:08:19 +02:00
|
|
|
if (position >= 0 && position < this._heap.length)
|
|
|
|
|
return this.priorities.get(this._heap[position])
|
2023-02-23 15:35:45 +01:00
|
|
|
else return Infinity
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
_shiftUp(position) {
|
2023-02-23 15:35:45 +01:00
|
|
|
// Helper function to shift up a node to proper position (equivalent to bubbleUp)
|
|
|
|
|
let currPos = position
|
|
|
|
|
let parentPos = getParentPosition(currPos)
|
|
|
|
|
let currPriority = this._getPriorityOrInfinite(currPos)
|
|
|
|
|
let parentPriority = this._getPriorityOrInfinite(parentPos)
|
|
|
|
|
|
|
|
|
|
while (parentPos >= 0 && parentPriority > currPriority) {
|
|
|
|
|
this._swap(currPos, parentPos)
|
|
|
|
|
currPos = parentPos
|
|
|
|
|
parentPos = getParentPosition(currPos)
|
|
|
|
|
currPriority = this._getPriorityOrInfinite(currPos)
|
|
|
|
|
parentPriority = this._getPriorityOrInfinite(parentPos)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
_shiftDown(position) {
|
2023-02-23 15:35:45 +01:00
|
|
|
// Helper function to shift down a node to proper position (equivalent to bubbleDown)
|
|
|
|
|
let currPos = position
|
|
|
|
|
let [child1Pos, child2Pos] = getChildrenPositions(currPos)
|
|
|
|
|
let child1Priority = this._getPriorityOrInfinite(child1Pos)
|
|
|
|
|
let child2Priority = this._getPriorityOrInfinite(child2Pos)
|
|
|
|
|
let currPriority = this._getPriorityOrInfinite(currPos)
|
|
|
|
|
|
|
|
|
|
if (currPriority === Infinity) {
|
|
|
|
|
return
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
while (child1Priority < currPriority || child2Priority < currPriority) {
|
|
|
|
|
if (child1Priority < currPriority && child1Priority < child2Priority) {
|
|
|
|
|
this._swap(child1Pos, currPos)
|
|
|
|
|
currPos = child1Pos
|
|
|
|
|
} else {
|
|
|
|
|
this._swap(child2Pos, currPos)
|
|
|
|
|
currPos = child2Pos
|
|
|
|
|
}
|
2023-10-03 23:08:19 +02:00
|
|
|
;[child1Pos, child2Pos] = getChildrenPositions(currPos)
|
2023-02-23 15:35:45 +01:00
|
|
|
child1Priority = this._getPriorityOrInfinite(child1Pos)
|
|
|
|
|
child2Priority = this._getPriorityOrInfinite(child2Pos)
|
|
|
|
|
currPriority = this._getPriorityOrInfinite(currPos)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
_swap(position1, position2) {
|
2023-02-23 15:35:45 +01:00
|
|
|
// Helper function to swap 2 nodes
|
2023-10-03 23:08:19 +02:00
|
|
|
;[this._heap[position1], this._heap[position2]] = [
|
|
|
|
|
this._heap[position2],
|
|
|
|
|
this._heap[position1]
|
|
|
|
|
]
|
2023-02-23 15:35:45 +01:00
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
export { KeyPriorityQueue }
|
