堆排序 Heapsort

堆排序是一种以(二叉)堆为数据结构来管理算法执行的原地排序算法。
二叉堆是一种数组对象,可以被视为一颗完全二叉树。二叉堆分为最大堆和最小堆。
对于数组:

[20, 17, 13, 12, 10, 9, 7, 6, 5,2, 1]




它可以就可视为一个最大堆,一下为一个二叉树的示意图:



我们把要排序的数组记为 A , A.length 为数组的长度(数组元素的个数),
下标从 0 开始到 A.length – 1 结束,对于元素 A[i] 有父节点 parent(i)、
左儿子 left(i)、右儿子 right(i),则有下列关系:

parent(i) = floor((i - 1) / 2)
left(i) = 2 * (i + 1) - 1
right(i) = 2 * (i + 1)

floor 为向下取整。
这也可以结合上面的图例看出来。
那么最大堆应该满足: A[i] <= A[parent(i)],最小堆应该满足:A[i] >= A[parent(i)]
这也就是堆的基本性质。
在堆排序中,我们要一直维护堆的这种性质,对于第 i 个元素使用如下方式:

function maxHeapify(A, i, len){
	var l = left(i), r = right(i), largest;
	if(l < len && A[l] > A[i]){
		largest = l;
	}
	else{
		largest = i;
	}
	if(r < len && A[r] > a[largest]){
		largest = r;
	}
	if(largest != i){
		var temp = A[i];
		A[i] = A[largest];
		A[largest] = temp;
		maxHeapify(A, largest, len);
	}
}

此方法使用递归的方式维护一个堆的最大堆性质。

下面我们将这个数组构建为最大堆:

function buildMaxHeap(A){
	var len = A.length, start = floor(len / 2);
	for(var i = start; i > 0; i--){
		maxHeapify(A, i, len);
	}
}

先面我们以数组

 [9, 17, 1, 13, 7, 20,2, 10, 6, 5, 12]

为例图解一下最大堆构建过程:



这样就构造好了最大堆。
最大堆的一个性质就是根节点的值(A[0])最大,那么我们只要用最后一个元素和
根节点元素交换,然后将剩余的元素构成的堆重新调整为最大堆就能顺序取出有序元素了。
算法如下:

我们以上面已经构造好的最大堆图解完成排序过程:


现在我们整理一下算法:

function maxHeapify(aArr, iIndex, iLength){
	var iRight = 2 * (1 + iIndex),
	iLeft = iRight - 1,
	iLargest = iIndex;

	if(iLeft < iLength && aArr[iLeft] > aArr[iIndex]){
		iLargest = iLeft;
	}
	if(iRight < iLength && aArr[iRight] > aArr[iLargest]){
		iLargest = iRight;
	}
	if(iLargest !== iIndex){
		var mTemp = aArr[iIndex];
		aArr[iIndex] = aArr[iLargest];
		aArr[iLargest] = mTemp;
		maxHeapify(aArr, iLargest, iLength);
	}
}
function buildMaxHeap(aArr){
	var iLength = aArr.length,
	iStart = Math.floor(iLength / 2);

	while(--iStart >= 0){
		maxHeapify(aArr, iStart, iLength);
	}
}
function heapSort(aArr){
	var iLength = aArr.length,
	iStart = iLength,
	mTemp;

	buildMaxHeap(aArr);
	while(--iStart > 0){
		mTemp = aArr[0];
		aArr[0] = aArr[iStart];
		aArr[iStart] = mTemp;
		maxHeapify(aArr, 0, --iLength)
	}
	return aArr;
}

Post a Comment

Your email is never shared. Required fields are marked *

*
*