javascript:堆排序

堆排序是指利用（堆）这种数据结构所涉及的一种排序算法。堆积树是一个近似完全二叉树的结构，并同时满足堆属性：即子节点的键值总是小鱼（或者大于）他的父节点（大顶堆/小顶堆）。

算法描述：在堆积树的数据结构中堆积树中的最大值总是位于根节点（指大顶堆）。堆积树中定义一下几种操作：
（1）最大堆调整（Max_Heapify）:将堆积树的末端子节点作调整，使得子节点永远小于父节点；
（2）创建最大堆（Build_Max_Heap）:将堆积树所有数据重新排序；
（3）堆积排序：移除位在第一个数据的根节点，并做最大的堆积调整的递归运算

<script>
var HEAP_SIZE = 11;
// 获取父节点
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);
}
}
// 由数组建立最大堆树结构
//数组A后一半一定是分支节点，从最后一个根开始调整出初始堆*/
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);
}
// 测试堆排序
var A = [111,1,3,2,116,9,10,14,8,7,1];
HeapSort(A, HEAP_SIZE);
</script>
结果：
1
1
2
3
7
8
9
10
14
111
116