数据结构——二叉堆
二叉堆是一种特殊的二叉树数据结构。它有以下两个特性：
- 它是一个完全二叉树，即：除了叶子节点，树的每一层都有左侧和右侧子节点；
- 它的最后一层的叶子节点尽可能的都是左侧子节点（当然也可以在右侧，这表明左侧的叶子节点已经满了）；
二叉堆一般有两种：
- 最小堆（或小根堆）：所有的节点都小于或等于它的子节点；
- 最大堆（或大根堆）：所有的节点都大于或等于它的子节点；
二叉堆的算法
本文会实现下面几个二叉堆操作算法：
insert(value)向堆中插入一个元素，插入成功返回 true；isEmpty()判断这个堆是不是空的，为空返回 true；size()返回堆的大小，返回类型是数字；extract()删除堆的根元素（最小堆中最小的节点，最大堆中最大的节点），并返回该元素；findRoot()返回堆的根元素（不做删除操作，而只是返回）；delete(value)删除匹配到堆中的第一个元素，并返回该元素；merge(heap1, heap2, ...)合并堆，合并成功会返回 true；values()返回堆中所有的元素以数组的形式；
使用语言：TypeScript。使用数组来表示出二叉堆（用数组比较好实现）。
准备工作
首先需要了解三个函数。这三个函数可以通过索引检索出父节点，也可以通过父节点的索引检索出子节点。例如下面一个最小二叉堆，可用数组的表示：
最小堆
通过观察可以发现，知道一个节点索引后，它的左、右子节点索引可以很好的求出：
// 获取左子节点
function getLeftIndex(idx: number): number{
return 2 * idx + 1;
}
// 获取右子节点
function getRightIndex(idx: number): number{
return 2 * idx + 2;
}而知道了某个节点的索引也可以很好的求出它父节点的索引：
function getParentIndex(idx: number): number{
return Math.floor((idx - 1) / 2);
}在实现二叉堆过程中，我们还需要下面的交换函数，它用于交换数组中两个元素的位置：
function swap(array: Array<any>, a: number, b: number): void{
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}OK，一切准备就绪，下面开始实现堆的核心方法。
创建最小堆类
先实现一下最小堆，而最大堆的实现基本与最小堆是一样的。首先定义一个抽象类：
abstract class Heap<T>{
abstract insert(value: T): boolean; // 向堆中插入一个元素
abstract extract(): T | undefined; // 移除最小值（最小堆）或最大值（最大堆），并返回这个值
abstract findRootVal(): T | undefined; // 返回最小值（最小堆）或最大值（最大堆），且不会移除这个值
abstract isEmpty(): boolean; // 判断是否为空
abstract size(): number; // 堆的大小
abstract values(): Array<T>; // 以数组的形式返回堆中所有的元素
abstract merge(target: Heap<T>, ...heaps: Array<Heap<T>>): boolean; // 合并两个堆
abstract delete(value: T): T | undefined; // 删除堆中的某个值
}数组中的数据类型是个泛型，在创建实例时我们需要传入具体的类型。
然后是构造最小堆类，让它继承抽象类:
class MinHeap<T> extends Heap<T>{
protected heap: T[]; // 用于存储最小堆的数组，用该数组映射出最小堆
constructor(){
super();
this.heap = [];
// ...
}
}然后开始实现我们定义的各个方法。
insert
往堆中插入新项。
思路：先把这个新的值放入数组的末端，然后对这个元素进行“上浮”操作。插入末端后我们可以拿到这个元素的索引，通过索引可以获取到它父元素的索引（使用上面的 getParentIndex 方法），然后拿父元素与该元素做对比，当父元素比这个新元素值大时，就交换这两个元素（因为在最小堆中，父节点总比子节点值要小）；如果该元素不小于它的父元素就不做任何操作，因为这符合最小堆的特点。
class MinHeap<T> extends Heap<T>{
protected heap: T[];
constructor(){
super();
this.heap = [];
// ...
}
size(): number{
return this.heap.length;
}
insert(value){
// 当是空值时就返回 false（也就是传入 undefined 或者 null 时并不会做插入操作）
if(value == null) return false;
this.heap.push(value);
var size = this.size();
// 上移操作函数
this.siftUp(size - 1);
return true;
}
siftUp(idx){
// 获取到新插入元素的父节点的索引
var parentIdx = getParentIndex(idx);
var heap = this.heap;
while(idx > 0 && heap[parentIdx] > heap[idx]){
// 交换操作
swap(heap, parentIdx, idx);
idx = parentIdx;
parentIdx = getParentIndex(idx);
}
}
}这里有一点需要注意，在 siftUp 函数中我们使用了循环，这是因为当父元素与子元素交换后，这个子元素也可能比它的父元素的父元素还要小，这时就还需要交换。idx > 0 一方面是因为如果 heap 数组为空时我们不需要交换，只需要放入该元素即可；另一方面是因为该元素可能会上移到最顶端，成为堆的根元素，这时就不再需要交换操作了。
比如 heap 数组是 [2,3,4,5,6,7]，而我们新插入了一个元素：1，很显然它比堆中任何一个元素都要小，通过循环最终会抵达根部。
扩展 constructor 函数
当我们每次实力化一个堆时，可能需要插入很多元素，我们可以使用循环一一插入，但也可以利用构造函数更方便的进行初始插入操作：
class MinHeap<T> extends Heap<T>{
protected heap: T[];
// 构造函数可以传入一个数组，不传时默认是一个空数组
constructor(values: T[] = []){
super();
this.heap = [];
var len = values.length;
if(len){
for(let i = 0;i < len;i ++){
// 遍历然后插入
this.insert(values[i]);
}
}
}
}isEmpty、values、findRootVal
这三个方法都很简单，代码如下：
isEmpty(): boolean{
return this.size() ? false : true;
}
values(): T[]{
return [...this.heap];
}
findRootVal(): T | undefined{
return this.heap[0];
}merge 函数
这个函数可以接收任意多的参数，但参数应是堆实例，然后会把这些堆合并到当前堆中。
思路：通过实例中的 values 方法获取到每个堆中的数据，然后使用循环把每个元素获取到，最后把元素 insert 到当前堆里。
merge(heaps: Array<Heap<T>>): boolean{
var len: number = heaps.length;
if(len){
for(let i = 0;i < len;i ++){
var values = heaps[i].values();
for(let k = 0;k < values.length;k ++){
this.insert(values[k]);
}
}
return true;
}
return false;
}extract 函数
extract 函数会删除最小堆的根节点。如果删除根节点我们很可能需要将堆重新编排。如果我们直接删除根节点，可能会变成下面这个样子，导致堆特性不存在（右子树中的 3 节点不应在 4 节点下面）。
extract
解决思路：我们先不删除根节点，而是将最后一个节点（它必定是一个叶子节点）与根节点做交换，然后 pop 出根节点。根元素变成了原来是叶子结点的元素，我们需要将该元素做“下移”操作，因为这个元素并不一定比它的左右子节点要小。虽然需要交换，但除了根节点之外，堆的特性还都是满足的。
下移操作思路：首先我们可以获取到根元素的左右子节点索引值，然后分别与它们比较大小，如果根节点比它们的值要大，就需要做交换操作，重复这个过程，一直将这个元素交换到不能满足条件为止。这里需要注意一点，做交换前需要先了解一下它的左右子节点索引是否存在，判断依据就是索引值是不是比数组长度大（应该说是大于数组长度减一，因为索引值是从零开始的），如果求得的索引值比数组长度还要等显然不满足条件。
extract(): T | undefined{
var size: number = this.size();
if(!size) return undefined;
if(size === 1){
// 如果数组中只有一项，直接 pop 出去即可
return this.heap.pop();
}
// 否则就需要另外处理
// 首先根节点与最后一个节点做交换
swap(this.heap, 0, size - 1);
// 然后直接删除并拿到最后一个元素
var root = this.heap.pop();
// 下移操作（给数组的第零个元素做下移操作）
this.siftDown(0);
return root; // 返回被删除的元素
}接下来是 siftDown 函数：
siftDown(idx: number): void{
var elem: number = idx;
var left: number = getLeftIndex(idx);
var right: number = getRightIndex(idx);
var size: number = this.size();
// 先判断左侧，如果根元素比左侧子节点的值要大，就把做左子节点的索引给 elem
if(left < size && this.heap[elem] > this.heap[left]){
elem = left;
}
// 后判断右侧，如果根元素或者左子节点的值比右侧子节点的值要大，就把做右子节点的索引给 elem
if(right < size && this.heap[elem] > this.heap[right]){
elem = right;
}
if(elem !== idx){
// 当 elem 与 idx 值不相等时操作下面的操作，因为两者相等交换没有什么意义
swap(this.heap, elem, idx);
// 使用递归继续判断，此时 elem 已经变成子节点，但它的子节点的值也可能比它小
this.siftDown(elem);
}
// 如果 elem 与 idx 相等，说明它的左右子节点的值都比它大，满足最小堆特性
}delete 函数
写完了上面的 siftDown 函数，再写 delete 函数时就很简单了，要删除某个元素，我们首先获取该元素的索引，然后需要做判断。因为我们删除的节点可能并不是根节点，那这个节点就有父节点，我们不光要考虑下移操作，还需要考虑上移操作，因为在交换后最后一个节点的值可能要比它的父节点的值要大。例如下面的二叉堆，如果我们要删除黄色的那两个节点，而最后一个节点值是 3（黑色的节点），显然交换后 3 的父节点是 4 要比它大，因此交换后还要考虑上移操作。
delete node
具体实现如下：
delete(value: T): T | undefined{
var idx: number = this.heap.indexOf(value);
if(idx === -1) return undefined; // 说明没有这个值
// 先把这个元素与最后一个元素交换，然后使用 siftDown 函数
swap(this.heap, idx, this.size() - 1);
var result = this.heap.pop();
// 先进行上移操作，然后进行下移操作：
this.siftUp(idx);
this.siftDown(idx);
return result;
}OK，最小二叉堆的所有方法就写完了。然后是最大二叉堆。
最大二叉堆实现思路与最小二叉堆一样，我们只需要将最大堆继承最小堆的方法即可：
class MaxHeap<T> extends MinHeap<T>{
protected heap: T[];
constructor(ary: T[] = []){
super();
this.heap = [];
var len = ary.length;
if(len){
for(let i = 0;i < len;i ++){
// 调用父类上的方法
super.insert(ary[i]);
}
}
}
// siftUp 方法需要重写
siftUp(idx: number): boolean{
var parentIdx = getParentIndex(idx);
var heap = this.heap;
// 这里就应该是 '<' 了
while(idx > 0 && heap[parentIdx] < heap[idx]){
// 交换操作
swap(heap, parentIdx, idx);
idx = parentIdx;
parentIdx = getParentIndex(idx);
}
}
// siftDown 方法也需要重写
siftDown(idx: number): boolean{
var elem: number = idx;
var left: number = getLeftIndex(idx);
var right: number = getRightIndex(idx);
var size: number = this.size();
// 不再是 ‘>’ 而是 '<'
if(left < size && this.heap[elem] < this.heap[left]){
elem = left;
}
if(right < size && this.heap[elem] < this.heap[right]){
elem = right;
}
if(elem !== idx){
swap(this.heap, elem, idx);
this.siftDown(elem);
}
}
}堆排序
利用堆特性也能给一个数组做排序算法。
思路：我们知道，对于大根堆来说，堆的根节点是最大的一个元素，而小根堆的根节点是最小的一个元素。我们可以将堆的根元素删除并拿到，然后使用类似 siftDown 的操作将堆重新生成。然后再删掉根元素，再重新生成，这样反反复复就可以获得一个排好序的数组了。
首先我们需要一个 siftDown 函数（siftDown 并不做排序，它只做调整，就像上面的 siftDown 函数一样），它接收三个参数：
array需要排序的数组；idx被删除节点的索引；size最后一个元素索引；
然后就是实现，代码与上面的 siftDown 函数一样：
function siftDown<T>(array: T[], idx: number, size: number){
var cur = idx;
var left = getLeftIndex(idx);
var right = getRightIndex(idx);
if(left < size && array[cur] < array[left]){
cur = left;
}
if(right < size && array[cur] < array[right]){
cur = right;
}
if(cur !== idx){
swap(array, cur, idx);
siftDown(array, cur, size);
}
}写完了之后，我们需要一个用于排序的函数：
function maxHeapSort<T>(array: T[]){
var size = array.length;
for(let i = Math.floor(len / 2);i >= 0;i -= 1){
siftDown(array, i, len);
}
while(size > 1){
// 最后一个元素（并不是真正的最后一个，而是未排序的数组的最后一个元素）与第一个元素交换
swap(array, 0, -- size);
// 交换后把第一个元素下移
siftDown(array, 0, size);
}
return array;
}首先，我们使用 for 循环遍历数组，但只遍历了数组的后一半。试想一下，数组的后一个是不是都是堆的叶子节点？我们只需要对数组的一半元素进行下移操作就可以得到一个二叉堆。然后先交换数组元素，然后再进行下移操作。前一个循环是为了构建二叉堆，后一个循环是为了实现数组排序。
-- size 这一步很重要，因为最后一个元素与根元素交换后，最后一个元素就会变成最大的值（相当于排好了一个，就不用再动它了），然后重新构建后，根节点就又会变成最大的元素，然后再交换，再把 size 减一，反反复复，直到 size 小于等于一。
使用大根堆排序，排序后的数组是从小到大排列的，小根堆与之相反。
假如一个未排序的数组是 [2,3,5,1,4,7,6,8]。使用大根堆排序，它会经历以下的过程：
[2, 3, 5, 1, 4, 7, 6, 8]
// 开始构建大根堆
[2, 3, 5, 1, 4, 7, 6, 8]
[2, 3, 5, 8, 4, 7, 6, 1]
[2, 3, 7, 8, 4, 5, 6, 1]
[2, 8, 7, 3, 4, 5, 6, 1]
[8, 4, 7, 3, 2, 5, 6, 1]
// 开始排序：
[7, 4, 6, 3, 2, 5, 1, 8]
[6, 4, 5, 3, 2, 1, 7, 8]
[5, 4, 1, 3, 2, 6, 7, 8]
[4, 3, 1, 2, 5, 6, 7, 8]
[3, 2, 1, 4, 5, 6, 7, 8]
[2, 1, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]例题
问题描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
例如：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5例如：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4解题思路：先将数组从小到大排序，然后循环 pop 出第 k 个元素。于是就可以利用堆排序来实现该算法。不好的一点是堆排序过程有些复杂，需要 swap 函数、siftDown 函数、getLeftIndex 函数、getRightIndex 函数作为支撑。
我们改写一下上面的 maxHeapSort 函数即可：
function maxHeapSort<T>(array: T[], k: number): T{
let size: number = array.length;
let end: number = size - k; // 循环停止条件
let res: T;
for(let i = Math.floor(len / 2);i >= 0;i -= 1){
siftDown(array, i, len);
}
while(size > end){
swap(array, 0, -- size);
res = array.pop();
siftDown(array, 0, size);
}
return res; // 返回弹出的结果
}需要注意的是，堆排序算法不是一个稳定的排序算法。所谓排序算法稳定性，在原序列中，
r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。显然堆排序并不一定满足，比如做下移操作，或者根元素与最后一个未排序的元素做交换操作时。不过堆排序的时间复杂度还是比较低的：O(nlgn)。