什么是优先级
优先级通常被表示成一个 可以比较 的数值；有的时候数值越大，优先级越高；有时候数值越小，优先级越高；
很多场景下我们只需要知道当前优先级最高的那个元素，不需要维护所有的元素的优先级；
在数据动态变化的场景下，每一次都排序就会很耗时，优先队列就是一个刚刚好的数据结构，在动态的场景下，高效地选取优先级最高的元素；
完全二叉树的特点
完全二叉树有个重要的性质：它 可以使用数组表示；
这是因为按照从上至下、从左至右的顺序给完全二叉树编号，任意结点的父亲结点和子结点的下标是有规律的；
这一点决定了，在完全二叉树中，左右子结点、父结点可以根据当前下标数值 互相访问：
- 根据父亲结点的下标，可以访问到它的两个子结点；
- 根据子结点的下标，可以访问到它的唯一的父亲结点；
使用数组存放二叉树的优点是：不用维护左右子结点、父结点的引用关系；
从下标 0 开始存储数据
父节点索引：parentInx = (i - 1)/2
左孩子节点：leftChildInx = 2 * i +1
右孩子节点：rightChildInx = 2 * i +2
从下标 1 开始存储数据
父节点索引：parentInx = i/2
左孩子节点：leftChildInx = 2 * i
右孩子节点：rightChildInx = 2 * i + 1
堆有序、堆的分类
-
最大堆 也叫做 大顶堆、大根堆 ，任一节点的数值都大于等于它的两个孩子节点的数值；
![]( "大顶堆")
-
最小堆 也叫做 小顶堆、小根堆 ，任一节点的数值都小于等于它的两个孩子节点的数值；
![]( "小顶堆")
构建大顶堆（迭代数组）
需要将数组中的元素 一个接一个地 放进堆中，才能得到一个堆有序的数组
构建图解
基本操作
| 返回值 | 方法名 | 方法描述 |
|---|---|---|
| void | MaxHeap(number N) |
初始化 N 空间大小的大顶堆 |
| number | size | 返回优先队列中元素的个数 |
| void | offer(number x) |
元素 x 入队的时候，先放在二叉堆的末尾，然后向上逐层调整它的位置 |
| number | poll() |
堆顶元素出队的时候，先把二叉堆 末尾 的元素放在根结点，然后逐层向下调整它的位置 |
| number | peek() |
返回队首元素 |
| void | replace(number x) |
将当前队首元素替换成为 x |
代码实现
class Heap {
private _data: number[];
private _capacity: number;
private compare: (a: number, b: number) => boolean;
constructor(capacity, compare = (a, b) => a < b) { // 默认最大堆
this._data = [0]; // 数据从 1 开始存储
this._capacity = capacity;
this.compare = compare || ((a, b) => a < b);
}
// 当前最大堆中真正存储的元素的个数
get size() {
return this._data.length - 1;
}
/**
* 返回队首元素
* @returns
*/
peek() {
// 下标 0 不存元素
return this._data[1];
}
/**
* 入队
* @param item
*/
offer(item: number) {
if (this.size + 1 > this._capacity) {
return
}
// 把新添加的元素放在数组的最后一位
this._data.push(item);
// 将 入队 的元素上移到合适的位置
this.siftUp(this.size);
}
/**
* 元素上浮
* @param k 索引
*/
siftUp(k: number) {
// 有下标就要考虑索引越界的情况，已经在下标 1 的位置，就没有必要上移了
while (k > 1 && this.compare(this._data[this.parent(k)], this._data[k])) {
this.swap(this.parent(k), k);
k = this.parent(k);
}
}
/**
* 元素上浮，与 siftUp() 方法等价
* @param k 索引
*/
shiftUp(k: number) {
// 编写方式等价于「插入排序」的优化，先暂存，再逐个移动，最后空出位置把先前暂存元素放进去
const temp = this._data[k];
while (k > 1) {
if (this.compare(this._data[this.parent(k)], temp)) {
this._data[k] = this._data[this.parent(k)];
k /= 2;
} else {
break;
}
}
this._data[k] = temp;
}
/**
* 堆顶元素出队
* @returns
*/
poll() {
const res = this.peek(); // 队首元素
// 把最后一个元素的值赋值到二叉堆的根结点
this.replace(this._data.pop());
return res;
}
/**
* 元素下沉
* @param k 索引
*/
siftDown(k: number) {
// 只要它有孩子，注意这里使用等于号，是因为真正存数据的下标从 1 开始
while (this.leftChild(k) <= this.size) {
// 1. 拿到左右节点的最大值
let leftChildInx = this.leftChild(k);
let rightChildInx = this.rightChild(k);
if (rightChildInx <= this.size && this.compare(this._data[leftChildInx], this._data[rightChildInx])) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (this.compare(this._data[leftChildInx], this._data[k])) {
break;
}
// 3. 交换位置后，继续下沉操作
this.swap(k, leftChildInx);
k = leftChildInx; // 更新位置
}
}
/**
* 元素下沉，与 siftDown() 方法等价
* @param k 索引
*/
shiftDown(k: number) {
// 编写方式等价于「插入排序」的优化，先暂存，再逐个移动，最后空出位置把先前暂存元素放进去
let temp = this._data[k];
while (this.leftChild(k) <= this.size) {
// 1. 拿到左右节点的最大值
let leftChildInx = this.leftChild(k);
let rightChildInx = this.rightChild(k);
if (rightChildInx <= this.size && this.compare(this._data[leftChildInx], this._data[rightChildInx])) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (this.compare(this._data[leftChildInx], temp)) {
break;
}
// 3. 依次后移，继续下沉操作
this._data[k] = this._data[leftChildInx];
k = leftChildInx; // 更新位置
}
this._data[k] = temp;
}
/**
* 指定元素替换到队首
* @param item
*/
replace(item: number) {
this._data[1] = item;
this.siftDown(1);
}
/**
* 获取左边孩子节点索引
* @param k
* @returns
*/
leftChild(k: number) {
return k * 2;
}
/**
* 获取右边孩子节点索引
* @param k
* @returns
*/
rightChild(k: number) {
return k * 2 + 1;
}
/**
* 获取父节点索引
* @param k
* @returns
*/
parent(k: number) {
return k >> 1;
}
/**
* 交换位置
* @param i 索引
* @param j 索引
*/
swap(i: number, j: number) {
[this._data[i], this._data[j]] = [this._data[j], this._data[i]];
}
}
构建大顶堆（转化数组）
直接将数组整理成堆有序的样子,这种操作称为 Heapify（堆化）
自顶向下
-
从这个二叉堆的第 2 个结点开始，依次执行
元素上浮操作即可，其实这和一个接一个把数组元素添加到一个最大堆中是等价的；
![]( "自顶向下")
-
时间复杂度：
0(NlogN) -
关键代码：
class Heap { private _data: number[]; private _capacity: number; private compare: (a: number, b: number) => boolean; constructor(nums: number[], capacity: number, compare = (a, b) => a < b) { this._data = [0, ...nums]; // 数据从 1 开始存储 this._capacity = capacity; this.compare = compare || ((a, b) => a < b); for (let index = 2; index < this._data.length; index++) { this.siftUp(index); } } // ... }
自底向上（推荐）
-
从这个二叉堆的第 1 个非叶子结点处开始（一下子跳过整棵树一半以上的元素），自底向上依次执行
下沉操作，向下调整；
![]( "自底向上")
-
时间复杂度：
0(N)，证明过程可以看 bilibili 爱学习的饲养员 -
关键代码：
class Heap { private _data: number[]; private _capacity: number; private compare: (a: number, b: number) => boolean; constructor(nums: number[], capacity: number, compare = (a, b) => a < b) { this._data = [0, ...nums]; // 数据从 1 开始存储 this._capacity = capacity; this.compare = compare || ((a, b) => a < b); // 从 1 开始编号的堆最后一个非叶子结点的下标是 size/2 （画图就可以观察出来） for (let index = this._data.length >> 1; index >= 1; index--) { this.siftDown(index); } } // ... }
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 散列表
上一篇
评论
