【思维】堆排序 - 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