用c语言实现一个优先级队列
时间: 2024-05-11 11:17:59 浏览: 10
优先级队列是一种特殊的队列,它的每个元素都有一个优先级。在队列中,高优先级的元素会先被处理,而低优先级的元素则会被放置到队列的末尾。下面是一个简单的优先级队列的 C 语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int priority;
int value;
} node;
typedef struct {
node *nodes;
int len;
int size;
} priority_queue;
void push(priority_queue *q, int priority, int value) {
if (q->len == q->size) {
q->size *= 2;
q->nodes = (node*)realloc(q->nodes, q->size * sizeof(node));
}
int i = q->len++;
while (i > 0) {
int p = (i - 1) / 2;
if (q->nodes[p].priority <= priority) {
break;
}
q->nodes[i] = q->nodes[p];
i = p;
}
q->nodes[i].priority = priority;
q->nodes[i].value = value;
}
int pop(priority_queue *q) {
if (q->len == 0) {
return -1;
}
int ret = q->nodes[0].value;
q->len--;
node last = q->nodes[q->len];
int i = 0;
while (i * 2 + 1 < q->len) {
int a = i * 2 + 1, b = i * 2 + 2;
if (b < q->len && q->nodes[b].priority < q->nodes[a].priority) {
a = b;
}
if (q->nodes[a].priority >= last.priority) {
break;
}
q->nodes[i] = q->nodes[a];
i = a;
}
q->nodes[i] = last;
return ret;
}
priority_queue *new_priority_queue() {
priority_queue *q = (priority_queue*)malloc(sizeof(priority_queue));
q->size = 1;
q->len = 0;
q->nodes = (node*)malloc(q->size * sizeof(node));
return q;
}
void free_priority_queue(priority_queue *q) {
free(q->nodes);
free(q);
}
int main() {
priority_queue *q = new_priority_queue();
push(q, 3, 10);
push(q, 1, 20);
push(q, 2, 30);
push(q, 0, 40);
while (q->len > 0) {
printf("%d ", pop(q));
}
free_priority_queue(q);
return 0;
}
```
在这个实现中,我们使用了一个结构体 `node` 存储每个元素的优先级和值,一个结构体 `priority_queue` 存储队列的所有元素。使用 `push` 函数将新元素添加到队列中,使用 `pop` 函数从队列中删除并返回具有最高优先级的元素。我们还提供了一个 `new_priority_queue` 函数用于创建一个新的队列,并提供了一个 `free_priority_queue` 函数用于释放队列。在 `main` 函数中,我们首先创建了一个新的队列,然后向队列中添加了四个元素,每个元素都有不同的优先级和值。最后,我们使用 `pop` 函数从队列中删除所有元素,并将它们打印出来。