堆中定义以下几种操作：
- 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
- 堆排序（HeapSort）：卸载位在第一个数据的根节点，并做最大堆调整的递归运算
堆排序算法的基本特性：
时间复杂度：O(N * logN)
堆排序为不稳定排序，不适合记录较少的排序。
测试结果：
数组里有10000个随机数, 执行500次后花费的毫秒数
最大毫秒数为17
最小毫秒数为8
平均毫秒数为10
示例代码：
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>堆排序算法</title>
</head>
<body>
<script>
var count = 10000,
num = testCount = 500,
i,
exeCount,
exeTimeArr = [],
// 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
makeMax = function(a, pIndex, size){
var largest = pIndex,
lIndex= 2 * pIndex + 1,
rIndex = lIndex + 1;
if(a[pIndex] < a[lIndex] && lIndex < size){
largest = lIndex;
}
if(a[largest] < a[rIndex] && rIndex < size){
largest = rIndex;
}
if(largest != pIndex){
a[pIndex] = [ a[largest], a[largest] = a[pIndex] ] [0]; // 交换顶、左（右）节点2个数
a = makeMax(a, largest, size);
}
return a;
},
heapSort = function(a){
// 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
for(var len = a.length, i = Math.floor( (len - 2) / 2 ); i >= 0; i--){
a = makeMax(a, i, len);
}
// 头尾交换并确保最大堆成立
for(i = len - 1; i >= 0; i--){
a[0] = [ a[i], a[i] = a[0] ] [0]; // 头尾交换
a = makeMax(a, 0, i); //确保最大堆成立
}
return a;
};
var body = document.getElementsByTagName('body')[0];
var log = function(s){
var p = document.createElement('p');
var ps = document.getElementsByTagName('p');
p.innerHTML = s;
ps.length ?
body.insertBefore(p, ps[0]) :
body.appendChild(p);
//document.write(s + '<br />'); 破坏文档结构
//firefox下使用console.log并开启firebug会影响执行
}
function exeTest( callback ){
function test(){
var cost,
startTime,
arr = [];
testCount--;
// 构建随机数组
for(i=0;i<count;i++){
arr.push( Math.round(Math.random() * count) ); // 0 - count
}
startTime = + new Date();
arr = heapSort(arr);
exeTimeArr.push(cost = new Date() - startTime); //花费的毫秒数
log('本次测试花费 '+ cost +' 毫秒, 还剩 '+ testCount +' 次测试');
if(testCount == 0 && typeof callback == 'function'){
callback();
}else{
// 预防浏览器挂起
setTimeout(test, 10);
}
}
test();
}
function callback(){
var sum = 0;
var result = '数组里有'+ count +'个随机数, 执行'+ num +'次后花费的毫秒数' + '<br />' +
'最大毫秒数为' + Math.max.apply(null, exeTimeArr) + '<br />' +
'最小毫秒数为' + Math.min.apply(null, exeTimeArr) + '<br />';
exeTimeArr.forEach(function(value) {
sum += value;
})
result += '平均毫秒数为' + Math.round( sum / num ) ;
log(result);
}
// 执行100次测试完成时间
exeTest(callback);
</script>
</body>
</html>
