堆排序-c++

2018-03-01 10:57:24来源:https://www.jianshu.com/p/984e47bf0323作者:爱秋刀鱼的猫人点击

分享


堆排序应该不会考笔试,但是知道它总是好的。


首先,堆排序会涉及到最大堆,最小堆。而这两种数据结构的基础都是完全二叉树。完全二叉树是一种特殊的二叉树。它的特殊性在于,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。


最大堆和对应的存储结构
从图中可以看出父节点和子节点的对应关系。相应的,几个计算公式:
Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标

对于堆排序,要两个关键步骤:


最开始最大堆的构建(Build-Max-Heap)
最大堆的调整(Max_heapify)
Max_heapify


最大堆调整过程

这里最巧妙的是引入了一个imax这个变量。这个是指示最后最大元素所在位置,然后将堆顶的元素和这个元素进行交换。然后继续调整交换以后的子树。


function maxHeapify(array, index, heapSize) {
var iMax = index,
iLeft = 2 * index + 1,
iRight = 2 * (index + 1);
if (iLeft < heapSize && array[index] < array[iLeft]) {
iMax = iLeft;
}
if (iRight < heapSize && array[iMax] < array[iRight]) {
iMax = iRight;
}
if (iMax != index) {
swap(array, iMax, index);
maxHeapify(array, iMax, heapSize); // 递归调整
}
}
function swap(array, i, j) {
var temp = array[I];
array[i] = array[j];
array[j] = temp;
}

回到堆排序,我们要做的是,先建立一个最大堆,然后将堆顶元素和最后一个元素交换 ,接着调整除最后一个元素的满二叉树为最大堆。其中第一步调整最大堆伪代码:


function buildMaxHeap(array, heapSize) {
var i,
iParent = Math.floor((heapSize - 1) / 2);

for (i = iParent; i >= 0; i--) {
maxHeapify(array, i, heapSize);
}
}


那么,堆排序的整个过程如下图:





堆排序示意图

伪代码:


function heapSort(array, heapSize) {
buildMaxHeap(array, heapSize);
for (int i = heapSize - 1; i > 0; i--) {
swap(array, 0, i);
maxHeapify(array, 0, i);
}
}







最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台