Linux环境下的C语言编程（四十二）

一、优先队列概念

优先队列是一种特殊的队列，元素出队顺序不是FIFO，而是按照优先级：

• 每次出队的是优先级最高（或最低）的元素

二、两种实现方式对比

三、数组实现

1. 数组无序实现

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int size; } PriorityQueueArray; // 初始化 void initPriorityQueueArray(PriorityQueueArray* pq) { pq->size = 0; } // 入队 O(1) - 直接添加到尾部 void enqueueArray(PriorityQueueArray* pq, int value) { if (pq->size >= MAX_SIZE) { printf("队列已满！\n"); return; } pq->data[pq->size++] = value; } // 出队 O(n) - 需要遍历找到最大值 int dequeueArray(PriorityQueueArray* pq) { if (pq->size == 0) { printf("队列为空！\n"); return INT_MIN; } // 找到最大值的索引 int maxIndex = 0; for (int i = 1; i < pq->size; i++) { if (pq->data[i] > pq->data[maxIndex]) { maxIndex = i; } } // 保存最大值 int maxValue = pq->data[maxIndex]; // 用最后一个元素填补空缺 pq->data[maxIndex] = pq->data[pq->size - 1]; pq->size--; return maxValue; } // 查看最高优先级 O(n) int peekArray(PriorityQueueArray* pq) { if (pq->size == 0) return INT_MIN; int maxValue = pq->data[0]; for (int i = 1; i < pq->size; i++) { if (pq->data[i] > maxValue) { maxValue = pq->data[i]; } } return maxValue; } 2. 数组有序

四、堆实现

堆是一种特殊的完全二叉树，满足：

• 最大堆：父节点 ≥ 子节点

• 最小堆：父节点 ≤ 子节点

1. 最大堆实现优先队列

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_HEAP_SIZE 100 typedef struct { int data[MAX_HEAP_SIZE]; int size; } MaxHeap; // 辅助函数：交换两个元素 void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // 初始化堆 void initMaxHeap(MaxHeap* heap) { heap->size = 0; } // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左孩子索引 int leftChild(int i) { return 2 * i + 1; } // 获取右孩子索引 int rightChild(int i) { return 2 * i + 2; } // 上浮操作（维护堆性质）O(log n) void heapifyUp(MaxHeap* heap, int index) { while (index > 0 && heap->data[parent(index)] < heap->data[index]) { swap(&heap->data[parent(index)], &heap->data[index]); index = parent(index); } } // 下沉操作（维护堆性质）O(log n) void heapifyDown(MaxHeap* heap, int index) { int maxIndex = index; int left = leftChild(index); int right = rightChild(index); // 找到当前节点、左孩子、右孩子中的最大值 if (left < heap->size && heap->data[left] > heap->data[maxIndex]) { maxIndex = left; } if (right < heap->size && heap->data[right] > heap->data[maxIndex]) { maxIndex = right; } // 如果当前节点不是最大值，交换并继续下沉 if (index != maxIndex) { swap(&heap->data[index], &heap->data[maxIndex]); heapifyDown(heap, maxIndex); } } // 入队操作 O(log n) void heapEnqueue(MaxHeap* heap, int value) { if (heap->size >= MAX_HEAP_SIZE) { printf("堆已满！\n"); return; } // 1. 将新元素放到末尾 heap->data[heap->size] = value; heap->size++; // 2. 上浮调整 heapifyUp(heap, heap->size - 1); } // 出队操作 O(log n) int heapDequeue(MaxHeap* heap) { if (heap->size == 0) { printf("堆为空！\n"); return INT_MIN; } // 1. 保存堆顶（最大值） int maxValue = heap->data[0]; // 2. 用最后一个元素替换堆顶 heap->data[0] = heap->data[heap->size - 1]; heap->size--; // 3. 下沉调整 heapifyDown(heap, 0); return maxValue; } // 查看堆顶元素 O(1) int heapPeek(MaxHeap* heap) { if (heap->size == 0) return INT_MIN; return heap->data[0]; } // 构建堆 O(n) - 弗洛伊德建堆法 void buildHeap(MaxHeap* heap, int arr[], int n) { // 复制数据 for (int i = 0; i < n; i++) { heap->data[i] = arr[i]; } heap->size = n; // 从最后一个非叶子节点开始下沉 for (int i = n / 2 - 1; i >= 0; i--) { heapifyDown(heap, i); } } // 打印堆（树状结构） void printHeapTree(MaxHeap* heap, int index, int level) { if (index >= heap->size) return; // 先打印右子树 printHeapTree(heap, rightChild(index), level + 1); // 打印当前节点 for (int i = 0; i < level; i++) printf(" "); printf("%d\n", heap->data[index]); // 打印左子树 printHeapTree(heap, leftChild(index), level + 1); }

2. 最小堆实现

typedef struct { int data[MAX_HEAP_SIZE]; int size; } MinHeap; // 最小堆的上浮操作 void minHeapifyUp(MinHeap* heap, int index) { while (index > 0 && heap->data[parent(index)] > heap->data[index]) { swap(&heap->data[parent(index)], &heap->data[index]); index = parent(index); } } // 最小堆的下沉操作 void minHeapifyDown(MinHeap* heap, int index) { int minIndex = index; int left = leftChild(index); int right = rightChild(index); if (left < heap->size && heap->data[left] < heap->data[minIndex]) { minIndex = left; } if (right < heap->size && heap->data[right] < heap->data[minIndex]) { minIndex = right; } if (index != minIndex) { swap(&heap->data[index], &heap->data[minIndex]); minHeapifyDown(heap, minIndex); } }

五、时间复杂度对比分析

各种实现的时间复杂度：