二叉堆是一种特殊的二叉树数据结构。它有以下两个特性:
二叉堆一般有两种:
本文会实现下面几个二叉堆操作算法:
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 = [];
// ...
}
}
然后开始实现我们定义的各个方法。
往堆中插入新项。
思路:先把这个新的值放入数组的末端,然后对这个元素进行“上浮”操作。插入末端后我们可以拿到这个元素的索引,通过索引可以获取到它父元素的索引(使用上面的 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
,很显然它比堆中任何一个元素都要小,通过循环最终会抵达根部。
当我们每次实力化一个堆时,可能需要插入很多元素,我们可以使用循环一一插入,但也可以利用构造函数更方便的进行初始插入操作:
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(): boolean{
return this.size() ? false : true;
}
values(): T[]{
return [...this.heap];
}
findRootVal(): T | undefined{
return this.heap[0];
}
这个函数可以接收任意多的参数,但参数应是堆实例,然后会把这些堆合并到当前堆中。
思路:通过实例中的 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
函数会删除最小堆的根节点。如果删除根节点我们很可能需要将堆重新编排。如果我们直接删除根节点,可能会变成下面这个样子,导致堆特性不存在(右子树中的 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 相等,说明它的左右子节点的值都比它大,满足最小堆特性
}
写完了上面的 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)
。