class PriorityQueue {
constructor() {
this.heap = [];
}
insert(value, priority) {
this.heap.push({ value, priority });
this.bubbleUp();
}
extractMin() {
if (this.isEmpty()) return null;
if (this.heap.length === 1) return this.heap.pop().value;
const min = this.heap[0].value;
this.heap[0] = this.heap.pop();
this.bubbleDown();
return min;
}
peek() {
if (this.isEmpty()) return null;
return this.heap[0].value;
}
isEmpty() {
return this.heap.length === 0;
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index].priority < this.heap[parentIndex].priority) {
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
} else {
break;
}
}
}
bubbleDown() {
let index = 0;
const lastIndex = this.heap.length - 1;
while (true) {
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
let smallestChildIndex = index;
if (leftChildIndex <= lastIndex && this.heap[leftChildIndex].priority < this.heap[smallestChildIndex].priority) {
smallestChildIndex = leftChildIndex;
}
if (rightChildIndex <= lastIndex && this.heap[rightChildIndex].priority < this.heap[smallestChildIndex].priority) {
smallestChildIndex = rightChildIndex;
}
if (smallestChildIndex !== index) {
[this.heap[index], this.heap[smallestChildIndex]] = [this.heap[smallestChildIndex], this.heap[index]];
index = smallestChildIndex;
} else {
break;
}
}
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)