Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 1x 5x 1x 11x 34x 5x 11x 2x 5x 7x 8x 8x 8x 7x 1x 1x 1x 5x 3x 4x 11x 11x 7x 6x 7x 7x 7x | import { swap } from "@benneq/array";
import { Comparator } from "@benneq/comparator";
/**
* A queue that sorts its values by priority.
*/
export interface PriorityQueue<T> {
/**
* Returns the number of values in this queue
*/
get size(): number;
/**
* Adds a value to this queue
*
* @param value - the value to add
*/
add(value: T): void;
/**
* Returns the first value of this queue.
*
* @returns - the first value, or `undefined` if queue is empty
*/
peek(): T | undefined;
/**
* Removes the first value from this queue and returns it.
*
* @returns - the first value, or `undefined` if queue is empty
*/
poll(): T | undefined;
}
/**
* Creates a new {@link PriorityQueue} that orders its values using a
* {@link Comparator}.
*
* @param comparator - the {@link Comparator} to use
* @returns - the created {@link PriorityQueue}
*/
export const priorityQueue: {
<T>(comparator: Comparator<T>): PriorityQueue<T>;
} = <T>(
comparator: Comparator<T>,
// internal variables:
heap: T[] = [],
isGreater = (a: number, b: number) =>
comparator(heap[a] as T, heap[b] as T) > 0,
size = () => heap.length
): PriorityQueue<T> => {
const siftUp: () => void = (
node = size() - 1,
parent = ((node + 1) >>> 1) - 1
) => {
for (
;
node && isGreater(node, parent);
node = parent, parent = ((node + 1) >>> 1) - 1
) {
swap(node, parent)(heap);
}
};
const siftDown: () => void = (s = size(), node = 0) => {
for (;;) {
const leftNode = 2 * node + 1;
const rightNode = leftNode + 1;
if (
(leftNode >= s || isGreater(node, leftNode)) &&
(rightNode >= s || isGreater(node, rightNode))
) {
break;
}
const maxChild =
rightNode < s && isGreater(rightNode, leftNode) ? rightNode : leftNode;
swap(node, maxChild)(heap);
node = maxChild;
}
};
return {
get size() {
return size();
},
peek() {
return heap[0];
},
add(value) {
heap.push(value);
siftUp();
},
poll(value = heap[0]) {
if (size()) {
swap(0, size() - 1)(heap);
}
heap.pop();
siftDown();
return value;
},
};
};
|