90 lines
2.0 KiB
JavaScript
90 lines
2.0 KiB
JavaScript
/**
|
|
* @param compare - comparison function for items
|
|
* @returns Priority queue implemented with a min heap
|
|
*/ export function createPriorityQueue(compare) {
|
|
const arr = [];
|
|
let size = 0;
|
|
const left = (i)=>{
|
|
return 2 * i + 1;
|
|
};
|
|
const right = (i)=>{
|
|
return 2 * i + 2;
|
|
};
|
|
const parent = (i)=>{
|
|
return Math.floor((i - 1) / 2);
|
|
};
|
|
const swap = (a, b)=>{
|
|
const tmp = arr[a];
|
|
arr[a] = arr[b];
|
|
arr[b] = tmp;
|
|
};
|
|
const heapify = (i)=>{
|
|
let smallest = i;
|
|
const l = left(i);
|
|
const r = right(i);
|
|
if (l < size && compare(arr[l], arr[smallest]) < 0) {
|
|
smallest = l;
|
|
}
|
|
if (r < size && compare(arr[r], arr[smallest]) < 0) {
|
|
smallest = r;
|
|
}
|
|
if (smallest !== i) {
|
|
swap(smallest, i);
|
|
heapify(smallest);
|
|
}
|
|
};
|
|
const dequeue = ()=>{
|
|
if (size === 0) {
|
|
throw new Error('Priority queue empty');
|
|
}
|
|
const res = arr[0];
|
|
arr[0] = arr[--size];
|
|
heapify(0);
|
|
return res;
|
|
};
|
|
const peek = ()=>{
|
|
if (size === 0) {
|
|
return null;
|
|
}
|
|
return arr[0];
|
|
};
|
|
const enqueue = (item)=>{
|
|
arr[size++] = item;
|
|
let i = size - 1;
|
|
let p = parent(i);
|
|
while(i > 0 && compare(arr[p], arr[i]) > 0){
|
|
swap(p, i);
|
|
i = p;
|
|
p = parent(i);
|
|
}
|
|
};
|
|
const contains = (item)=>{
|
|
const index = arr.indexOf(item);
|
|
return index >= 0 && index < size;
|
|
};
|
|
const remove = (item)=>{
|
|
const i = arr.indexOf(item);
|
|
if (i === -1 || i >= size) {
|
|
return;
|
|
}
|
|
arr[i] = arr[--size];
|
|
heapify(i);
|
|
};
|
|
const clear = ()=>{
|
|
size = 0;
|
|
};
|
|
const all = ()=>{
|
|
return arr.slice(0, size);
|
|
};
|
|
return {
|
|
all,
|
|
clear,
|
|
contains,
|
|
dequeue,
|
|
enqueue,
|
|
peek,
|
|
remove,
|
|
size: ()=>size
|
|
};
|
|
}
|