最小堆、最大堆、堆排序

发表于 | 分类于 | |

堆树的定义：

堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

最小堆：

元素下沉思想：从无序数组的最后往前遍历，堆树从下层到上层依次搭建完成

1 从叶子节点（无序数组的最后一个元素）出发，把当前的parent设置为无序数组中的最后一个数（也就是叶子节点），依次往前遍历，当parent是叶子节点，就不做操作

2 当parent遍历到非叶子节点，此时，它就有左子节点和右子节点或者只有左子节点。需要做的操作：先在左右子节点中找到最小元素所在的索引，然后将左右子节点中的最小元素与parent的节点，进行比较，如果小于，则交换，同时更新parent和child的位置。否则不交换，退出当前循环。

3 “元素下沉”的终止条件就是父节点的元素值不小于其任意左右子节点的元素值，或者当前父节点无子节点（即当前节点为叶子节点）。

最大堆：

最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

插入：

由于需要维持完全二叉树的形态，需要先将要插入的结点x放在最底层的最右边，插入后满 足完全二叉树的特点；
然后把x依次向上调整到合适位置满足堆的性质,例如下图中插入80,先将80放在最后,然后两次上浮到合适位置.

时间：O(logn)。 “结点上浮”

删除：

操作原理是：当删除节点的数值时，原来的位置就会出现一个孔,填充这个孔的方法就是，
把最后的叶子的值赋给该孔并下调到合适位置，最后把该叶子删除。

初始化：

方法1：插入法：
从空堆开始，依次插入每一个结点，直到所有的结点全部插入到堆为止。
时间：O(n*log(n))
方法2：调整法：
​ 序列对应一个完全二叉树；从最后一个分支结点（n div 2）开始，到根（1）为止，依次对每个分支结点进行调整（下沉），
以便形成以每个分支结点为根的堆，当最后对树根结点进行调整后，整个树就变成了一个堆。
时间：O(n)

堆排序C实现：

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
#include <stdio.h>
#include <stdlib.h>
 
void swap(int* a, int* b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}
 
void max_heapify(int arr[], int start, int end) 
{
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)  //若子节点指标在范围内才做比较
        {
            if (son + 1 <= end && arr[son] < arr[son + 1]) 
            //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
            return;
        else  //否则交换父子内容再继续子节点和孙节点比较
        {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
 
void heap_sort(int arr[], int len) 
{
    int i;
    //初始化，i从最後一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) 
    {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
 
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

注意：

在二叉树中，若当前节点的下标为 i， 则其父节点的下标为 i/2，其左子节点的下标为 i*2，其右子节点的下标为i*2+1；