堆，优先队列，堆排序

本文主要是介绍堆，优先队列，堆排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

#define swape(a, b) ({\
                __typeof(a) temp = a;\
                a = b; b = temp;\
                })

typedef struct priority_queue {
        int *data, cnt, size;
} Priority_queue;

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

void clear(Priority_queue *p) {
        if (!p) return ;
        free(p->data);
        free(p);
        return ;
}

int empty(Priority_queue *p) {
        if (!p->cnt) return 1;
        return 0;
}

int top(Priority_queue *p) {
        return p->data[1];
}

int push(Priority_queue *p, int n) {
        if(!p || p->cnt > p->size) return 0;
        p->data[++p->cnt] = n;
        int ind = p->cnt;
        while(ind > 1 && n > p->data[ind >> 1]) {
                swape(p->data[ind >> 1], p->data[ind]);
                ind >>= 1;
        }
        return 1;
}

int pop(Priority_queue *p) {
        if(!p || empty(p)) return 0;
        p->data[1] = p->data[p->cnt--];
        int ind = 1, key = 1;
        while(p->cnt > ind && ind << 1 < p->cnt) {
                p->data[ind << 1] > p->data[ind] && (key = ind << 1);
                p->cnt > key && p->data[key] < p->data[ind << 1 | 1] && (key = ind << 1 | 1);
                if (ind == key) break;
                swape(p->data[ind], p->data[key]);
                ind = key;
        }
        return 1;
}

int main() {
        int k;
        srand(time(0));
#define MAX_N 20
        Priority_queue *p = init(MAX_N);
        for (int i = 1; i <= MAX_N; i++) k = rand() % 100, printf(" %d,", k), push(p, k);
        printf("\n"); for (int i = 1; i <= MAX_N; i++) printf(" %d ", p->data[i]);printf("\n");
        for (int i = 1; i <= MAX_N; i++) printf(" %d,", top(p)), pop(p);
#undef MAX_N
        clear(p);
        printf("\n");
        return 0;
}

这篇关于堆，优先队列，堆排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！