C语言优先队列的应用的全代码
时间: 2023-07-09 07:09:27 浏览: 42
以下是C语言优先队列的应用示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
typedef struct {
int key;
/* 其他数据字段 */
} Element;
typedef struct {
Element heap[MAX_HEAP_SIZE];
int size;
} Heap;
Heap *create_heap() {
Heap *heap = (Heap *) malloc(sizeof(Heap));
heap->size = 0;
return heap;
}
int parent(int i) {
return (i - 1) / 2;
}
int left_child(int i) {
return 2 * i + 1;
}
int right_child(int i) {
return 2 * i + 2;
}
void swap(Element *a, Element *b) {
Element temp = *a;
*a = *b;
*b = temp;
}
void insert(Heap *heap, Element e) {
if (heap->size >= MAX_HEAP_SIZE) {
printf("Error: heap overflow!\n");
exit(EXIT_FAILURE);
}
int i = heap->size++;
heap->heap[i] = e;
while (i > 0 && heap->heap[i].key > heap->heap[parent(i)].key) {
swap(&heap->heap[i], &heap->heap[parent(i)]);
i = parent(i);
}
}
Element delete_max(Heap *heap) {
if (heap->size <= 0) {
printf("Error: heap underflow!\n");
exit(EXIT_FAILURE);
}
Element max = heap->heap[0];
heap->heap[0] = heap->heap[--heap->size];
int i = 0;
while (left_child(i) < heap->size) {
int j = left_child(i);
if (right_child(i) < heap->size && heap->heap[right_child(i)].key > heap->heap[left_child(i)].key) {
j = right_child(i);
}
if (heap->heap[i].key >= heap->heap[j].key) {
break;
}
swap(&heap->heap[i], &heap->heap[j]);
i = j;
}
return max;
}
int main() {
Heap *heap = create_heap();
Element e1 = {10};
insert(heap, e1);
Element e2 = {20};
insert(heap, e2);
Element e3 = {30};
insert(heap, e3);
Element e4 = {5};
insert(heap, e4);
Element e5 = {15};
insert(heap, e5);
Element e6 = {25};
insert(heap, e6);
printf("Heap elements: ");
while (heap->size > 0) {
Element max = delete_max(heap);
printf("%d ", max.key);
}
printf("\n");
return 0;
}
```
在这个示例中,我们定义了一个元素(Element)结构体,其中包含一个关键字(key)字段和其他数据字段。我们还定义了一个堆(Heap)结构体,其中包含一个存储元素数组和堆大小的字段。
我们实现了堆的基本操作,例如插入和删除最大元素。插入操作将元素插入堆中,并将其上移以满足堆的性质。删除操作将堆的根节点删除,并将其替换为堆的最后一个元素。然后,它将新根节点下移以满足堆的性质。
在main函数中,我们创建了一个堆,并插入了一些元素。然后,我们执行删除操作,直到堆为空,并打印删除的元素。