前言
优先队列本身就是一种队列。
普通队列：先进先出、后进后出，如排队买票吃饭一样。
优先队列：出队顺序和入队顺序无关，和优先级相关。如去医院看病，床位非常的紧张，需要排队才能去做手术的话，此时做手术的这个队伍的顺序就是一个优先队列。因为医生是根据每一个患者的病症的不同以及需要这个手术的紧急程度的不同来去安排谁先做手术谁后做手术，也可以认为每一个患者是有一个优先级的。优先级高者先得，这样的一个队列就叫做优先队列，它和普通队列最主要的区别是在于出队这个操作上，入队很简单，但是优先级高的先出队。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
优先队列(PriorityQueue)
优先队列的应用
在计算机的世界中优先队列的使用也是非常多的。例如操作系统中进行任务的调度，现在的操作系统中会同时执行多个任务，操作系统就要为这多个任务分配计算资源，包括去分配 cpu 的时间片，具体去分配这些资源的时候。操作系统就要看各个任务的优先级，然后动态的去选择优先级最高的任务来执行。
这个动态很重要，如果任务数量是固定的，那么就不需要去制作新的数据结构来处理这个问题，那么这个过程就只需要一个排序算法而并不是一个优先队列。
通常实际情况不是这样的，假设有一个任务处理中心，有三个任务请求过来，那么这个时候任务处理中心就需要去找出优先级最高的那个请求，然后对这个任务进行相应的处理，但是处理完这个任务的同时，很有可能就来了很多新的任务请求，这就是动态的意思。
并不能够在一开始就确定任务中心一共需要处理多少个任务，其实医生是不知道每天或者每个月每个季度每一年要来多少患者，它要随时根据新来的患者的情况来调整整个队列的优先级，这就是动态的意思。
而不是一开始任务中心就知道所有的任务是什么，然后排排序就好了，就像医生也不能一开始就把今年要做的所有的手术都列出来，然后排排序就好了。随着时间的推移会不停的有新的元素入队，也就是队列中的元素是在不断的变化的，所以必须使用优先队列这样的数据结构来解决这个问题，而不仅仅是按照优先级排序。
比如做一个简单的 AI。这个 AI 要自动的帮你打怪，其实 AI 也没有那么高级，在很多游戏的底层本身就存在这样的 AI。比如说在一个即时战略的游戏中，当你创建了己方军队的时候，当然可以通过自己的操作来指挥己方的军队去攻击哪些敌人，但是你不去指定，当敌方军队接近己方军队的时候，己方军队也会自动的去攻击敌方军队。这也叫做一个 AI，这种 AI 其实是非常常见的，这种时候 AI 可能同时面对不同的敌人，那么它就需要选择优先去打那种敌人，在这种情况下就需要使用优先队列，其实就是去打威胁程度最高的敌人，也就是去打优先级最高的那个敌人。
优先级的高低是可以定义的，可能是最强悍的那个敌人、也有可能是最弱小的敌人、也有可能是距离你最近的敌人等等。AI 自动打怪中的优先队列也是动态的处理敌人，因为敌人是不断的在接近你，在每一时刻 AI 都需要考虑新的敌人的出现，因为新的敌人可能是优先级更高的需要被打击的目标，这就是一个动态的过程，所以才需要使用优先队列。
实现优先级队列的时候是不用去管优先高低的，当用户具体去使用的时候，才会去定义优先级。
优先队列的实现思路
实现的时候与普通队列的实现会有些区别，主要区别在于出队操作和获取队首元素操作上，因为出队元素是优先级最高的元素，队首的元素也是优先级最高的元素，并不是普通队列那样的选择最早进入队列的元素。
对于优先队列这样的数据结构，也是可以使用不同的底层实现的，可以使用最基础的普通线性数据结构和顺序线性结构来实现，也可以使用堆来进行实现。
两种基础实现优先队列思路
使用普通的线性结构，入队为O(1)级别的操作出队需要扫描一遍线性结构中所有的元素，从而找出其优先级最高的那个元素，然后把它拿出队列，所以为O(n)级别的操作，如果某一操作为O(n)级别的操作，那么就会大大的降低整个数据结构的效率。所以普通线性结构的实现方式性能方面会很不好。
顺序线性结构，整个线性结构维持所有元素的顺序，整个线性数据结构都是从小到大或者从大到小排列的，在这种情况下出队将变得非常的容易，出队会是O(1)级别的操作。
因为只需要拿出当前这个数据结构队首或者队尾的那个元素就好了，那么入队的时候就会是一个O(n)级别的操作了，在入队的时候需要找到这个元素在线性结构中应该插入的位置。这个找到合适插入位置的操作需要O(n)的复杂度，在最差的情况就需要将整个线性数据结构都扫描一遍，所以顺序线性结构在出队的操作上是O(1)的复杂度，但是在入队的操作上是O(n)的复杂度。
所以无论是普通的线性结构还是顺序的线性结构，它们都有一定的劣势，都会存在一个操作是O(n)级别的操作，它们都不够好。
可以使用动态数组、链表这样的底层实现来进行优先队列的实现。虽然这样实现出来的优先队列，可能实际不会去应用，但是也是一个很好的练习，可以深入的理解队列这样抽象的数据结构。
在这个基础上限制它的性质，就创建出了优先队列这个概念，具体在实现优先队列这个概念的时候，还可以使用不同的底层实现，这在数据结构领域是非常重要的思想。
使用堆来实现优先队列思路
使用堆这种数据结构，入队操作和出队操作都是O(logn)这种级别的操作，而且它和二分搜索树不同，二分搜索树是在平均情况下是O(logn)的时间复杂度，而堆是在最差的情况下是O(logn)的时间复杂度，这也使得堆这种数据结构是相当高效的。
它和前面两种基础的实现方式有着天壤之别。
使用堆来实现优先队列
优先队列即可以使用普通的线性数据结构来实现，如 动态数组、链表。优先队列也可以使用一个维护顺序的线性数据结构来实现，如 动态数组、链表。
队列的接口是完全一致的，同时它们的功能也是一样的。只不过用的底层的数据结构是不同的，这样就会导致一些方法在时间复杂度上产生不同的效果，在使用普通数组的时候入队这个操作是O(1)的复杂度，但是出队的那个操作，寻找那个最大值就是O(n)的复杂度。
如果使用顺序的线性结构的时候，那会有点相反，入队会变成O(n)的复杂度，因为要找到待插入的这个元素的正确位置，出队会是O(1)的复杂度。
MyQueue
void enqueue(e) E dequeue() E getFront() int getSize() boolean isEmpty()
MyPriorityQueue
代码示例
(class: Myarray, class: MaxHeap, class: MyPriorityQueue)
Myarray
// 自定义类
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// 新增： 交换两个索引位置的变量 2018-11-6
swap(indexA, indexB) {
if (
indexA < 0 ||
indexA >= this.size ||
indexB < 0 ||
indexB >= this.size
)
throw new Error('Index is Illegal.'); // 索引越界异常
let temp = this.data[indexA];
this.data[indexA] = this.data[indexB];
this.data[indexB] = temp;
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MaxHeap
// 自定义二叉堆之最大堆 Heap
class MyMaxHeap {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 添加操作
add(element) {
// 追加元素
this.myArray.push(element);
// 将追加的元素上浮到堆中合适的位置
this.siftUp(this.myArray.getSize() - 1);
}
// 堆的上浮操作 -
siftUp(index) {
this.nonRecursiveSiftUp(index);
// this.recursiveSiftUp(index);
// 无论是递归还是非递归都有一个
// 元素上浮后结束的条件 当前节点元素值 小于其父节点元素值
// 和
// 索引即将越界的终止条件 要上浮的元素索引 小于等于0
}
// 堆的上浮操作 递归算法 -
recursiveSiftUp(index) {
// 解决最基本的问题， 递归终止条件
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
// 递归写法
if (this.compare(currentValue, parentValue) > 0) {
this.swap(index, parentIndex);
this.recursiveSiftUp(parentIndex);
}
}
// 堆的上浮操作 非递归算法 -
nonRecursiveSiftUp(index) {
if (index <= 0) return;
let currentValue = this.myArray.get(index);
let parentIndex = this.calcParentIndex(index);
let parentValue = this.myArray.get(parentIndex);
while (this.compare(currentValue, parentValue) > 0) {
// 交换堆中两个元素位置的值
this.swap(index, parentIndex);
// 交换了位置之后，元素上浮后的索引变量也要进行相应的变更
index = parentIndex;
// 如果索引小于等于0了 那就结束循环
if (index <= 0) break;
currentValue = this.myArray.get(index);
parentIndex = this.calcParentIndex(index);
parentValue = this.myArray.get(parentIndex);
}
}
// 找到优先级最大的元素 （查找元素）操作
findMax() {
if (this.myArray.isEmpty())
throw new Error('can not findMax when heap is empty.');
return this.myArray.getFirst();
}
// 提取优先级最大的元素（删除元素）操作
extractMax() {
// 获取堆顶的元素
let maxElement = this.findMax();
// 获取堆底的元素
let element = this.myArray.getLast();
// 让堆底的元素替换掉堆顶的元素
this.myArray.set(0, element);
// 移除堆底的元素
this.myArray.pop();
// 让堆顶的元素开始下沉，从而能够正常满足堆的性质
this.siftDown(0);
// 返回堆顶的元素
return maxElement;
}
// 堆的下沉操作 -
siftDown(index) {
this.nonRecursiveSiftDown(index);
// this.recursiveSiftDown(index);
}
// 堆的下沉操作 递归算法
recursiveSiftDown(index) {
// 递归终止条件
// 如果当前索引位置的元素没有左孩子就说也没有右孩子，
// 那么可以直接终止，因为无法下沉
if (this.calcLeftChildIndex(index) >= this.myArray.getSize()) return;
let leftChildIndex = this.calcLeftChildIndex(index);
let leftChildValue = this.myArray.get(leftChildIndex);
let rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
// let maxIndex = 0;
// if (rightChildIndex >= this.myArray.getSize())
// maxIndex = leftChildIndex;
// else {
// rightChildValue = this.myArray.get(rightChildIndex);
// if (this.compare(rightChildValue, leftChildValue) > 0)
// maxIndex = rightChildIndex;
// else
// maxIndex = leftChildIndex;
// }
// 这段代码是上面注释代码的优化
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) < 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
// 交换位置
this.swap(maxIndex, index);
// 继续下沉
this.recursiveSiftDown(maxIndex);
}
}
// 堆的下沉操作 非递归算法 -
nonRecursiveSiftDown(index) {
// 该索引位置的元素有左右孩子节点才可以下沉，
// 在完全二叉树中 如果一个节点没有左孩子必然没有右孩子
while (this.calcLeftChildIndex(index) < this.myArray.getSize()) {
let leftChildIndex = this.calcLeftChildIndex(index);
let leftChildValue = this.myArray.get(leftChildIndex);
let rightChildIndex = this.calcRightChildIndex(index);
let rightChildValue = null;
let maxIndex = leftChildIndex;
if (rightChildIndex < this.myArray.getSize()) {
rightChildValue = this.myArray.get(rightChildIndex);
if (this.compare(leftChildValue, rightChildValue) < 0)
maxIndex = rightChildIndex;
}
let maxValue = this.myArray.get(maxIndex);
let currentValue = this.myArray.get(index);
if (this.compare(maxValue, currentValue) > 0) {
this.swap(maxIndex, index);
index = maxIndex;
continue;
} else break;
}
}
// 将堆顶的元素用一个新元素替换出来
replace(element) {
let maxElement = this.findMax();
this.myArray.set(0, element);
this.siftDown(0);
return maxElement;
}
// 将一个数组变成一个最大堆 -
heapify(array) {
// 将数组中的元素添加到自定义动态数组里
for (const element of array) this.myArray.push(element);
// 减少一个O(n)的操作，不然性能相对来说会差一些
// this.myArray.data = array;
// this.myArray.size = array.length;
// 这个动态数组满足了一棵完全二叉树的性质
// 获取 这棵完全二叉树 最后一个非叶子节点的索引
let index = this.calcParentIndex(this.myArray.getSize() - 1);
// 从最后一个非叶子节点开始遍历 从后向前遍历 不停的下沉， 这个就是heapify的过程
// for (let i = index; i >= 0; i --) { this.siftDown(i);}
while (0 <= index) this.siftDown(index--);
}
// 堆中两个元素的位置进行交换
swap(indexA, indexB) {
this.myArray.swap(indexA, indexB);
}
// 辅助函数 计算出堆中指定索引位置的元素其父节点的索引 -
calcParentIndex(index) {
if (index === 0)
// 索引为0是根节点，根节点没有父亲节点，小于0就更加不可以了
throw new Error("index is 0. doesn't have parent.");
return Math.floor((index - 1) / 2);
}
// 辅助函数 计算出堆中指定索引位置的元素其左孩子节点的索引 -
calcLeftChildIndex(index) {
return index * 2 + 1;
}
// 辅助函数 计算出堆中指定索引位置的元素其右孩子节点的索引 -
calcRightChildIndex(index) {
return index * 2 + 2;
}
// 比较的功能 -
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is error. element can't compare.");
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 获取堆中实际的元素个数
size() {
return this.myArray.getSize();
}
// 返回堆中元素是否为空的判断值
isEmpty() {
return this.myArray.isEmpty();
}
}MyPriorityQueue
// 自定义优先队列 PriorityQueue
class MyPriorityQueue {
constructor() {
this.maxHeap = new MyMaxHeap();
}
// 入队
enqueue(element) {
this.maxHeap.add(element);
}
// 出队
dequeue() {
return this.maxHeap.extractMax();
}
// 查看队首元素
getFront() {
return this.maxHeap.findMax();
}
// 查看队列中实际元素的个数
getSize() {
return this.maxHeap.size();
}
// 返回队列是否为空的判断值
isEmpty() {
return this.maxHeap.isEmpty();
}
// 扩展： 修改最大堆中的比较算法
updateCompare(compareMethod) {
// 传入参数可以替换掉原堆中实现的compare方法
this.maxHeap.compare = compareMethod;
}
// 扩展： 用一个新元素去替换队首的元素，同时再次确认优先级别
replaceFront(element) {
// 这样就就可 不需要 出队入队操作这么麻烦了
return this.maxHeap.replace(element);
}
}总结
这个优先队列是基于前面实现的自定义数组和自定义堆，所以还是用来学习数据结构的算法实现思想的噢。队列的功能基本如下了：
Queue
void enqueue(e) E dequeue() E getFront() int getSize() boolean isEmpty()
一般来说只要支持这样的接口或者支持入队或者出队操作，它就可以叫做一个队列。这么定义一个队列的话，那么队列这个概念就很广义了，如普通队列（先到先得）、优先队列（优先级最高的先出队），如此一来，栈其实也可以理解是一个队列。
入栈和出栈操作也是向一个数据结构添加元素和拿出元素，所以栈也可以理解成是一个队列，事实上当你这么理解的时候，对于很多计算机算法，你理解的角度将会产生新的变化。最典型的例子如二分搜索树，实现了一个非递归的前序遍历、层序遍历，这两个算法基本的逻辑是完全一样的。
区别只在于一个使用的栈一个使用的队列，当你把栈也看做队列的时候，这两种方式非常完美的统一了，对于这两种遍历方式来说，它们的区别在于你使用了怎样的数据结构，而不是具体的逻辑，这个具体的逻辑其实是一致的。
在慕课网《看的见的算法》中第五章第 9 节有讲深度优先遍历与广度优先遍历的内在联系，这个内在联系就是这两种遍历逻辑是一致的，本质的区别在使用了怎样的数据结构。正是因为有这样的内在联系，就可以生成一个随机迷宫的算法，这个随机迷宫生成的算法使用了是一个自定义的随机队列。
看的见的算法讲的是一些有趣的能够实际应用的小 demo，算法和数据结构不仅仅只是面试和做题，它除了能够做很多计算机科学领域高大上的事情。例如人工智能、游戏 AI、数据库、操作系统等等，还可以做出很多小而美的有趣的可以发现计算机乐趣的小的 demo。
拓展
优先队列的经典问题
在1,000,000个元素中选出前 100 名？
也就是在 N 个元素中选出前 M 个元素，如果 M 等于 1，那么就是在 N 个元素中就选择第一名的那个元素，只需要遍历一遍就好了，非常的简单，整个算法的时间复杂度是 O(n)级别的。
但是 M 如果不等于 1 的话，那么就有一点棘手。最朴素的想法就是对这一百万个元素进行一下排序，对于一百万这个级别的元素来说，使用高级的排序算法，无论是归并排序也好还是快速排序也好都可以在NlogN的时间里完成任务，整体来说这种时间复杂还是可以接受的，排序完成后直接取出前一百名元素就好了，非常容易。
但是问题的关键在于有没有更好的方法，在这个问题上，如果使用优先队列的话，那么就可以在NlogM这个时间复杂度内解决问题，如果这个 M 等于 100 的话，logM 大概是 7 左右。如果使用高级的排序算法，在NlogN这个时间复杂度内的话，那么 logN 大概是 20。这样一来它们相差了三倍左右，所以 NlogM 是比 NlogN 更好的时间复杂度。
使用优先队列，维护当前看到的前 M 个元素。对于这 100 万个元素，肯定是要从头到尾扫描一遍，在扫描的过程中，首先将这 N 个元素中的前 M 个元素放入优先队列中。
之后每次看到一个新的元素，如果这个新的元素比当前优先队列中最小的元素还要大，那么就把优先队列中最小的那个元素给扔出去，取而代之的换上这个新的元素。
用这样的方式，相当于这个优先队列中一直维护者当前可以看到的前 M 个元素，直到把这 n 个元素全都扫描完，在优先队列中最终留下来的这 M 个元素，就是最终要求的结果。
实际需要的是一个最小堆 MinHeap，要能够非常快速的取出当前看到前 M 个元素中最小的那个元素，需要不断的将当前可以看到的前 M 大的元素中最小的元素进行替换，已经实现了最大堆 MaxHeap，你只需要把这个逻辑改一改，把它变成一个最小堆 MinHeap 是非常容易的，就是将核心逻辑比较的时候符号进行一个改变。
实际上解决这个问题并不需要真的使用最小堆 MinHeap，依然使用最大堆也是可以的，这里面最关键的怎么去定义优先级。优先级的大小，没有谁规定最大的元素优先级就是最高的，这个问题的解决方案中，每次都是去取出这个优先队列中最小的元素，那么就完全可以自己去定义。例如元素的值越小，它的优先级越高，在这样的一个定义下，依然可以使用底层以最大堆实现的优先队列了，大和小其实是相对的。
leetcode 347.前K个高频元素
https://leetcode-cn.com/problems/top-k-frequent-elements/。
可以使用 系统内置的 Map 来统计频率，然后使用 PriorityQueue 来进行频率的优先级统计，由于自己实现的自定义优先队列是以一个最大堆为底层实现，那么入队的元素的比较操作需要相。要支持的是，频次越低优先级就越高，那么当当前元素的频次越低，就让它在堆的最顶端。
那么 compareTo 操作时，返回的值为正数则会进行向上浮动，返回的值如果为负数则会进行下沉。
// 答题
class Solution {
// leetcode 347. 前K个高频元素
topKFrequent(nums, k) {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
* 原版
*/
var topKFrequent = function(nums, k) {
let map = new Map();
// 统计 数组中每一个元素出现频率
for (const num of nums) {
if (map.has(num)) map.set(num, map.get(num) + 1);
else map.set(num, 1);
}
// 优先队列：使用的时候指定优先级比较的方式
let queue = new MyPriorityQueue();
// 变更优先队列中的定义优先级的方法
queue.updateCompare((elementA, elementB) => {
// 原的比较算法是 值越大 优先级越大
// 现在改为 值越小 优先级越大
if (elementA.value < elementB.value) return 1;
else if (elementA.value > elementB.value) return -1;
else return 0;
});
for (const key of map.keys()) {
if (queue.getSize() < k)
queue.enqueue({ key: key, value: map.get(key) });
else if (map.get(key) > queue.getFront().value) {
queue.replaceFront({ key: key, value: map.get(key) });
// queue.dequeue();
// queue.enqueue({"key": key, "value": map.get(key)});
}
}
let result = [];
for (var i = 0; i < k; i++) {
result.push(queue.dequeue().key);
}
return result;
};
// 精简版
var topKFrequent = function(nums, k) {
let map = new Map();
// 统计 数组中每一个元素出现频率
for (const num of nums) {
if (map.has(num)) map.set(num, map.get(num) + 1);
else map.set(num, 1);
}
// 优先队列：使用的时候指定优先级比较的方式
let queue = new MyPriorityQueue();
// 变更优先队列中的定义优先级的方法
queue.updateCompare((keyA, keyB) => {
// 原的比较算法是 值越大 优先级越大
// 现在改为 值越小 优先级越大
if (map.get(keyA) < map.get(keyB)) return 1;
else if (map.get(keyA) > map.get(keyB)) return -1;
else return 0;
});
for (const key of map.keys()) {
if (queue.getSize() < k) queue.enqueue(key);
else if (map.get(key) > map.get(queue.getFront())) {
queue.replaceFront(key);
}
}
let result = [];
for (var i = 0; i < k; i++) {
result.push(queue.dequeue());
}
return result;
};
return topKFrequent(nums, k);
}
}
// main 函数
class Main {
constructor() {
this.alterLine('leetcode 347. 前K个高频元素');
let s = new Solution();
let arr = [
5,
-3,
9,
1,
7,
7,
9,
10,
2,
2,
10,
10,
3,
-1,
3,
7,
-9,
-1,
3,
3
];
console.log(arr);
this.show(arr);
let result = s.topKFrequent(arr, 3);
console.log(result);
this.show(result);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};
