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 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | 44x 44x 92x 44x 50x 44x 16x 16x 9x 44x 175x 175x 175x 175x 175x 174x 44x 149x 149x 149x 149x 141x 141x 52x 89x 89x 44x 85x 85x 85x 85x 85x 56x 56x 34x 56x 10x 10x 44x 3x 1x 2x 44x 104x 104x 103x 103x 103x 103x 103x 1x 44x 76x 75x 75x 75x 75x 44x 48x 1x 47x 47x 1x 46x 46x | // A PriorityQueue is a queue that can be sorted by priority.
export default class PriorityQueue<T = string> {
/**
* @description The internal data structure.
* @description.zh-CN 内部数据结构。
*/
private arr: { key: T; priority: number }[] = [];
/**
* @description the index indiced by the key.
* @description.zh-CN 通过 key 找到的索引。
*/
private keyIndice = new Map<T, number>();
/**
* @description The number of elements in the queue.
* @description.zh-CN 队列中元素的数量。
*/
size = () => this.arr.length;
/**
* @description all the keys in the queue.
* @description.zh-CN 队列中所有的 key。
*/
keys = () => this.arr.map((e) => e.key);
/**
* @description does the queue contain the key?
* @description.zh-CN 队列中是否包含 key？
* @param key
* @returns
*/
has = (key: T) => this.keyIndice.has(key);
/**
* @description get the priority of the key.
* @description.zh-CN 获取 key 的优先级。
* @param key
* @returns
*/
priority = (key: T) => {
const index = this.keyIndice.get(key);
if (index !== undefined) {
return this.arr[index].priority;
}
};
/**
* @description swap the index of two keys.
* @description.zh-CN 交换两个 key 的索引。
* @param i
* @param j
*/
private swap = (i: number, j: number) => {
const { arr, keyIndice } = this;
const [originI, originJ] = [arr[i], arr[j]];
arr[i] = originJ;
arr[j] = originI;
keyIndice.set(originI.key, j);
keyIndice.set(originJ.key, i);
};
/**
* @description decrease the priority of the key by index
* @description.zh-CN 通过索引减小 key 的优先级。
* @param index
*/
private innerDecrease = (index: number) => {
const { arr } = this;
const priority = arr[index].priority;
let parent;
let i = index;
while (i !== 0) {
parent = i >> 1;
if (arr[parent]?.priority < priority) {
break;
}
this.swap(i, parent);
i = parent;
}
};
/**
* @description create heap from the array by index
* @description.zh-CN 通过索引创建堆。
* @param i
*/
private heapify = (i: number) => {
const { arr } = this;
const l = i << 1;
const r = l + 1;
let largest = i;
if (l < arr.length) {
largest = arr[l].priority < arr[largest].priority ? l : largest;
if (r < arr.length) {
largest = arr[r].priority < arr[largest].priority ? r : largest;
}
if (largest !== i) {
this.swap(i, largest);
this.heapify(largest);
}
}
};
/**
* @description the key with min priority in the queue.
* @description.zh-CN 队列中优先级最小的 key。
* @returns
*/
min = () => {
if (this.size() === 0) {
throw new Error('Queue underflow');
}
return this.arr[0].key;
};
/**
* @description insert a key with priority.
* @description.zh-CN 用优先级插入一个 key。
* @param key
* @param priority
* @returns
*/
add = (key: T, priority: number) => {
const { keyIndice, arr } = this;
// if the key is already in the queue, update the priority
if (!keyIndice.has(key)) {
const index = arr.length;
keyIndice.set(key, index);
arr.push({
key,
priority,
});
this.innerDecrease(index);
return true;
}
return false;
};
/**
* @description remove the key with min priority and return the key.
* @description.zh-CN 删除优先级最小的 key，并返回 key。
* @returns
*/
removeMin = () => {
this.swap(0, this.arr.length - 1);
const min = this.arr.pop()!;
this.keyIndice.delete(min.key);
this.heapify(0);
return min.key;
};
/**
* @description decrease the priority of the key.
* @description.zh-CN 通过 key 减小 key 的优先级。
* @param key
* @param priority
*/
decrease = (key: T, priority: number) => {
if (!this.has(key)) {
throw new Error(`There's no key named ${key}`);
}
// there must be an index
const index = this.keyIndice.get(key)!;
if (priority > this.arr[index].priority) {
throw new Error(
`New priority is greater than current priority.Key: ${key} Old: + ${this.arr[index].priority} New: ${priority}`,
);
}
this.arr[index].priority = priority;
this.innerDecrease(index);
};
}
|