堆与堆排序

一、定义

堆的定义

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1. 堆中某个节点的值总是不大于或不小于其父节点的值

2. 堆总是一棵完全二叉树。

大顶堆

每个结点的值都大于或等于其左右孩子结点的值

小顶堆

每个结点的值都小于或等于其左右孩子结点的值
另外在堆的存储方式需要注意，以大顶堆为例

存储时假如父节点存在arr[i]则左孩子存在arr[2i ]右孩子存在arr[2i+1]（数组从1开始存储数据，0不存储任何数据）

二、堆的相关操作（大顶堆）

结构定义

因为堆可以看成数组所以我们用数组来实现，下面堆所用数组从1开始存储数据，0不存储任何数据

typedef struct priority_queue{
    int *data;
    int cnt, size;        //cnt用来表示数组中存储数据的个数，而size表示数组开辟空间的大小
}priority_queue;

初始化

priority_queue *init(int n) {
    priority_queue * q = (priority_queue *)malloc(sizeof(priority_queue));
    q->data = (int *) malloc(sizeof(int) * (n + 1));  //因为数组0位置上不存储数据所以要开n+1的空间大小
    q->cnt = 0;          
    q->size = n;
    return q;
}

判空

int empty(priority_queue *q) {
    return q->cnt == 0;
}

返回堆中最大或最小元素

int top(priority_queue *q) {
    return q->data[1];
}

添加元素

int push(priority_queue *q, int val) {
    if(q == NULL) return 0;
    if(q->cnt == q->size) return 0;
    q->cnt += 1;
    q->data[q->cnt] = val;            //先将要添加的元素放到数组最后
    int ind = q->cnt;
    while(ind / 2 && q->data[ind] > q->data[ind / 2]) { //需要判断该子节点的父节点存不存在若存在则比较父节点与子节点的值，若父节点的值小于子节点的值则交换，一直进行直到新加入的节点到它应该在的位置
        swap(q->data[ind],q->data[ind/ 2]);
        ind >>= 1;
    } 
    return 1;
}

删除根节点

int pop(priority_queue *q) {
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->data[1] = q->data[q->cnt--];  //先将最后一个节点覆盖到根节点上
    int ind = 1;
    while((ind  * 2)<= q->cnt) {
        int temp = ind, l = ind * 2, r=ind *2 + 1;
        if(q->data[l] > q->data[temp]) temp = l;
        if(r <= q->cnt && q->data[r] > q->data[temp]) temp =r;
        if(temp == ind) break;
        swap(q->data[ind],q->data[temp]);
        ind = temp;
    }
    return 1;
}

可参考https://www.jianshu.com/p/6b526aa481b1

代码汇总

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define swap(a,b) {\
    __typeof(a) __temp = a;\
    a= b,b=__temp;\
}
typedef struct priority_queue{
    int *data;
    int cnt, size;
}priority_queue;

priority_queue *init(int n) {
    priority_queue * q = (priority_queue *) malloc(sizeof(priority_queue));
    q->data = (int *) malloc(sizeof(int) * (n + 1));
    q->cnt = 0;
    q->size = n;
    return q;
}

int empty(priority_queue *q) {
    return q->cnt == 0;
}

int top(priority_queue *q) {
    return q->data[1];
}

int push(priority_queue *q, int val) {
    if(q == NULL) return 0;
    if(q->cnt == q->size) return 0;
    q->cnt += 1;
    q->data[q->cnt] = val;
    int ind = q->cnt;
    while(ind >> 1 && q->data[ind] > q->data[ind >> 1]) {
        swap(q->data[ind],q->data[ind>> 1]);
        ind >>= 1;
    } 
    return 1;
}

int pop(priority_queue *q) {
    if(q == NULL) return 0;
    if(empty(q)) return 0;
    q->data[1] = q->data[q->cnt--];

    int ind = 1;
    while((ind << 1)<= q->cnt) {
        int temp = ind, l = ind << 1, r=ind << 1 | 1;
        if(q->data[l] > q->data[temp]) temp = l;
        if(r <= q->cnt && q->data[r] > q->data[temp]) temp =r;
        if(temp == ind) break;
        swap(q->data[ind],q->data[temp]);
        ind = temp;
    }
    return 1;
}

void clear(priority_queue *q) {
    if(q == NULL) return;
    free(q->data);
    free(q);
    return;
}

int main() {
    srand(time(0));
    #define max_op 20
    priority_queue *q = init(max_op);
    for(int i = 0; i< max_op; i++) {
        int val = rand() % 100;
        push(q, val);
        printf("insert %d to queue\n", val);

    }
    for(int i = 0; i< max_op; i++){
        printf("%d ", top(q));
        pop(q);
    }
    printf("\n");
    clear(q);
    return 0;
}

三、堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b; b = __temp;\
}

void downUpdate(int *arr, int n, int ind) {  //构建大顶堆
    while ((ind * 2) <= n) {
        int temp = ind, l = ind * 2, r = ind * 2 + 1;
        if (arr[l] > arr[temp]) temp = l;
        if (r <= n && arr[r] > arr[temp]) temp = r;
        if (temp == ind) break;
        swap(arr[temp], arr[ind]);
        ind = temp;
    }
    return ;
}

void heap_sort(int *arr, int n) { // 堆排序
    for (int i = n / 2 ; i >= 1; i--) { //最后一个非叶子结点开始进行调整
        downUpdate(arr, n, i);
    }
    for (int i = n; i > 1; i--) {
        swap(arr[i], arr[1]);
        downUpdate(arr, i - 1, 1);
    }
    return ;
}

void output(int *arr, int n) {
    printf("arr(%d) = [", n);
    for (int i = 1; i <= n; i++) {
        printf(" %d", arr[i]);
    }
    printf("]\n");
    return ;
}

int main() {
    srand(time(0));
    #define max_op 20
    int *arr = (int *)malloc(sizeof(int) * (max_op + 1));
    for (int i = 1; i <= max_op; i++) {
        int val = rand() % 100;
        arr[i] = val;
    }
    output(arr, max_op);
    heap_sort(arr, max_op);
    output(arr, max_op);
    free(arr);
    return 0;
}

参考https://www.cnblogs.com/chengxiao/p/6129630.html