forked from TheAlgorithms/JavaScript
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinPriorityQueue.js
More file actions
Latest commit
125 lines (114 loc) · 3.39 KB
/
Copy pathMinPriorityQueue.js
File metadata and controls
125 lines (114 loc) · 3.39 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/* Minimum Priority Queue
* 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.
*/
// Functions: insert, delete, peek, isEmpty, print, heapSort, sink
classMinPriorityQueue{
// calls the constructor and initializes the capacity
constructor(c){
this.heap=[]
this.capacity=c
this.size=0
}
// inserts the key at the end and rearranges it
// so that the binary heap is in appropriate order
insert(key){
if(this.isFull())return
this.heap[this.size+1]=key
letk=this.size+1
while(k>1){
if(this.heap[k]<this.heap[Math.floor(k/2)]){
consttemp=this.heap[k]
this.heap[k]=this.heap[Math.floor(k/2)]
this.heap[Math.floor(k/2)]=temp
}
k=Math.floor(k/2)
}
this.size++
}
// returns the highest priority value
peek(){
returnthis.heap[1]
}
// returns boolean value whether the heap is empty or not
isEmpty(){
returnthis.size===0
}
// returns boolean value whether the heap is full or not
isFull(){
returnthis.size===this.capacity
}
// prints the heap
print(output=value=>console.log(value)){
output(this.heap.slice(1))
}
// heap reverse can be done by performing swapping the first
// element with the last, removing the last element to
// new array and calling sink function.
heapReverse(){
constheapSort=[]
while(this.size>0){
// swap first element with last element
[this.heap[1],this.heap[this.size]]=[this.heap[this.size],this.heap[1]]
heapSort.push(this.heap.pop())
this.size--
this.sink()
}
// 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
}
// this function reorders the heap after every delete function
sink(){
letk=1
while(2*k<=this.size||2*k+1<=this.size){
letminIndex
if(this.heap[2*k]>=this.heap[k]){
if(2*k+1<=this.size&&this.heap[2*k+1]>=this.heap[k]){
break
}elseif(2*k+1>this.size){
break
}
}
if(2*k+1>this.size){
minIndex=this.heap[2*k]<this.heap[k] ? 2*k : k
}else{
if(
this.heap[k]>this.heap[2*k]||
this.heap[k]>this.heap[2*k+1]
){
minIndex=
this.heap[2*k]<this.heap[2*k+1] ? 2*k : 2*k+1
}else{
minIndex=k
}
}
consttemp=this.heap[k]
this.heap[k]=this.heap[minIndex]
this.heap[minIndex]=temp
k=minIndex
}
}
// deletes the highest priority value from the heap. The last
// element goes to ahead to first position and reorder heap
delete(){
// checks empty and one element array conditions
if(this.isEmpty())return
if(this.size===1){
this.size--
returnthis.heap.pop()
}
constmin=this.heap[1]
this.heap[1]=this.heap.pop()
this.size--
this.sink()
returnmin
}
}
export{MinPriorityQueue}