2018-10-04 23:53:13 +05:30
|
|
|
/* Minimum Priority Queue
|
2023-10-03 23:08:19 +02:00
|
|
|
* It is a part of heap data structure
|
|
|
|
|
* A heap is a specific tree based data structure
|
|
|
|
|
* in which all the nodes of tree are in a specific order.
|
|
|
|
|
* that is the children are arranged in some
|
|
|
|
|
* respect of their parents, can either be greater
|
|
|
|
|
* or less than the parent. This makes it a min priority queue
|
|
|
|
|
* or max priority queue.
|
|
|
|
|
*/
|
2018-10-04 23:53:13 +05:30
|
|
|
|
|
|
|
|
// Functions: insert, delete, peek, isEmpty, print, heapSort, sink
|
|
|
|
|
|
|
|
|
|
class MinPriorityQueue {
|
2020-05-03 21:26:52 -03:00
|
|
|
// calls the constructor and initializes the capacity
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor(c) {
|
2020-05-03 09:05:12 +02:00
|
|
|
this.heap = []
|
|
|
|
|
this.capacity = c
|
|
|
|
|
this.size = 0
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// inserts the key at the end and rearranges it
|
|
|
|
|
// so that the binary heap is in appropriate order
|
2023-10-03 23:08:19 +02:00
|
|
|
insert(key) {
|
2020-05-03 09:05:12 +02:00
|
|
|
if (this.isFull()) return
|
|
|
|
|
this.heap[this.size + 1] = key
|
|
|
|
|
let k = this.size + 1
|
2018-10-04 23:53:13 +05:30
|
|
|
while (k > 1) {
|
|
|
|
|
if (this.heap[k] < this.heap[Math.floor(k / 2)]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
const temp = this.heap[k]
|
|
|
|
|
this.heap[k] = this.heap[Math.floor(k / 2)]
|
|
|
|
|
this.heap[Math.floor(k / 2)] = temp
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
k = Math.floor(k / 2)
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
this.size++
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// returns the highest priority value
|
2023-10-03 23:08:19 +02:00
|
|
|
peek() {
|
2020-05-03 09:05:12 +02:00
|
|
|
return this.heap[1]
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// returns boolean value whether the heap is empty or not
|
2023-10-03 23:08:19 +02:00
|
|
|
isEmpty() {
|
2020-05-03 21:26:52 -03:00
|
|
|
return this.size === 0
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// returns boolean value whether the heap is full or not
|
2023-10-03 23:08:19 +02:00
|
|
|
isFull() {
|
2023-08-21 15:06:43 -03:00
|
|
|
return this.size === this.capacity
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// prints the heap
|
2023-10-03 23:08:19 +02:00
|
|
|
print(output = (value) => console.log(value)) {
|
2021-10-10 16:25:41 +02:00
|
|
|
output(this.heap.slice(1))
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2021-10-28 15:37:43 +05:30
|
|
|
// heap reverse can be done by performing swapping the first
|
2021-10-26 05:41:32 +02:00
|
|
|
// element with the last, removing the last element to
|
|
|
|
|
// new array and calling sink function.
|
2023-10-03 23:08:19 +02:00
|
|
|
heapReverse() {
|
2021-10-26 05:41:32 +02:00
|
|
|
const heapSort = []
|
|
|
|
|
while (this.size > 0) {
|
|
|
|
|
// swap first element with last element
|
2023-10-03 23:08:19 +02:00
|
|
|
;[this.heap[1], this.heap[this.size]] = [
|
|
|
|
|
this.heap[this.size],
|
|
|
|
|
this.heap[1]
|
|
|
|
|
]
|
2021-10-26 05:41:32 +02:00
|
|
|
heapSort.push(this.heap.pop())
|
|
|
|
|
this.size--
|
|
|
|
|
this.sink()
|
2020-05-03 09:05:12 +02:00
|
|
|
}
|
2021-10-26 05:41:32 +02:00
|
|
|
// first value from heap it's empty to respect
|
|
|
|
|
// structure with 1 as index of the first element
|
|
|
|
|
this.heap = [undefined, ...heapSort.reverse()]
|
|
|
|
|
this.size = heapSort.length
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
|
2020-05-03 09:05:12 +02:00
|
|
|
// this function reorders the heap after every delete function
|
2023-10-03 23:08:19 +02:00
|
|
|
sink() {
|
2020-05-03 09:05:12 +02:00
|
|
|
let k = 1
|
2018-10-04 23:53:13 +05:30
|
|
|
while (2 * k <= this.size || 2 * k + 1 <= this.size) {
|
2020-05-03 09:05:12 +02:00
|
|
|
let minIndex
|
2018-10-04 23:53:13 +05:30
|
|
|
if (this.heap[2 * k] >= this.heap[k]) {
|
2020-05-03 09:05:12 +02:00
|
|
|
if (2 * k + 1 <= this.size && this.heap[2 * k + 1] >= this.heap[k]) {
|
|
|
|
|
break
|
|
|
|
|
} else if (2 * k + 1 > this.size) {
|
|
|
|
|
break
|
|
|
|
|
}
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
if (2 * k + 1 > this.size) {
|
2020-05-03 09:05:12 +02:00
|
|
|
minIndex = this.heap[2 * k] < this.heap[k] ? 2 * k : k
|
2018-10-04 23:53:13 +05:30
|
|
|
} else {
|
|
|
|
|
if (
|
|
|
|
|
this.heap[k] > this.heap[2 * k] ||
|
|
|
|
|
this.heap[k] > this.heap[2 * k + 1]
|
|
|
|
|
) {
|
2023-10-03 23:08:19 +02:00
|
|
|
minIndex = this.heap[2 * k] < this.heap[2 * k + 1] ? 2 * k : 2 * k + 1
|
2018-10-04 23:53:13 +05:30
|
|
|
} else {
|
2020-05-03 09:05:12 +02:00
|
|
|
minIndex = k
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
const temp = this.heap[k]
|
|
|
|
|
this.heap[k] = this.heap[minIndex]
|
|
|
|
|
this.heap[minIndex] = temp
|
|
|
|
|
k = minIndex
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-26 05:41:32 +02:00
|
|
|
// deletes the highest priority value from the heap. The last
|
|
|
|
|
// element goes to ahead to first position and reorder heap
|
2023-10-03 23:08:19 +02:00
|
|
|
delete() {
|
2021-10-26 05:41:32 +02:00
|
|
|
// checks empty and one element array conditions
|
|
|
|
|
if (this.isEmpty()) return
|
|
|
|
|
if (this.size === 1) {
|
|
|
|
|
this.size--
|
|
|
|
|
return this.heap.pop()
|
|
|
|
|
}
|
2020-05-03 09:05:12 +02:00
|
|
|
const min = this.heap[1]
|
2021-10-26 05:41:32 +02:00
|
|
|
this.heap[1] = this.heap.pop()
|
2020-05-03 09:05:12 +02:00
|
|
|
this.size--
|
|
|
|
|
this.sink()
|
|
|
|
|
return min
|
2018-10-04 23:53:13 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2021-10-10 16:25:41 +02:00
|
|
|
export { MinPriorityQueue }
|
