07 数据结构与算法之堆与优先级队列（C语言实现）

注：只给出C语言实现代码，涉及到的数据结构相关概念请自行阅读相关书籍或参考其他博文；

堆与优先级队列的形式大概如下：
堆是一种特殊的完全二叉树结构

插入的时间复杂度O(logN), 整个堆的调整时间复杂度为O(NlogN)

//可以用二叉树或用顺序结构(队列)实现
#include 
#include 
#include 

#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->data[++(q->cnt)] = val;//从尾部插入数据
    int ind = q->cnt;//自下向上调整元素至平衡为止
  //ind >> 1表示堆中还有元素，
    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;//调整堆元素,ind记录存堆数组的下标
    while((ind << 1) <= q->cnt){//从根节点自上向下调整
        int temp = ind, l = ind << 1, r = ind << 1 | 1;//l左孩子，r右孩子或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 the priority_queue!n", val);
    }
    for(int i = 0; i < MAX_OP; i++){
        printf("%d ", top(q));
        pop(q);
    }
    printf("n");
    #undef MAX_OP
    clear(q);
    return 0;
}

//线性建堆法的调整策略为自下向上调整
#include 
#include 
#include 

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

void downUpdate(int *arr, int n, int ind) {
    while ((ind << 1) <= n) {
        int temp = ind, l = ind << 1, r = ind << 1 | 1;
        if (arr[l] > arr[temp]) temp = l;//大顶堆小顶堆只跟本行有关
        if (r <= n && arr[r] > arr[temp]) temp = r;//大顶堆小顶堆只跟本行有关
        if (temp == ind) break;
        swap(arr[ind], arr[temp]);
        ind = temp;
    }
    return ;
}

void heap_sort(int *arr, int n) { //堆排序
    arr -= 1;
    for (int i = n >> 1; 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("[");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("]n");
    return ;
}

int main() {
    srand(time(0));
    #define MAX_N 20
    int *arr = (int *)malloc(sizeof(int) * (MAX_N + 1)); //用顺序表存储堆元素
    for (int i = 0; i < MAX_N; i++) {
        arr[i] = rand() % 100;
    }
    output(arr, MAX_N);
    heap_sort(arr, MAX_N);
    output(arr, MAX_N);
    free(arr);
    #undef MAX_N
    return 0;
}