堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)
的几种常见排序方法。
堆排序是就地排序,辅助空间为O(1)
。
它是不稳定的排序方法(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化)。
什么是堆
堆通常是一个可以被看做一棵树的数组对象。满足下列性质:
1.堆中某个节点的值总是不大于(或不小于)其父节点的值;
2.堆总是一棵完全二叉树(完全二叉树叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部,详见二叉树中的完全二叉树)。
各种堆
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。
堆的结构
一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2
。它的左右子结点下标分别为2 * i + 1
和2 * i + 2
。如第0个结点左右子结点下标分别为1和2。
堆的操作
建立堆
一般情况下,树并不满足堆的条件,通过重新排列元素,可以建立一棵”堆化“的树。如初始表:55 12 16,堆化后为:12 55 16。
堆化数组:
关于怎样把一个数据进行堆化。可能很多人会想,要一个一个的从数组中取出数据来建立堆?不用。
比如说:
1 | int A[0] = {8,11,16,29,49,19,59,64,3,18}; |
如果把这个数组看成是一棵树,那么它的叶子结点19,59,64,3,18都分别是一个合法的堆。只要把49开始向下调整就可以了。然后再取29,16,11,9结点分别作一次向下调整操作就可以了。
1 | //建立最小堆 |
堆的插入
每次插入都是将新数据放在数组最后。然后树被更新以恢复堆次序。如初始表:12 22 7,插入新数据后,数组为12 22 7 16,然后重排树的顺序,数组为12 16 7 22。
可以发现从这个新数据的父结点到根结点必然为一个有序的数列。
1 | // 新加入i结点 其父结点为(i - 1) / 2 |
堆的删除
堆中每次都只能删除第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。
如初始表:12 16 50 22,删除第0个数据后,数组为22 16 50 _,然后重排树的顺序,数组为16 22 50。
1 | // 从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2 |
堆排序
根据堆的性质,堆建好之后。堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。
由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。
1 | void MinheapsortTodescendarray(int a[], int n) |
注意使用最小堆排序后是递减数组,要得到递增数组,可以使用最大堆。
应用
libevent
中的定时事件管理就是用一个以时间作为key
的小根堆结构做的,放弃了原来的红黑树,大概就是堆比红黑树简单吧。