堆与优先队列

数据结构就是定义一种性质并去维护这种性质所产生的结构。

优先队列(堆)

#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 size, length;
} priority_queue;

priority_queue *init(int size);
void clear(priority_queue *que);
int push(priority_queue *que, int val);
int top(priority_queue *que);
int empty(priority_queue *que);
int pop(priority_queue *que);

int main() {
    srand(time(0));
    #define MAX_N 20
    priority_queue *que = init(MAX_N);
    for (int i = 0; i < MAX_N; i++) {
        int val = rand() % 100;
        printf("push the %2d to the priority_queue! = %d\n", val, push(que, val));
    }
    for (int i = 0; i < MAX_N; i++) {
        printf("%d ", top(que));
        pop(que);
    }
    printf("\n");
    #undef MAX_N
    clear(que);
    return 0;
}

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

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

int push(priority_queue *que, int val) {
    if (que == NULL) return 0;
    if (que->length == que->size) return 0;
    que->data[++que->length] = val;
    int ind = que->length;
    //大顶堆：向上调整
    while (ind >> 1 && que->data[ind >> 1] < que->data[ind]) {
        swap(que->data[ind >> 1], que->data[ind]);
        ind >>= 1;
    }
    return 1;
}

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

int empty(priority_queue *que) {
    return que->length == 0;
}

int pop(priority_queue *que) {
    if (que == NULL) return 0;
    if (empty(que)) return 0;
    que->data[1] = que->data[que->length--];
    //大顶堆：向下调整
    int ind = 1;
    while ((ind << 1) <= que->length) {
        int l = ind << 1, r = ind << 1 | 1, temp = ind;
        if (que->data[l] > que->data[temp]) temp = l;
        //记得是与temp比较，而不是ind！！！
        if (r <= que->length && que->data[r] > que->data[temp]) temp = r;
        if (temp == ind) break;
        swap(que->data[ind], que->data[temp]);
        ind = temp;
    }
}

堆排序

#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 ind, int max) {
    while ((ind << 1) <= max) {
        int l = ind << 1, r = ind << 1 | 1, temp = ind;
        //大顶堆：从小到大排序
        if (arr[l] > arr[temp]) temp = l;
        //记得是与temp比较，而不是ind！！！
        if (r <= max && 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 > 0; i--) {
        downUpdate(arr, i, n);
    }
    for (int i = n; i > 1; i--) {
        swap(arr[1], arr[i]);
        downUpdate(arr, 1, i - 1);
    }
    return;
}

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

int main() {
    srand(time(0));
    #define MAX_N 10
    int arr[MAX_N] = {0};
    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);
    #undef MAX_N
    return 0;
}

线性建堆法：将原本插入元素时的“向上调整”更改为“向下调整”