c语言中的优先队列
时间: 2023-07-02 08:16:55 浏览: 93
在 C 语言中,优先队列可以使用堆来实现。堆是一种完全二叉树,分为最大堆和最小堆两种类型。最大堆要求父节点的值大于等于其子节点的值,最小堆要求父节点的值小于等于其子节点的值。
在实现优先队列时,可以使用最小堆来存储元素,保证队首元素是最小值。对于插入操作,先将元素插入到堆的末尾,然后执行上滤操作,将新元素上滤到合适的位置。对于弹出操作,将堆顶元素弹出,然后将堆末尾元素放到堆顶,执行下滤操作,将新堆顶元素下滤到合适的位置。
下面是一个简单的优先队列的实现示例,使用最小堆来存储元素:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int size;
} Heap;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void up(Heap *heap, int index) {
int parent = (index - 1) / 2;
if (parent >= 0 && heap->data[parent] > heap->data[index]) {
swap(&heap->data[parent], &heap->data[index]);
up(heap, parent);
}
}
void down(Heap *heap, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int min = index;
if (left < heap->size && heap->data[left] < heap->data[min]) {
min = left;
}
if (right < heap->size && heap->data[right] < heap->data[min]) {
min = right;
}
if (min != index) {
swap(&heap->data[min], &heap->data[index]);
down(heap, min);
}
}
void insert(Heap *heap, int value) {
heap->data[heap->size] = value;
heap->size++;
up(heap, heap->size - 1);
}
int pop(Heap *heap) {
int value = heap->data[0];
heap->data[0] = heap->data[heap->size - 1];
heap->size--;
down(heap, 0);
return value;
}
int main() {
Heap heap = {0};
insert(&heap, 3);
insert(&heap, 1);
insert(&heap, 4);
insert(&heap, 1);
while (heap.size > 0) {
printf("%d ", pop(&heap));
}
printf("\n");
return 0;
}
```
输出结果为:1 1 3 4
阅读全文