JS 实现堆排序

思路

首先堆是一个二叉树，分为最大堆和最小堆。最大堆是代表每个父节点大于子节点，最小堆相反。在排序中堆是一个完全二叉树。
里面涉及了几个公式：

几个公式

一个二叉树完全二叉树他的节点计算公式为
parent(i) = floor(i/2);
ileft(i)=2i;
iright(i)=2i+1;
而数组中公式则是有变化
parent(i) = floor((i-1)/2);
ileft(i)=2i+1;
iright(i)=2(i+1);

主要思路

首先先进行最大堆调整，之后将最大堆的顶部也就是最大的数挪到尾部。之后堆的大小缩小1，之后继续进行最大堆调整重复上面的步骤。

最大堆的实现

注意下面的代码最大堆的实现就是从最后一个节点的父节点开始调整每颗子树当调整到头位置是调整完毕。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

//首先堆排序的时候的堆就是一个二叉树是一个完全二叉树
//首选第一个问题 就是构造最大或者最小堆
//这个问题要从底向上一点点的交换
//然后看公式
//一个二叉树完全二叉树他的节点计算公式为
//parent(i) = floor(i/2);
//ileft(i)=2i;
//iright(i)=2i+1;
//而数组中公式则是有变化
//parent(i) = floor((i-1)/2);
//ileft(i)=2i+1;
//iright(i)=2(i+1);
//有了公式之后的思路就变得简单了
// 首先找到最后一个节点之后找到他的父节点之后开始在这颗树里面调整最大堆之后一步步向前推进即可这样最大堆构建完成
//

function getMaxHeap(array,i,heapSize) {
    var imax,ileft,iright;
    while (true) {
        imax=i;
        ileft=2*i+1;
        iright=2*(i+1);
        if (iLeft<heapSize && array[i]<array[ileft]){
            imax=ileft;
        }
        if (iright<heapSize && array[i]<array[right]){
            imax=iright;
        }
    }
}
/**
 * 从 index 开始检查并保持最大堆性质
 * @array
 * @index 检查的起始下标
 * @heapSize 堆大小
 **/
function maxHeapify(array, index, heapSize) {
    var iMax, iLeft, iRight;
    while (true) {
        iMax = index;
        iLeft = 2 * index + 1;
        iRight = 2 * (index + 1);
        if (iLeft < heapSize && array[index] < array[iLeft]) {
            iMax = iLeft;
        }

        if (iRight < heapSize && array[iMax] < array[iRight]) {
            iMax = iRight;
        }

        if (iMax != index) {
            swap(array, iMax, index);
            index = iMax;
        } else {
            break;
        }
    }
    return array;
}

function swap(array, i, j) {
    var temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}


function buildMaxHeap(array, heapSize) {
    var i,iParent = Math.floor((heapSize - 1) / 2);//找寻最后一个节点的父元素
    for (i = iParent; i >= 0; i--) {
        maxHeapify(array, i, heapSize);
    }
    return array;
}

function heap_sort(arr) {
    buildMaxHeap(arr,arr.length);
    for (let i = arr.length-1; i >0; i--) {
        swap(arr,0,i);
        buildMaxHeap(arr,i);
    }
    return arr;
    
}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(heap_sort(elements));