一、优先队列概念
优先队列是一种特殊的队列，元素出队顺序不是FIFO，而是按照优先级：
每次出队的是优先级最高（或最低）的元素
二、两种实现方式对比
| 特性 | 使用数组/链表（朴素实现） | 使用堆（推荐实现） |
|---|---|---|
| 入队时间复杂度 | O(1) | O(log n) |
| 出队（获取最高优先级）时间复杂度 | O(n) | O(log n) |
| 查找最高优先级 | O(n) | O(1) |
三、数组实现
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); } }五、时间复杂度对比分析
各种实现的时间复杂度：
| 操作 | 无序数组/链表 | 有序数组 | 堆 |
|---|---|---|---|
| 插入(入队) | O(1) | O(n) | O(log n) |
| 删除最大(出队) | O(n) | O(1) | O(log n) |
| 获取最大(查看) | O(n) | O(1) | O(1) |
| 构建 | O(1) | O(n log n) | O(n) |
