堆排序

发表于 更新于

今天在写堆结构的时候，突然怀疑两种方式构建堆的正确性了，还是记录下思考过程比较好。

一、算法实现

我们知道，在堆排序的过程中有两种方式构建堆，从后往前依次下沉插入$O(n)$，从前往后依次上升插入$O(nlogn)$。这里都可以用数学归纳法证明其构建的正确性，具体我写在注释里了。

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
#define _CRT_SECURE_NO_WARNINGS
#include "iostream"
#include "cstring"
#include "cstdlib"
#include "algorithm"
using namespace std;
void heapInsert(int* arr, int i) {
    // 不要用 (i - 1) >> 1, 当i=0时会有问题
    while (arr[(i - 1) / 2] < arr[i]) {
        swap(arr[(i - 1) / 2], arr[i]);
        i = (i - 1) / 2;
    }
}
// 大顶堆 下调堆
void heapify(int *arr, int i, int n) {
    int left = (i << 1) + 1, right = left + 1;
    while (left <= n) {
        int largest = i;
        if (arr[largest] < arr[left]) largest = left;
        if (right <= n && arr[largest] < arr[right]) largest = right;
        if (largest == i) break;
        swap(arr[largest], arr[i]);
        i = largest;
        left = (i << 1) + 1, right = left + 1;
    }
}


int main()
{
    int arr[] = { 1,3,5,7,9,2,4,6,10,8 };
    int n = sizeof(arr) / sizeof(int);

    // 可以用数学归纳法证明O(nlogn) 这样构建的是一个大根堆
    // i = 0 显然成立
    // i = n + 1 时：假设不是大根堆，只会是 n+1 的父节点严格小于 n+1的兄弟节点，这显然是不可能的
    for (int i = 0; i < n; ++i) heapInsert(arr, i);
    // 同理也可以证明 这也是一个大根堆 O(n)
    /*for (int i = n - 1; i >= 0; --i) {
        heapify(arr, i, n - 1);
    }*/
    for (int i = 1; i < n; ++i) {
        swap(arr[0], arr[n - i]);
        heapify(arr, 0, n - 1 - i);
    }



    for (int i = 0; i < n; ++i) printf("%d  ", arr[i]);
    return 0;
}