基本思想
本节采用的是 堆化 构建大顶堆；
- 前置知识请看 算法基础🔮 优先级队列
- 先构建 大顶堆/小顶堆 ，再对 构建好的堆 依次出队，就是排好序的序列；
大顶堆图解
复杂度
-
时间复杂度：
O(NlogN)，其中：- N 是数组的长度，构建 大顶堆 的时间复杂度为
O(N)； - 建完堆以后需要进行 N−1 次调整，每次调整的时间复杂度为
O(logN)；
- N 是数组的长度，构建 大顶堆 的时间复杂度为
-
空间复杂度：
O(1)，只需要常数变量
代码实现
class MaxHeap {
private _data: number[];
constructor(nums: number[], capacity: number) {
this._data = [0, ...nums]; // 数据从 1 开始存储
// 从 1 开始编号的堆最后一个非叶子结点的下标是 size/2 （画图就可以观察出来）
for (let index = this._data.length >> 1; index >= 1; index--) {
this.siftDown(index);
}
}
// 当前最大堆中真正存储的元素的个数
get size() {
return this._data.length - 1;
}
isEmpty() {
return this.size < 0;
}
/**
* 返回队首元素
* @returns
*/
peek() {
if (this.isEmpty()) {
return
}
// 下标 0 不存元素
return this._data[1];
}
/**
* 堆顶元素出队
* @returns
*/
poll() {
if (this.size == 0) {
return
}
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._data[leftChildInx] < this._data[rightChildInx]) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (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._data[leftChildInx] < this._data[rightChildInx]) {
leftChildInx = rightChildInx;
}
// 2. k 满足大顶堆，什么都不做
if (temp >= this._data[leftChildInx]) {
break;
}
// 3. 依次后移，继续下沉操作
this._data[k] = this._data[leftChildInx];
k = leftChildInx; // 更新位置
}
this._data[k] = temp;
}
/**
* 指定元素替换到队首
* @param item
*/
replace(item: number) {
if (this.isEmpty()) {
return
}
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]];
}
}
function heapSort(nums) {
var maxHeap = new MaxHeap(nums, 10);
for (var inx = nums.length - 1; inx >= 0; inx--) {
nums[inx] = maxHeap.poll();
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 快速排序
上一篇
评论
