堆与优先队列

堆与优先队列

优先队列性质？

• 队列元素具有优先的特点
• 优先队列插入元素和弹出元素，堆中元素都是无序的，但一个一个的弹出元素，就会发现弹出元素是有序的，堆排序就是由此而来
• 队首元素要么最小要么最大
• 二叉树中第二大或者第二小元素就在二叉树第二层

优先队列本质为什么？

• 堆，完美二叉树

优先队列操作时间复杂度

• 出队：O(long n)
• 入队：O(long n)
• 取队首元素 ：O(1)
• 判空 ：O(1)

优先队列实现方法？

• 结构体实现或者数组（因为完美二叉树可以用数组实现）

节点从数组0号位置开始

代码演示1：递归版

其中递归函数fl_r1是仿照迭代版函数pop写的， 而fl_r是我自己写的，fl_r更优

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

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

// 节点范围[0, n) 
typedef struct priority_queue {
    int *data;
    int size; 
    int cnt;
} priority_queue;

priority_queue *init(int n) { //初始化优先队列数组长度
    priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
    q->cnt = 0;
    q->size = n;
    q->data = (int *)malloc(sizeof(int) * n);
    return q;
}

int insert(priority_queue *q, int val) { //大顶堆 
    if (q == NULL) return 0;
    if (q->size == q->cnt) return 0;  //堆满了 
    int n = ((q->cnt)++);
    q->data[n] = val;
    while (q->data[(n - 1) >> 1] < q->data[n] && n) { // < 大顶堆； > 小顶堆 
        //n为0时即q->cnt = 0, 即堆中只有一个数，无需比较 
        swap(q->data[n], q->data[(n - 1) >> 1]);
        n = (n - 1) >> 1;
    }
    return 1;
}

int front(priority_queue *q) { // 取队列头部 
    return q->data[0];
} 

int empty(priority_queue *q) { //队列判空 
    return q->cnt;
}

void output(priority_queue *q) {
    if (q == NULL) return ;
    for (int i = 0; i < q->cnt; i++) {
        printf("%d ", q->data[i]);
    }
    return ;
}

//递归pop
void fl_r(priority_queue *q, int n, int l, int r) {
    int nn = n, ll = l, rr = r;
    if (ll >= q->cnt) return ;
    if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
    //output(q), printf("\n"); 
    if (rr >= q->cnt) return ;
    if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
    //    output(q), printf("\n");
    fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
    fl_r(q, ll, (ll << 1) + 1, (ll << 1) + 2);
    return ;
}

//递归pop
void fl_r1(priority_queue *q, int n, int l, int r) {
    int nn = n, ll = l, rr = r;
    if (ll >= q->cnt) return ;
    //if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
    if (q->data[ll] > q->data[nn]) nn = ll;
    //output(q), printf("\n");
    if (rr >= q->cnt) return ;
//    if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
    if (q->data[rr] > q->data[nn]) nn = rr;
    //    output(q), printf("\n");
//    fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
    if (nn == n) return ;
    swap(q->data[nn], q->data[n]);
    n = nn;
    fl_r1(q, nn, (nn << 1) + 1, (nn << 1) + 2);
    return ;
}

int pop(priority_queue *q) {
    if (!empty(q)) return 0;
    if (q == NULL) return 0; 
    q->data[0] = q->data[--(q->cnt)];
//    output(q), printf("\n");
    fl_r(q, 0, 1, 2);
    return 1;
}


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

int main() {
    #define n 20
    srand(time(0));
    priority_queue *q = init(n);
    for (int i = 0; i < n; i++) {
        //int val = rand() % 1001;
        printf("%s\n", insert(q, i) ? "插入成功" : "插入失败");
        output(q);
        printf("\n");
    }
    for (int i = 3; i < n; i++) {
        printf("%s\n", pop(q) ? "删除成功" : "删除失败");
        output(q);
        printf("\n");
        printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
    }
    
    #undef n
    clear(q);
    return 0;
}

代码演示二：迭代版

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

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

// 节点范围[0, n) 
typedef struct priority_queue {
    int *data;
    int size; 
    int cnt;
} priority_queue;

priority_queue *init(int n) { //初始化优先队列数组长度
    priority_queue *q = (priority_queue *)malloc(sizeof(priority_queue));
    q->cnt = 0;
    q->size = n;
    q->data = (int *)malloc(sizeof(int) * n);
    return q;
}
 //  数据范围[0, n) 
int push(priority_queue *q, int val) { //大顶堆 
    if (q == NULL) return 0;
    if (q->size == q->cnt) return 0;  //堆满了 
    int n = ((q->cnt)++);
    q->data[n] = val;
    while (n && q->data[(n - 1) >> 1] < q->data[n]) { // < 大顶堆； > 小顶堆 
        //n为0时即q->cnt = 0, 即堆中只有一个数，无需比较 
        swap(q->data[n], q->data[(n - 1) >> 1]);
        n = (n - 1) >> 1;
    }
    return 1;
}

int front(priority_queue *q) { // 取队列头部 
    return q->data[0];
} 

int empty(priority_queue *q) { //队列判空 
    return q->cnt;
}

void output(priority_queue *q) {
    if (q == NULL) return ;
    for (int i = 0; i < q->cnt; i++) {
        printf("%d ", q->data[i]);
    }
    return ;
}

//迭代版pop
int pop_(priority_queue *q) {
    if (q == NULL) return 0;    
    if (!empty(q)) return 0;
    q->data[0] = q->data[--(q->cnt)];
    int ind = 0;
    //max_root 为一个三元组中最大值的序号 
    //优先队列在二叉树种保证了对于每棵子树，其根节点都是最大值 
    //自上而下求出 完美二叉树 最大值 
    while (((ind << 1) + 1) < (q->cnt)) {
        int max_root = ind, l = (ind << 1) + 1, r = (ind << 1) + 2; 
        if (r < q->cnt && q->data[max_root] < q->data[r]) max_root = r; //与右节点比较， 取最大值 
        if (q->data[max_root] < q->data[l]) max_root = l; //与左节点比较， 取最大值 
        if (max_root == ind) break;
        swap(q->data[ind], q->data[max_root]);    
        ind = max_root;
    }
    return 1;
}

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

int main() {
    #define n 20
    srand(time(0));
    priority_queue *q = init(n);
    for (int i = 0; i < n; i++) {
        //int val = rand() % 1001;
        printf("%s\n", push(q, i) ? "插入成功" : "插入失败");
        output(q);
        printf("\n");
    }
    for (int i = 3; i < n; i++) {
        printf("%s\n", pop_(q) ? "删除成功" : "删除失败");
        output(q);
        printf("\n");
    //    printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
    }
    
    #undef n
    clear(q);
    return 0;
}

节点从数组1号位置开始

代码演示1：迭代版

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

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

// 节点范围[0, n) 
typedef struct priority_queue {
    int *data;
    int size; //代表队列长度 
    int cnt; //代表存在元素个数 
} 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 top(priority_queue *q) { // 取队列头部 
    return q->data[1];
} 

int empty(priority_queue *q) { //队列判空 
    return q->cnt == 0;
}

void output(priority_queue *q) {
    if (q == NULL) return ;
    for (int i = 1; i <= q->cnt; i++) {
        printf("%d ", q->data[i]);
    }
    return ;
}

int push(priority_queue *q, int val) { //大顶堆 
    if (q == NULL) return 0;
    if (q->size == q->cnt) return 0;  //堆满了 
    q->data[++(q->cnt)] = val;
    int n = q->cnt;
    while (n >> 1 && q->data[n] > q->data[n >> 1]) { // < 大顶堆； > 小顶堆 
        swap(q->data[n], q->data[n >> 1]);
        n >>= 1;
    }
    return 1;
}

//迭代版pop
int pop(priority_queue *q) {
    if (q == NULL) return 0;    
    if (empty(q)) return 0;
    q->data[1] = q->data[(q->cnt)--];
//    output(q), printf("\n");
    int ind = 1;
    //max_root 为一个三元组中最大值的序号 
    //优先队列在二叉树种保证了对于每棵子树，其根节点都是最大值 
    //自上而下求出 完美二叉树 最大值 
    while ((ind << 1) <= q->cnt) {
        int max_root = ind, l = ind << 1, r = ind << 1 | 1;
        if (q->data[max_root] < q->data[l]) max_root = l; //与左节点比较， 取最大值 
        // 如果它有右节点 ； r <= q->cnt 和 q->data[max_root] < q->data[r]顺序不能变 
        if (r <= q->cnt && q->data[max_root] < q->data[r]) max_root = r; //与右节点比较， 取最大值 
        if (max_root == ind) break;
        swap(q->data[ind], q->data[max_root]);
        ind = max_root;
    //    output(q), printf("\n");
    }
    return 1;
}

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

int main() {
    srand(time(0));
    #define n 20
    priority_queue *q = init(n);
    for (int i = 0; i < n; i++) {
        //int val = rand() % 1001;
        push(q, i);
        printf("插入%d到堆中\n", i);
        output(q), printf("\n");
    }
        //output(q), printf("\n");
    for (int i = 3; i < n; i++) {
        printf("%s\n", pop(q) ? "删除成功" : "删除失败");
        output(q);
        printf("\n");
    //    printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
    }
    
    #undef n
    clear(q);
    return 0;
}

代码演示二：递归版

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

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

// 节点范围[1, n] 
typedef struct priority_queue {
    int *data;
    int size; //代表队列长度 
    int cnt; //代表存在元素个数 
} 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 top(priority_queue *q) { // 取队列头部 
    return q->data[1];
} 

int empty(priority_queue *q) { //队列判空 
    return q->cnt == 0;
}

void output(priority_queue *q) {
    if (q == NULL) return ;
    for (int i = 1; i <= q->cnt; i++) {
        printf("%d ", q->data[i]);
    }
    return ;
}

int push(priority_queue *q, int val) { //大顶堆 
    if (q == NULL) return 0;
    if (q->size == q->cnt) return 0;  //堆满了 
    q->data[++(q->cnt)] = val;
    int n = q->cnt;
    while (n >> 1 && q->data[n] > q->data[n >> 1]) { // < 大顶堆； > 小顶堆 
        swap(q->data[n], q->data[n >> 1]);
        n >>= 1;
    }
    return 1;
}

//递归pop
void fl_r(priority_queue *q, int n, int l, int r) {
    int nn = n, ll = l, rr = r;
    if (ll > q->cnt) return ;
    //if (q->data[ll] > q->data[nn]) swap(q->data[ll], q->data[nn]);
    if (q->data[ll] > q->data[nn]) nn = ll;
    //output(q), printf("\n");
    if (rr > q->cnt) return ;
//    if (q->data[rr] > q->data[nn]) swap(q->data[rr], q->data[nn]);
    if (q->data[rr] > q->data[nn]) nn = rr;
    //    output(q), printf("\n");
//    fl_r(q, rr, (rr << 1) + 1, (rr << 1) + 2);
    if (nn == n) return ;
    swap(q->data[nn], q->data[n]);
    n = nn;
    fl_r(q, nn, nn << 1, (nn << 1) | 1);
    return ;
}

int pop(priority_queue *q) {
    if (q == NULL) return 0; 
    if (empty(q)) return 0;
    
    q->data[1] = q->data[(q->cnt)--];
//    output(q), printf("\n");
    fl_r(q, 1, 2, 3);
    return 1;
}

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

int main() {
    srand(time(0));
    #define n 20
    priority_queue *q = init(n);
    for (int i = 0; i < n; i++) {
        //int val = rand() % 1001;
        push(q, i);
        printf("插入%d到堆中\n", i);
        output(q), printf("\n");
    }
        //output(q), printf("\n");
    for (int i = 3; i < n; i++) {
        printf("%s\n", pop(q) ? "删除成功" : "删除失败");
        output(q);
        printf("\n");
    //    printf("第一大 = %d, 第二大 = %d\n", q->data[0], q->data[1] > q->data[2] ? q->data[1] : q->data[2]);
    }
    
    #undef n
    clear(q);
    return 0;
}