【思维】堆排序 - BlueDream
算法定义
堆排序(Heapsort)是指利用(堆)这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构,并同时满足堆属性:即子结点的键值或索引总是小于(或者大于)它的父节点。
最差时间复杂度 O(nlogn) 最优时间复杂度 O(nlogn) 平均时间复杂度 Θ(nlogn)
算法描述
在堆积树的数据结构中,堆积树中的最大值总是位于根节点。堆积树中定义以下几种操作:
最大堆积调整(Max_Heapify):将堆积树的末端子结点作调整,使得子结点永远小于父结点 创建最大堆积(Build_Max_Heap):将堆积树所有数据重新排序 堆积排序(HeapSort):移除位在第一个数据的根结点,并做最大堆积调整的递归运算
源码描述
var HEAP_SIZE = 10;
// 获取父节点function getParent(i) {
return Math.floor(i/2);
}
// 获取左子节点
function getLeft(i) {
return 2 * i;
}
// 获取右子节点
function getRight(i) {
return (2 * i + 1);
}
// 对单一子节点维持最大堆
function Max_Heapify(A, i, heap_size) {
var l = getLeft(i);
var r = getRight(i);
var largest;
var temp;
if (l < heap_size && A[l] > A[i]) {
largest = l;
} else {
largest = i;
}
if (r < heap_size && A[r] > A[largest]) {
largest = r;
}
if (largest != i) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;
Max_Heapify(A, largest, heap_size);
}
}
// 建立最大堆树结构
function Buile_Max_Heap(A) {
for (var i = Math.floor(HEAP_SIZE/2); i >= 0; i--) {
Max_Heapify(A, i, HEAP_SIZE);
}
}
// 打印最大堆二叉树
function printTree(A) {
for (var i = 0; i < HEAP_SIZE; i++) {
document.write(A[i] + '<br/>');
}
}
// 堆排序
function HeapSort(A, heap_size) {
var temp;
Buile_Max_Heap(A);
for (var i = heap_size-1; i >= 1; i--) {
temp = A[0];
A[0] = A[i];
A[i] = temp;
heap_size = heap_size - 1;
Max_Heapify(A, 0, heap_size);
}
printTree(A);
}
// 测试堆排序
(function() {
var A = [4,1,3,2,16,9,10,14,8,7];
HeapSort(A, HEAP_SIZE);
})();
本文链接:http://www.cnblogs.com/bluedream2009/archive/2011/04/13/2014347.html,转载请注明。
文章来源:
Author:BlueDream
link:http://www.cnblogs.com/bluedream2009/archive/2011/04/13/2014347.html