Sure, binary heaps are often used to implement priority queues efficiently. Here's an example of a min binary heap, which can serve as a priority queue in JavaScript:
class MinHeap {
constructor() {
this.heap = [];
}
getMin() {
return this.heap[0];
}
insert(value) {
this.heap.push(value);
this.bubbleUp();
}
removeMin() {
const min = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.bubbleDown();
}
return min;
}
bubbleUp() {
let currentIndex = this.heap.length - 1;
while (currentIndex > 0) {
const parentIndex = Math.floor((currentIndex - 1) / 2);
if (this.heap[parentIndex] <= this.heap[currentIndex]) break;
[this.heap[parentIndex], this.heap[currentIndex]] = [
this.heap[currentIndex],
this.heap[parentIndex],
];
currentIndex = parentIndex;
}
}
bubbleDown() {
let currentIndex = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIndex = 2 * currentIndex + 1;
let rightChildIndex = 2 * currentIndex + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild < element) {
swap = leftChildIndex;
}
}
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if (
(swap === null && rightChild < element) ||
(swap !== null && rightChild < leftChild)
) {
swap = rightChildIndex;
}
}
if (swap === null) break;
this.heap[currentIndex] = this.heap[swap];
this.heap[swap] = element;
currentIndex = swap;
}
}
}
// Example usage:
const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(4);
minHeap.insert(8);
minHeap.insert(15);
console.log(minHeap.getMin()); // Output: 4
minHeap.removeMin();
console.log(minHeap.getMin()); // Output: 8
This MinHeap class maintains a binary heap structure where the minimum element is at the root. The insert() method adds elements to the heap while maintaining the heap property, getMin() returns the minimum element without removing it, and removeMin() removes and returns the minimum element while maintaining the heap property.
This example provides a basic implementation of a min binary heap that can be used as a priority queue. There are other types of heaps (such as max heaps) and more advanced priority queue implementations, but this should give you a starting point.
