堆排序

文章目錄

对于求最小的K个数和最大的K个数，一种解决办法是使用堆。对于堆，数据结构的书籍中都有讲到，可是面试时不知是紧张还是什么原因，连堆都忘记了，悲哀，真是悲哀。

想来堆排序还是不难的，如果要对n个数字从小到大排序，则先建立这n个数字的大顶堆，之后堆顶与最后一个数字交换，此时就得到最大的数字，且在最后一位中，之后之需要对前n-1个数字排序。这里堆顶与最后一个数字交换后，会破坏了大顶堆，需要重建堆。对于大顶堆，意思就是堆顶的元素是最大的，之后是堆顶的左右子节点。

这里主要就是两个步骤，一个是建立大顶堆，一个是重建堆。
看代码可能会更容易一些

#include <stdio.h>
#include <stdlib.h>
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}
void adjust_heap(int *a, int cur, int n) {
    int left, right;
    while (true) {
        left = 2 * cur + 1;
        right = 2 * cur + 2;
        int index = cur;
        if (left < n && a[left] > a[index]) {
            index = left;
        }
        if (right < n && a[right] > a[index]) {
            index = right;
        }
        if (index != cur) {
            swap(a[cur], a[index]);
            cur = index;
        } else {
            break;
        }
    }
}
void build_heap(int *a, int n) {
    for (int i = (n - 1) / 2; i >= 0; i--) {
        adjust_heap(a, i, n);
    }
}
void heap_sort(int *a, int n) {
    build_heap(a, n);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        adjust_heap(a, 0, i);
    }
} 
int main() {
    int a[] = {10, 2, 5, 7, 6, 13 , 8, 7};
    int n = sizeof(a) / sizeof(int);
    heap_sort(a, n);
    for (int i = 0; i < n - 1; i++) {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n - 1]);
    return 0;
}