FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
javascript/data-structures/priorityQueue.js at master · dcipher00/javascript · GitHub
dcipher00
/
javascript
Public
forked from
AllAlgorithms/javascript
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
javascript
/
data-structures
/
priorityQueue.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
117 lines (106 loc) · 2.67 KB
Breadcrumbs
javascript
/
data-structures
/
priorityQueue.js
Copy path
File metadata and controls
117 lines (106 loc) · 2.67 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
/**
*
@author
Rashik Ansar
*
* Implemntaion of priority queue
* Lower the priority value higher its priority
* under the hood its implementing minBinaryHeap
*/
class
PriorityQueue
{
constructor
(
)
{
this
.
values
=
[
]
;
}
/**
* Adding data to the queue
*
@param
{
*
} data Data to add into queue
*
@param
{
*
} priority Priority of the data
*
@returns
{
PriorityQueue
}
*/
enqueue
(
data
,
priority
)
{
let
temp
=
new
Node
(
data
,
priority
)
;
this
.
values
.
push
(
temp
)
;
this
.
bubbleUp
(
)
;
return
this
;
}
/**
* removing a node from the queue
*
@returns
{
Node
}
*/
dequeue
(
)
{
const
min
=
this
.
values
[
0
]
;
const
end
=
this
.
values
.
pop
(
)
;
if
(
this
.
values
.
length
>
0
)
{
this
.
values
[
0
]
=
end
;
this
.
sinkDown
(
)
;
}
return
min
;
}
/**
* enqueue helper function
*/
bubbleUp
(
)
{
let
index
=
this
.
values
.
length
-
1
;
const
element
=
this
.
values
[
index
]
;
while
(
index
>
0
)
{
let
parentIndex
=
Math
.
floor
(
(
index
-
1
)
/
2
)
;
let
parent
=
this
.
values
[
parentIndex
]
;
// if (element.priority <= parent.priority) break; //maxBinaryHeap condition
if
(
element
.
priority
>=
parent
.
priority
)
break
;
//minBinaryHeap condition
this
.
values
[
parentIndex
]
=
element
;
this
.
values
[
index
]
=
parent
;
index
=
parentIndex
;
}
}
/**
* dequeue helper function
*/
sinkDown
(
)
{
let
index
=
0
;
const
length
=
this
.
values
.
length
;
const
element
=
this
.
values
[
index
]
;
while
(
true
)
{
let
leftChildIndex
=
2
*
index
+
1
;
let
rightChildIndex
=
2
*
index
+
2
;
let
leftChild
;
let
rightChild
;
let
swap
=
null
;
if
(
leftChildIndex
<
length
)
{
leftChild
=
this
.
values
[
leftChildIndex
]
;
// Change below comparision operators to make maxBinaryHeap
if
(
leftChild
.
priority
<
element
.
priority
)
{
swap
=
leftChildIndex
;
}
}
if
(
rightChildIndex
<
length
)
{
rightChild
=
this
.
values
[
rightChildIndex
]
;
// Change below comparision operators to make maxBinaryHeap
if
(
(
!
swap
&&
rightChild
.
priority
<
element
.
priority
)
||
(
swap
&&
rightChild
.
priority
<
leftChild
.
priority
)
)
{
swap
=
rightChildIndex
;
}
}
if
(
!
swap
)
break
;
this
.
values
[
index
]
=
this
.
values
[
swap
]
;
this
.
values
[
swap
]
=
element
;
index
=
swap
;
}
}
}
class
Node
{
constructor
(
data
,
priority
)
{
this
.
data
=
data
;
this
.
priority
=
priority
;
}
}
let
a
=
new
PriorityQueue
(
)
;
a
.
enqueue
(
'Common Cold'
,
10
)
;
a
.
enqueue
(
'Gunshot wound'
,
2
)
;
a
.
enqueue
(
'Fever'
,
8
)
;
console
.
log
(
a
)
;
a
.
dequeue
(
)
;
console
.
log
(
a
)
;
a
.
dequeue
(
)
;
console
.
log
(
a
)
;
a
.
dequeue
(
)
;
console
.
log
(
a
)
;
Back
|
FazBrowse Home
|
New Git URL