Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit566d910

Browse files
fix: refactor PrimMST and fix bug in PriorityQueue (TheAlgorithms#1300)
* ref: KeyPriorityQueue in separate fileTheAlgorithms#1298* feat: add tests for KeyPriorityQueueTheAlgorithms#1298* fix: _shiftDown refactored and correctedTheAlgorithms#1298* fix: use KeyPriorityQueue in PrimMSTTheAlgorithms#1298* feat: add test for PrimMSTTheAlgorithms#1298* fix: format filesTheAlgorithms#1298* fix: minor coding style changes* fix: use map for keys and prioritiesTheAlgorithms#1298
1 parent0c42758 commit566d910

File tree

4 files changed

+301
-154
lines changed

4 files changed

+301
-154
lines changed
Lines changed: 153 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,153 @@
1+
/**
2+
* KeyPriorityQueue is a priority queue based on a Minimum Binary Heap.
3+
*
4+
* Minimum Binary Heaps are binary trees which are filled level by level
5+
* and then from left to right inside a depth level.
6+
* Their main property is that any parent node has a smaller or equal priority to all of its children,
7+
* hence the root of the tree always has the smallest priority of all nodes.
8+
*
9+
* This implementation of the Minimum Binary Heap allows for nodes to be associated to both a key,
10+
* which can be any datatype, and a priority.
11+
*
12+
* The heap is represented by an array with nodes ordered
13+
* from root-to-leaf, left-to-right.
14+
* Therefore, the parent-child node relationship is such that
15+
* * the children nodes positions relative to their parent are: (parentPos * 2 + 1) and (parentPos * 2 + 2)
16+
* * the parent node position relative to either of its children is: Math.floor((childPos - 1) / 2)
17+
*
18+
* More information and visuals on Binary Heaps can be found here: https://www.geeksforgeeks.org/binary-heap/
19+
*/
20+
21+
// Priority Queue Helper functions
22+
constgetParentPosition=position=>Math.floor((position-1)/2)
23+
constgetChildrenPositions=position=>[2*position+1,2*position+2]
24+
25+
classKeyPriorityQueue{
26+
// Priority Queue class using Minimum Binary Heap
27+
constructor(){
28+
this._heap=[]
29+
this.priorities=newMap()
30+
}
31+
32+
/**
33+
* Checks if the heap is empty
34+
*@returns boolean
35+
*/
36+
isEmpty(){
37+
returnthis._heap.length===0
38+
}
39+
40+
/**
41+
* Adds an element to the queue
42+
*@param {*} key
43+
*@param {number} priority
44+
*/
45+
push(key,priority){
46+
this._heap.push(key)
47+
this.priorities.set(key,priority)
48+
this._shiftUp(this._heap.length-1)
49+
}
50+
51+
/**
52+
* Removes the element with least priority
53+
*@returns the key of the element with least priority
54+
*/
55+
pop(){
56+
this._swap(0,this._heap.length-1)
57+
constkey=this._heap.pop()
58+
this.priorities.delete(key)
59+
this._shiftDown(0)
60+
returnkey
61+
}
62+
63+
/**
64+
* Checks whether a given key is present in the queue
65+
*@param {*} key
66+
*@returns boolean
67+
*/
68+
contains(key){
69+
returnthis.priorities.has(key)
70+
}
71+
72+
/**
73+
* Updates the priority of the given element.
74+
* Adds the element if it is not in the queue.
75+
*@param {*} key the element to change
76+
*@param {number} priority new priority of the element
77+
*/
78+
update(key,priority){
79+
constcurrPos=this._heap.indexOf(key)
80+
// if the key does not exist yet, add it
81+
if(currPos===-1)returnthis.push(key,priority)
82+
// else update priority
83+
this.priorities.set(key,priority)
84+
constparentPos=getParentPosition(currPos)
85+
constcurrPriority=this._getPriorityOrInfinite(currPos)
86+
constparentPriority=this._getPriorityOrInfinite(parentPos)
87+
const[child1Pos,child2Pos]=getChildrenPositions(currPos)
88+
constchild1Priority=this._getPriorityOrInfinite(child1Pos)
89+
constchild2Priority=this._getPriorityOrInfinite(child2Pos)
90+
91+
if(parentPos>=0&&parentPriority>currPriority){
92+
this._shiftUp(currPos)
93+
}elseif(child1Priority<currPriority||child2Priority<currPriority){
94+
this._shiftDown(currPos)
95+
}
96+
}
97+
98+
_getPriorityOrInfinite(position){
99+
// Helper function, returns priority of the node, or Infinite if no node corresponds to this position
100+
if(position>=0&&position<this._heap.length)returnthis.priorities.get(this._heap[position])
101+
elsereturnInfinity
102+
}
103+
104+
_shiftUp(position){
105+
// Helper function to shift up a node to proper position (equivalent to bubbleUp)
106+
letcurrPos=position
107+
letparentPos=getParentPosition(currPos)
108+
letcurrPriority=this._getPriorityOrInfinite(currPos)
109+
letparentPriority=this._getPriorityOrInfinite(parentPos)
110+
111+
while(parentPos>=0&&parentPriority>currPriority){
112+
this._swap(currPos,parentPos)
113+
currPos=parentPos
114+
parentPos=getParentPosition(currPos)
115+
currPriority=this._getPriorityOrInfinite(currPos)
116+
parentPriority=this._getPriorityOrInfinite(parentPos)
117+
}
118+
}
119+
120+
_shiftDown(position){
121+
// Helper function to shift down a node to proper position (equivalent to bubbleDown)
122+
letcurrPos=position
123+
let[child1Pos,child2Pos]=getChildrenPositions(currPos)
124+
letchild1Priority=this._getPriorityOrInfinite(child1Pos)
125+
letchild2Priority=this._getPriorityOrInfinite(child2Pos)
126+
letcurrPriority=this._getPriorityOrInfinite(currPos)
127+
128+
if(currPriority===Infinity){
129+
return
130+
}
131+
132+
while(child1Priority<currPriority||child2Priority<currPriority){
133+
if(child1Priority<currPriority&&child1Priority<child2Priority){
134+
this._swap(child1Pos,currPos)
135+
currPos=child1Pos
136+
}else{
137+
this._swap(child2Pos,currPos)
138+
currPos=child2Pos
139+
}
140+
[child1Pos,child2Pos]=getChildrenPositions(currPos)
141+
child1Priority=this._getPriorityOrInfinite(child1Pos)
142+
child2Priority=this._getPriorityOrInfinite(child2Pos)
143+
currPriority=this._getPriorityOrInfinite(currPos)
144+
}
145+
}
146+
147+
_swap(position1,position2){
148+
// Helper function to swap 2 nodes
149+
[this._heap[position1],this._heap[position2]]=[this._heap[position2],this._heap[position1]]
150+
}
151+
}
152+
153+
export{KeyPriorityQueue}
Lines changed: 126 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,126 @@
1+
import{KeyPriorityQueue}from'../KeyPriorityQueue.js'
2+
3+
describe('Key Priority Queue',()=>{
4+
describe('Method isEmpty',()=>{
5+
test('Check heap is empty',()=>{
6+
constqueue=newKeyPriorityQueue()
7+
constres=queue.isEmpty()
8+
expect(res).toEqual(true)
9+
})
10+
11+
test('Check heap is not empty',()=>{
12+
constqueue=newKeyPriorityQueue()
13+
queue.push(0,2)
14+
constres=queue.isEmpty()
15+
expect(res).toEqual(false)
16+
})
17+
})
18+
19+
describe('Methods push and pop',()=>{
20+
test('Test Case 1',()=>{
21+
// create queue
22+
constqueue=newKeyPriorityQueue()
23+
queue.push(0,3)
24+
queue.push(1,7)
25+
queue.push(2,9)
26+
queue.push(3,13)
27+
// create expected queue
28+
constexpectedQueue=newKeyPriorityQueue()
29+
expectedQueue.push(1,7)
30+
expectedQueue.push(3,13)
31+
expectedQueue.push(2,9)
32+
// result from popping element from the queue
33+
queue.pop()
34+
expect(queue).toEqual(expectedQueue)
35+
})
36+
37+
test('Test Case 2',()=>{
38+
// create queue
39+
constqueue=newKeyPriorityQueue()
40+
queue.push(0,3)
41+
queue.push(1,9)
42+
queue.push(2,7)
43+
queue.push(3,13)
44+
// create expected queue
45+
constexpectedQueue=newKeyPriorityQueue()
46+
expectedQueue.push(2,7)
47+
expectedQueue.push(1,9)
48+
expectedQueue.push(3,13)
49+
// result from popping element from the queue
50+
queue.pop()
51+
expect(queue).toEqual(expectedQueue)
52+
})
53+
54+
test('Test Case 3',()=>{
55+
// create queue
56+
constqueue=newKeyPriorityQueue()
57+
queue.push(0,3)
58+
queue.push(1,7)
59+
queue.push(2,9)
60+
queue.push(3,12)
61+
queue.push(4,13)
62+
// create expected queue
63+
constexpectedQueue=newKeyPriorityQueue()
64+
expectedQueue.push(1,7)
65+
expectedQueue.push(3,12)
66+
expectedQueue.push(2,9)
67+
expectedQueue.push(4,13)
68+
// result from popping element from the queue
69+
queue.pop()
70+
expect(queue).toEqual(expectedQueue)
71+
})
72+
})
73+
74+
describe('Method contains',()=>{
75+
test('Check heap does not contain element',()=>{
76+
constqueue=newKeyPriorityQueue()
77+
constres=queue.contains(0)
78+
expect(res).toEqual(false)
79+
})
80+
81+
test('Check heap contains element',()=>{
82+
constqueue=newKeyPriorityQueue()
83+
queue.push(0,2)
84+
constres=queue.contains(0)
85+
expect(res).toEqual(true)
86+
})
87+
})
88+
89+
describe('Method update',()=>{
90+
test('Update without change in position',()=>{
91+
// create queue
92+
constqueue=newKeyPriorityQueue()
93+
queue.push(0,3)
94+
queue.push(1,5)
95+
queue.push(2,7)
96+
queue.push(3,11)
97+
// create expected queue
98+
constexpectedQueue=newKeyPriorityQueue()
99+
expectedQueue.push(0,2)
100+
expectedQueue.push(1,5)
101+
expectedQueue.push(2,7)
102+
expectedQueue.push(3,11)
103+
// result from updating to similar priority
104+
queue.update(0,2)
105+
expect(queue).toEqual(expectedQueue)
106+
})
107+
108+
test('Update with change in position',()=>{
109+
// create queue
110+
constqueue=newKeyPriorityQueue()
111+
queue.push(0,3)
112+
queue.push(1,5)
113+
queue.push(2,7)
114+
queue.push(3,11)
115+
// create expected queue
116+
constexpectedQueue=newKeyPriorityQueue()
117+
expectedQueue.push(1,5)
118+
expectedQueue.push(3,11)
119+
expectedQueue.push(2,7)
120+
expectedQueue.push(0,9)
121+
// result from updating to similar priority
122+
queue.update(0,9)
123+
expect(queue).toEqual(expectedQueue)
124+
})
125+
})
126+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp