在C語言中,要使用優先隊列(priority queue),你需要使用堆(heap)數據結構來實現。堆是一種特殊的二叉樹,具有以下性質:
在C語言中,可以使用數組來表示二叉堆。對于大根堆,數組中的每個元素都比其子節點的值要大;對于小根堆,數組中的每個元素都比其子節點的值要小。
以下是C語言中使用優先隊列的一般步驟:
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int size;
} PriorityQueue;
void insert(PriorityQueue* queue, int value) {
if (queue->size >= MAX_SIZE) {
printf("Priority queue is full.\n");
return;
}
// 插入新元素到堆的最后
int i = queue->size;
queue->data[i] = value;
// 調整堆,確保滿足堆的性質
while (i > 0 && queue->data[i] > queue->data[(i - 1) / 2]) {
// 交換當前節點和父節點的值
int temp = queue->data[i];
queue->data[i] = queue->data[(i - 1) / 2];
queue->data[(i - 1) / 2] = temp;
i = (i - 1) / 2; // 更新當前節點的索引
}
queue->size++; // 更新堆的大小
}
int deleteMax(PriorityQueue* queue) {
if (queue->size == 0) {
printf("Priority queue is empty.\n");
return -1; // 表示空值或錯誤
}
int max = queue->data[0]; // 保存堆頂元素
queue->size--; // 更新堆的大小
// 將最后一個元素移動到堆頂
queue->data[0] = queue->data[queue->size];
// 調整堆,確保滿足堆的性質
int i = 0;
while (2 * i + 1 < queue->size) {
int left = 2 * i + 1; // 左子節點的索引
int right = 2 * i + 2; // 右子節點的索引
int largest = i; // 最大值的索引
// 找到較大的子節點
if (left < queue->size && queue->data[left] > queue->data[largest]) {
largest = left;
}
if (right < queue->size && queue->data[right] > queue->data[largest]) {
largest = right;
}
if (largest == i) {
break; // 已經滿足堆的性質,退出循環
}
// 交換當前節點和較大子節點的值
int temp = queue->data[i];
queue->data[i] = queue->data[largest];
queue->data[largest] = temp;
i = largest; // 更新當前節點的索引
}
return max;
}
int main() {
PriorityQueue queue;
queue.size = 0;
insert(&queue, 5);
insert