重学数据结构与算法 - 堆排序
『22年11月19日』
之前学到二叉堆的时候,发现可以利用二叉堆来做排序算法。其基本原理就是利用其堆顶元素为数组的最大值或者最小值的特性,截取堆顶元素后再重新调整为最大或最小堆,最后按顺序截取的堆顶元素就是一个升序序列或将序序列。
堆化算法
移除堆顶元素,将堆的最后一个元素移动到堆顶,从堆顶开始调整堆,直到合适的位置。
算法思路
- 构建一个最大堆,堆顶元素为最大值;
- 交换堆顶元素和堆的最后一个元素,标记最后的元素为堆化截止点;
- 调整堆为最大堆,直到堆化截止点;
- 交换堆顶元素和上次的堆化截止点,重新调整截止点;
- 重复 2-3 步骤;
- 直到截止点为 1;
堆类型选择
- 升序排序 => 最大堆
- 降序陪序 => 最小堆
代码实现
// 升序排序 - 最大堆
class MaxHeap {
constructor() {
this.heap = [];
}
insert(val) {
const { heap } = this;
heap.push(val);
if (heap.length > 1) {
this._siftUp(heap.length - 1);
}
}
_siftUp(index) {
const { heap } = this;
const parent = this.parent(index);
if (parent === undefined) return;
if (heap[parent] < heap[index]) {
[heap[parent], heap[index]] = [heap[index], heap[parent]];
this._siftUp(parent);
}
}
sort() {
const { heap } = this;
let length = heap.length - 1;
while (length > 0) {
[heap[0], heap[length]] = [heap[length], heap[0]];
this._siftDown(0, length);
length--;
}
}
_siftDown(index, last) {
const { heap } = this;
let current = index;
const left = this.leftChild(current);
const right = this.rightChild(current);
if (left >= last || right >= last) return;
if (heap[current] < heap[left]) {
current = left;
}
if (heap[current] < heap[right]) {
current = right;
}
if (current !== index) {
[heap[current], heap[index]] = [heap[index], heap[current]];
this._siftDown(current, last);
}
}
leftChild(index) {
return 2 * index + 1;
}
rightChild(index) {
return 2 * index + 2;
}
parent(index) {
if (index === 0) {
return undefined;
}
return Math.floor((index - 1) / 2);
}
display() {
console.log(this.heap);
}
}
const maxHeap = new MaxHeap();
maxHeap.insert(1);
maxHeap.insert(5);
maxHeap.insert(4);
maxHeap.insert(3);
maxHeap.insert(2);
maxHeap.insert(6);
maxHeap.display();
maxHeap.sort();
maxHeap.display();
应用场景
- 可以用来实现优先队列,比如 React 的 Scheduler 的实现
算法分析
这是一个不稳定算法,因为相同值的元素不能确保排序后位置不变