C语言优先队列怎么使用

C语言中，优先队列可以通过使用堆（heap）来实现。堆是一种特殊的二叉树结构，满足以下两个性质：

1. 堆是一个完全二叉树（除了最后一层，其他层的节点都是满的，最后一层的节点从左到右依次填入）；
2. 堆中任意节点的值都不大于（或不小于）其子节点的值。

下面是使用C语言实现优先队列的示例代码：

#include stdio.h>
    
#include stdlib.h>


// 定义优先队列结构
typedef struct {
    
    int *arr;
      // 存储元素的数组
    int size;
      // 队列的当前大小
    int capacity;
  // 队列的最大容量
}
     PriorityQueue;


// 初始化优先队列
PriorityQueue* initPriorityQueue(int capacity) {
    
    PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));
    
    queue->
    arr = (int*)malloc(sizeof(int) * (capacity + 1));
    
    queue->
    size = 0;
    
    queue->
    capacity = capacity;
    
    return queue;

}


// 交换元素
void swap(int* a, int* b) {
    
    int temp = *a;
    
    *a = *b;
    
    *b = temp;

}


// 上浮操作
void swim(PriorityQueue* queue, int k) {
    
    while (k >
     1 &
    &
     queue->
    arr[k / 2]  queue->
arr[k]) {
    
        swap(&
    (queue->
    arr[k / 2]), &
    (queue->
    arr[k]));
    
        k = k / 2;

    }

}


// 下沉操作
void sink(PriorityQueue* queue, int k) {
    
    while (2 * k = queue->
size) {
    
        int j = 2 * k;
    
        if (j  queue->
    size &
    &
     queue->
    arr[j]  queue->
arr[j + 1]) {
    
            j++;

        }
    
        if (queue->
    arr[k] >
    = queue->
arr[j]) {
    
            break;

        }
    
        swap(&
    (queue->
    arr[k]), &
    (queue->
    arr[j]));
    
        k = j;

    }

}


// 插入元素
void insert(PriorityQueue* queue, int val) {
    
    if (queue->
    size == queue->
capacity) {
    
        printf("Priority queue is full.\n");
    
        return;

    }
    
    queue->
    arr[++queue->
    size] = val;
    
    swim(queue, queue->
    size);

}


// 删除最大元素
int deleteMax(PriorityQueue* queue) {
    
    if (queue->
size == 0) {
    
        printf("Priority queue is empty.\n");
    
        return -1;

    }
    
    int max = queue->
    arr[1];
    
    swap(&
    (queue->
    arr[1]), &
    (queue->
    arr[queue->
    size--]));
    
    sink(queue, 1);
    
    return max;

}


// 打印优先队列
void printPriorityQueue(PriorityQueue* queue) {
    
    printf("Priority Queue: ");
    
    for (int i = 1;
     i = queue->
    size;
 i++) {
    
        printf("%d ", queue->
    arr[i]);

    }
    
    printf("\n");

}


int main() {
    
    PriorityQueue* queue = initPriorityQueue(10);
    
    insert(queue, 3);
    
    insert(queue, 10);
    
    insert(queue, 5);
    
    insert(queue, 1);
    

    printPriorityQueue(queue);
    

    int max = deleteMax(queue);
    
    printf("Delete max: %d\n", max);
    

    printPriorityQueue(queue);
    

    free(queue->
    arr);
    
    free(queue);
    
    return 0;

}
    

在上述代码中，我们使用了一个数组来存储优先队列的元素，数组的第一个元素不使用，从数组的第二个元素开始存储元素。通过 swim 和 sink 操作来维持优先队列的性质，其中 swim 操作用于插入元素后的上浮操作，sink 操作用于删除元素后的下沉操作。 insert 函数用于插入元素， deleteMax 函数用于删除最大元素。在 main 函数中，我们演示了优先队列的使用过程。

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！