排序算法-堆排序

堆排序

定义

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
  堆排序的平均时间复杂度为 Ο(nlogn)。

完全二叉树

完全二叉树定义：除了最后一层，二叉树其他节点个数都是满的。
由完全二叉树转数组可以得出以下结论：任意一个节点 i（下标） 的父节点 parent ，左右子节点c1、c2 下标为：

parent = (i - 1) / 2 （向下取整）
c1 = 2 * i + 1
c2 = 2 * i + 2

例如：[4, 10, 3, 5, 1, 2]，生成完全二叉树。

• 元素4 （i=0），parent=4，左节点=10（c1=02+1），右节点=3(c2=02+2)
• 元素10（i=1），parent=4（parent=1-1/2），左节点=5（c1=12+1），右节点=1(c2=12+2)
• 元素3 （i=2），parent=4（parent=2-1/2），左节点=2（c1=22+1），无右节点c2(c2=22+2 > length)
• …

        4     
      /  \    
    10    3   
   / \   / \  
  5   1 2     
1
2
3
4
5

按指定位置生成合格的堆结构。

堆的定义：堆是一个完全二叉树。其中堆的每一个父节点的值，必须 大于等于 其左右节点的值。
例如：[4, 10, 3, 5, 1, 2]，生成的堆 [10, 5, 3, 4, 1, 2]

        4               10               10                         
      /  \             /  \             /  \                    
    10    3    ->     4    3    ->     5    3                    
   / \   / \         / \   /          / \   /                      
  5   1 2           5   1 2          4   1 2                       
1
2
3
4
5

对堆下标为 i 的父节点及左右子节点进行排序。n 为数组大小，i 为当前进行排序的父节点。

function heapify(tree, n, i) {
    if (i >= n) {
        return;
    }
    let c1 = 2 * i + 1;
    let c2 = 2 * i + 2;
    let max = i;
    // 找出最大值，与父节点进行交换。
    if (c1 < n && tree[c1] > tree[max]) {
        max = c1;
    }
    if (c2 < n && tree[c2] > tree[max]) {
        max = c2;
    }
    if (max != i) {
        swap(tree, max, i);
        // 为了确保交换后子节点依然满足堆结构，需要继续对底层子节点进行 heapify
        heapify(tree, n, max);
    }
}

function swap(tree, max, i) {
    let temp = tree[i];
    tree[i] = tree[max];
    tree[max] = temp;
}

let tree = [4, 10, 3, 5, 1, 2];
heapify(tree, tree.length, 0);
console.log(tree); // [ 10, 5, 3, 4, 1, 2 ]
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

构建堆结构

将完全无序的二叉树生成堆
例如：[2, 5, 3, 1, 10, 4]，不难发现，我们只需要在最底层的中间节点开始，倒着做 heapfiy 就行。
我们只需要在 5、3、2，也就是下标 2，1，0，三个位置做 heapfiy （Math.floor(tree.lenght/2)）。

        2                     2                      2                     10                     10       
      /  \   buideHeap（2）  /  \   buideHeap（1） /   \  buideHeap（0）  /   \  递归heapify(2)  /   \                  
    5     3     -->        10   3      -->       10    4     -->        2    4       -->       5    4    
   / \   / \              / \   /               / \   /                / \   /                / \   /    
  1  10 4                1   5 4               1   5 3                1   5 3                1   2 3    
1
2
3
4
5

将完全无序的二叉树生成符合条件的堆结构（每一节父节点都大于或等于左右子节点）。

function build_heap(tree, n) {
    let parent = Math.floor(n / 2);
    // 发现只需要在最底层的中间节点开始，倒着做 heapfiy 就行
    for (let i = parent; i >= 0; i--) {
        heapify(tree, n, i);
    }
}

let tree = [2, 5, 3, 1, 10, 4]
build_heap(tree, tree.length)
console.log(tree) // [ 10, 5, 4, 1, 2, 3 ]
1
2
3
4
5
6
7
8
9
10
11

堆排序

我们此时已经生成了堆，即保证每个父节点都大于子节点。接下来对生成好的堆结构进行排序。
排序步骤：不难发现，堆中最大的数在于堆顶。将堆顶取出，将最后一个节点替换为堆顶节点，重新对顶点进行 heapify。

     10                             3                             5    
    /   \                          /  \                         /   \        
   5     4  取出堆顶              5    4  堆顶执行至堆底-1     3     4              
  / \   /  替换堆尾元素          / \   /    执行 heapify      / \    /
 1   2 3                        1   2|10|                    1   2  |10|            

     5                              2                            4                            
   /   \      取出堆顶            /   \  堆顶执行至堆底-1      /   \                                                       
  3     4    替换堆尾元素       3     4    执行 heapify       3      2                                                   
 / \   /                       / \    /                      / \    /                                               
1   2 |10|                    1  |5| |10|                   1  |5| |10|                        


     4                            1                                 3                    
   /   \     取出堆顶          /    \        堆顶执行至堆底-1    /    \             
  3      2  替换堆尾元素      3      2        执行 heapify      1      2            
 / \    /                    / \     /                         / \     /                    
1  |5| |10|                 |4| |5| |10|                      |4| |5| |10|               


      3                            2                                   [1]                                                                 
   /    \     取出堆顶          /    \        堆顶执行至堆底-1      /    \   
  1      2   替换堆尾元素      1     [3]       执行 heapify        [2]   [3] 
 / \     /                    / \     /          生成小顶堆       / \     /          
|4| |5| |10|                 |4| |5| |10|                       |4| |5| |10|                                 

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

将堆顶与堆底进行 swap，并从堆顶到堆底（n–）进行 haepify

function heap_sort(tree, n) {
    let i
    for (i = n - 1; i >= 0; i--) {
        swap(tree, i, 0)
        heapify(tree, i, 0)
    }
}

let tree = [10, 5, 4, 1, 2, 3]
let n = tree.length
heap_sort(tree, n)
console.log(tree) // [ 1, 2, 3, 4, 5, 10 ]
1
2
3
4
5
6
7
8
9
10
11
12

完整堆排序代码

// 交换两个节点
function swap(tree, max, i) {
    let temp = tree[i];
    tree[i] = tree[max];
    tree[max] = temp;
}

// 生成合格的堆结构
function heapify(tree, n, i) {
    if (i >= n) {
        return;
    }
    let c1 = 2 * i + 1;
    let c2 = 2 * i + 2;
    let max = i;
    if (c1 < n && tree[c1] > tree[max]) {
        max = c1;
    }
    if (c2 < n && tree[c2] > tree[max]) {
        max = c2;
    }
    if (max != i) {
        swap(tree, max, i);
        heapify(tree, n, max);
    }
}

// 构建堆结构
function build_heap(tree, n) {
    let parent = Math.floor(n / 2);
    for (let i = parent; i >= 0; i--) {
        heapify(tree, n, i);
    }
}

// 堆排序入口，生成堆合格结构，后将堆变成小顶堆（最小的数字在堆顶）
function heap_sort(tree, n) {
    build_heap(tree, n);
    let i;
    for (i = n - 1; i >= 0; i--) {
        swap(tree, i, 0);
        heapify(tree, i, 0);
    }
}

let tree = [4, 10, 3, 5, 1, 2];
heap_sort(tree, tree.length);
console.log(tree);
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