优先队列是一种特殊的队列,其中每个元素都有一个优先级。高优先级的元素会比低优先级的元素先被处理。
优先队列是一种特殊的队列,它不遵循先进先出的原则,而是根据元素的优先级来决定出队顺序。在优先队列中,不管元素的入队顺序如何,优先级高的元素会优先出队。
优先队列内部一般使用堆(二叉堆)来实现,方便高效地维护元素的优先级顺序。

▼Java复制代码import java.util.PriorityQueue; import java.util.Comparator; public class PriorityQueueExample { public static void main(String[] args) { // 创建最小堆(默认) PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.offer(30); minHeap.offer(10); minHeap.offer(20); System.out.println("优先队列: " + minHeap); // 注意:打印顺序可能不是实际的优先级顺序 // 查看最高优先级元素(最小值) int highestPriority = minHeap.peek(); System.out.println("最高优先级元素: " + highestPriority); // 输出: 10 // 移除最高优先级元素 int removed = minHeap.poll(); System.out.println("移除的元素: " + removed); // 输出: 10 // 创建最大堆(通过比较器) PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); maxHeap.offer(30); maxHeap.offer(10); maxHeap.offer(20); System.out.println("最大堆顶部元素: " + maxHeap.peek()); // 输出: 30 } }
▼Java复制代码public class BinaryHeapPriorityQueue { private int[] heap; private int size; private int capacity; private boolean isMinHeap; // true表示最小堆,false表示最大堆 public BinaryHeapPriorityQueue(int capacity, boolean isMinHeap) { this.capacity = capacity; this.heap = new int[capacity]; this.size = 0; this.isMinHeap = isMinHeap; } // 获取父节点索引 private int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 private int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 private int rightChild(int i) { return 2 * i + 2; } // 交换两个节点 private void swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } // 向上调整 private void heapifyUp(int i) { int parentIndex = parent(i); if (isMinHeap) { while (i > 0 && heap[parentIndex] > heap[i]) { swap(i, parentIndex); i = parentIndex; parentIndex = parent(i); } } else { while (i > 0 && heap[parentIndex] < heap[i]) { swap(i, parentIndex); i = parentIndex; parentIndex = parent(i); } } } // 向下调整 private void heapifyDown(int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); if (isMinHeap) { if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } } else { if (left < size && heap[left] > heap[smallest]) { smallest = left; } if (right < size && heap[right] > heap[smallest]) { smallest = right; } } if (smallest != i) { swap(i, smallest); heapifyDown(smallest); } } // 插入元素 public void insert(int key) { if (size == capacity) { throw new IllegalStateException("优先队列已满"); } // 将新元素插入到末尾 heap[size] = key; size++; // 进行向上调整以维持堆性质 heapifyUp(size - 1); } // 移除并返回最高优先级元素 public int extractTop() { if (isEmpty()) { throw new IllegalStateException("优先队列为空"); } int top = heap[0]; // 将最后一个元素放到根节点 heap[0] = heap[size - 1]; size--; // 进行向下调整以维持堆性质 heapifyDown(0); return top; } // 查看最高优先级元素 public int peek() { if (isEmpty()) { throw new IllegalStateException("优先队列为空"); } return heap[0]; } // 判断队列是否为空 public boolean isEmpty() { return size == 0; } // 获取队列大小 public int size() { return size; } public static void main(String[] args) { // 创建最小堆 BinaryHeapPriorityQueue minHeap = new BinaryHeapPriorityQueue(10, true); minHeap.insert(30); minHeap.insert(10); minHeap.insert(20); System.out.println("最高优先级元素: " + minHeap.peek()); // 输出: 10 System.out.println("移除的元素: " + minHeap.extractTop()); // 输出: 10 System.out.println("新的最高优先级元素: " + minHeap.peek()); // 输出: 20 // 创建最大堆 BinaryHeapPriorityQueue maxHeap = new BinaryHeapPriorityQueue(10, false); maxHeap.insert(30); maxHeap.insert(10); maxHeap.insert(20); System.out.println("最高优先级元素: " + maxHeap.peek()); // 输出: 30 } }
▼Javascript复制代码class PriorityQueue { constructor(compareFunction = (a, b) => a - b) { this.heap = []; this.compare = compareFunction; // 默认为最小堆 } // 获取父节点索引 parent(i) { return Math.floor((i - 1) / 2); } // 获取左子节点索引 leftChild(i) { return 2 * i + 1; } // 获取右子节点索引 rightChild(i) { return 2 * i + 2; } // 交换两个节点 swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; } // 向上调整 heapifyUp(i) { let current = i; let parentIndex = this.parent(current); while (current > 0 && this.compare(this.heap[current], this.heap[parentIndex]) < 0) { this.swap(current, parentIndex); current = parentIndex; parentIndex = this.parent(current); } } // 向下调整 heapifyDown(i) { let current = i; let leftIndex = this.leftChild(current); let rightIndex = this.rightChild(current); let size = this.heap.length; let smallest = current; if (leftIndex < size && this.compare(this.heap[leftIndex], this.heap[smallest]) < 0) { smallest = leftIndex; } if (rightIndex < size && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) { smallest = rightIndex; } if (smallest !== current) { this.swap(current, smallest); this.heapifyDown(smallest); } } // 添加元素 enqueue(element) { this.heap.push(element); this.heapifyUp(this.heap.length - 1); } // 移除并返回最高优先级元素 dequeue() { if (this.isEmpty()) { throw new Error("优先队列为空"); } const top = this.heap[0]; const last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this.heapifyDown(0); } return top; } // 查看最高优先级元素 peek() { if (this.isEmpty()) { throw new Error("优先队列为空"); } return this.heap[0]; } // 判断队列是否为空 isEmpty() { return this.heap.length === 0; } // 获取队列大小 size() { return this.heap.length; } } // 使用示例 // 最小堆 const minHeap = new PriorityQueue(); minHeap.enqueue(30); minHeap.enqueue(10); minHeap.enqueue(20); console.log("最高优先级元素:", minHeap.peek()); // 输出: 10 console.log("移除的元素:", minHeap.dequeue()); // 输出: 10 console.log("队列大小:", minHeap.size()); // 输出: 2 // 最大堆 const maxHeap = new PriorityQueue((a, b) => b - a); maxHeap.enqueue(30); maxHeap.enqueue(10); maxHeap.enqueue(20); console.log("最高优先级元素:", maxHeap.peek()); // 输出: 30
▼Python复制代码import heapq class MinPriorityQueue: def __init__(self): self.heap = [] // 添加元素 def enqueue(self, item): heapq.heappush(self.heap, item) // 移除并返回最高优先级元素 def dequeue(self): if self.is_empty(): raise Exception("优先队列为空") return heapq.heappop(self.heap) // 查看最高优先级元素 def peek(self): if self.is_empty(): raise Exception("优先队列为空") return self.heap[0] // 判断队列是否为空 def is_empty(self): return len(self.heap) == 0 // 获取队列大小 def size(self): return len(self.heap) class MaxPriorityQueue: def __init__(self): self.heap = [] // 添加元素(取负数实现最大堆) def enqueue(self, item): heapq.heappush(self.heap, -item) // 移除并返回最高优先级元素 def dequeue(self): if self.is_empty(): raise Exception("优先队列为空") return -heapq.heappop(self.heap) // 查看最高优先级元素 def peek(self): if self.is_empty(): raise Exception("优先队列为空") return -self.heap[0] // 判断队列是否为空 def is_empty(self): return len(self.heap) == 0 // 获取队列大小 def size(self): return len(self.heap) # 使用示例 if __name__ == "__main__": // 最小堆 min_queue = MinPriorityQueue() min_queue.enqueue(30) min_queue.enqueue(10) min_queue.enqueue(20) print("最高优先级元素:", min_queue.peek()) # 输出: 10 print("移除的元素:", min_queue.dequeue()) # 输出: 10 print("队列大小:", min_queue.size()) # 输出: 2 // 最大堆 max_queue = MaxPriorityQueue() max_queue.enqueue(30) max_queue.enqueue(10) max_queue.enqueue(20) print("最高优先级元素:", max_queue.peek()) # 输出: 30
▼C复制代码#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_SIZE 100 typedef struct { int heap[MAX_SIZE]; int size; bool isMinHeap; // true表示最小堆,false表示最大堆 } PriorityQueue; // 初始化优先队列 void initialize(PriorityQueue *pq, bool isMinHeap) { pq->size = 0; pq->isMinHeap = isMinHeap; } // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; } // 交换两个元素 void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // 向上调整 void heapifyUp(PriorityQueue *pq, int i) { int p = parent(i); if (pq->isMinHeap) { while (i > 0 && pq->heap[p] > pq->heap[i]) { swap(&pq->heap[i], &pq->heap[p]); i = p; p = parent(i); } } else { while (i > 0 && pq->heap[p] < pq->heap[i]) { swap(&pq->heap[i], &pq->heap[p]); i = p; p = parent(i); } } } // 向下调整 void heapifyDown(PriorityQueue *pq, int i) { int smallest = i; int left = leftChild(i); int right = rightChild(i); if (pq->isMinHeap) { if (left < pq->size && pq->heap[left] < pq->heap[smallest]) { smallest = left; } if (right < pq->size && pq->heap[right] < pq->heap[smallest]) { smallest = right; } } else { if (left < pq->size && pq->heap[left] > pq->heap[smallest]) { smallest = left; } if (right < pq->size && pq->heap[right] > pq->heap[smallest]) { smallest = right; } } if (smallest != i) { swap(&pq->heap[i], &pq->heap[smallest]); heapifyDown(pq, smallest); } } // 判断队列是否为空 bool isEmpty(PriorityQueue *pq) { return pq->size == 0; } // 判断队列是否已满 bool isFull(PriorityQueue *pq) { return pq->size == MAX_SIZE; } // 获取队列大小 int size(PriorityQueue *pq) { return pq->size; } // 入队 void enqueue(PriorityQueue *pq, int item) { if (isFull(pq)) { printf("优先队列已满,无法入队\n"); return; } pq->heap[pq->size] = item; pq->size++; heapifyUp(pq, pq->size - 1); } // 出队 int dequeue(PriorityQueue *pq) { if (isEmpty(pq)) { printf("优先队列为空,无法出队\n"); return -1; } int top = pq->heap[0]; pq->heap[0] = pq->heap[pq->size - 1]; pq->size--; if (pq->size > 0) { heapifyDown(pq, 0); } return top; } // 查看队列顶部元素 int peek(PriorityQueue *pq) { if (isEmpty(pq)) { printf("优先队列为空,无法查看顶部元素\n"); return -1; } return pq->heap[0]; } int main() { // 创建最小堆 PriorityQueue minHeap; initialize(&minHeap, true); enqueue(&minHeap, 30); enqueue(&minHeap, 10); enqueue(&minHeap, 20); printf("最小堆顶部元素: %d\n", peek(&minHeap)); // 输出: 10 printf("出队的元素: %d\n", dequeue(&minHeap)); // 输出: 10 printf("队列大小: %d\n", size(&minHeap)); // 输出: 2 // 创建最大堆 PriorityQueue maxHeap; initialize(&maxHeap, false); enqueue(&maxHeap, 30); enqueue(&maxHeap, 10); enqueue(&maxHeap, 20); printf("最大堆顶部元素: %d\n", peek(&maxHeap)); // 输出: 30 return 0; }
▼Go复制代码package main import ( "container/heap" "fmt" ) // IntHeap 定义一个整数切片类型 type IntHeap []int // Len 返回堆的长度 func (h IntHeap) Len() int { return len(h) } // Less 定义优先级(小的元素优先,最小堆) func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // Swap 交换元素 func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } // Push 向堆中添加元素 func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) } // Pop 从堆中移除元素 func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } // MaxHeap 定义最大堆 type MaxHeap []int func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // 大的元素优先 func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) } func (h *MaxHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } // 自定义优先队列结构 type PriorityQueue struct { items []int isMinHeap bool } // NewPriorityQueue 创建新的优先队列 func NewPriorityQueue(isMinHeap bool) *PriorityQueue { return &PriorityQueue{ items: []int{}, isMinHeap: isMinHeap, } } // 获取父节点索引 func parent(i int) int { return (i - 1) / 2 } // 获取左子节点索引 func leftChild(i int) int { return 2*i + 1 } // 获取右子节点索引 func rightChild(i int) int { return 2*i + 2 } // 向上调整 func (pq *PriorityQueue) heapifyUp(i int) { for i > 0 { p := parent(i) if pq.isMinHeap { if pq.items[p] <= pq.items[i] { break } } else { if pq.items[p] >= pq.items[i] { break } } // 交换元素 pq.items[i], pq.items[p] = pq.items[p], pq.items[i] i = p } } // 向下调整 func (pq *PriorityQueue) heapifyDown(i int) { size := len(pq.items) for { smallest := i left := leftChild(i) right := rightChild(i) if pq.isMinHeap { if left < size && pq.items[left] < pq.items[smallest] { smallest = left } if right < size && pq.items[right] < pq.items[smallest] { smallest = right } } else { if left < size && pq.items[left] > pq.items[smallest] { smallest = left } if right < size && pq.items[right] > pq.items[smallest] { smallest = right } } if smallest == i { break } pq.items[i], pq.items[smallest] = pq.items[smallest], pq.items[i] i = smallest } } // Enqueue 添加元素到优先队列 func (pq *PriorityQueue) Enqueue(item int) { pq.items = append(pq.items, item) pq.heapifyUp(len(pq.items) - 1) } // Dequeue 移除并返回优先级最高的元素 func (pq *PriorityQueue) Dequeue() (int, error) { if pq.IsEmpty() { return 0, fmt.Errorf("优先队列为空") } top := pq.items[0] lastIndex := len(pq.items) - 1 pq.items[0] = pq.items[lastIndex] pq.items = pq.items[:lastIndex] if len(pq.items) > 0 { pq.heapifyDown(0) } return top, nil } // Peek 查看优先级最高的元素 func (pq *PriorityQueue) Peek() (int, error) { if pq.IsEmpty() { return 0, fmt.Errorf("优先队列为空") } return pq.items[0], nil } // IsEmpty 判断队列是否为空 func (pq *PriorityQueue) IsEmpty() bool { return len(pq.items) == 0 } // Size 获取队列大小 func (pq *PriorityQueue) Size() int { return len(pq.items) } func main() { // 使用标准库实现 fmt.Println("使用Go标准库heap包实现:") // 最小堆 minHeap := &IntHeap{} heap.Init(minHeap) heap.Push(minHeap, 30) heap.Push(minHeap, 10) heap.Push(minHeap, 20) fmt.Println("最高优先级元素:", (*minHeap)[0]) // 输出: 10 fmt.Println("出队的元素:", heap.Pop(minHeap)) // 输出: 10 fmt.Println("队列大小:", minHeap.Len()) // 输出: 2 // 最大堆 maxHeap := &MaxHeap{} heap.Init(maxHeap) heap.Push(maxHeap, 30) heap.Push(maxHeap, 10) heap.Push(maxHeap, 20) fmt.Println("最高优先级元素:", (*maxHeap)[0]) // 输出: 30 // 使用自定义实现 fmt.Println("\n使用自定义优先队列实现:") // 最小堆 minPQ := NewPriorityQueue(true) minPQ.Enqueue(30) minPQ.Enqueue(10) minPQ.Enqueue(20) top, _ := minPQ.Peek() fmt.Println("最高优先级元素:", top) // 输出: 10 popped, _ := minPQ.Dequeue() fmt.Println("出队的元素:", popped) // 输出: 10 fmt.Println("队列大小:", minPQ.Size()) // 输出: 2 // 最大堆 maxPQ := NewPriorityQueue(false) maxPQ.Enqueue(30) maxPQ.Enqueue(10) maxPQ.Enqueue(20) topMax, _ := maxPQ.Peek() fmt.Println("最高优先级元素:", topMax) // 输出: 30 }
▼C++复制代码#include <iostream> #include <vector> #include <queue> #include <functional> // 使用STL的优先队列 void stlPriorityQueueExample() { // 默认是最大堆 std::priority_queue<int> maxHeap; maxHeap.push(30); maxHeap.push(10); maxHeap.push(20); std::cout << "最大堆顶部元素: " << maxHeap.top() << std::endl; // 输出: 30 maxHeap.pop(); std::cout << "移除后的顶部元素: " << maxHeap.top() << std::endl; // 输出: 20 // 创建最小堆 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; minHeap.push(30); minHeap.push(10); minHeap.push(20); std::cout << "最小堆顶部元素: " << minHeap.top() << std::endl; // 输出: 10 } // 自定义优先队列实现 template <typename T> class PriorityQueue { private: std::vector<T> heap; bool isMinHeap; // 获取父节点索引 int parent(int i) { return (i - 1) / 2; } // 获取左子节点索引 int leftChild(int i) { return 2 * i + 1; } // 获取右子节点索引 int rightChild(int i) { return 2 * i + 2; } // 向上调整 void heapifyUp(int i) { while (i > 0) { int p = parent(i); if ((isMinHeap && heap[i] >= heap[p]) || (!isMinHeap && heap[i] <= heap[p])) { break; } std::swap(heap[i], heap[p]); i = p; } } // 向下调整 void heapifyDown(int i) { int size = heap.size(); int smallest = i; while (true) { int left = leftChild(i); int right = rightChild(i); if (isMinHeap) { if (left < size && heap[left] < heap[smallest]) { smallest = left; } if (right < size && heap[right] < heap[smallest]) { smallest = right; } } else { if (left < size && heap[left] > heap[smallest]) { smallest = left; } if (right < size && heap[right] > heap[smallest]) { smallest = right; } } if (smallest == i) { break; } std::swap(heap[i], heap[smallest]); i = smallest; } } public: PriorityQueue(bool isMin = true) : isMinHeap(isMin) {} // 添加元素 void push(T item) { heap.push_back(item); heapifyUp(heap.size() - 1); } // 移除并返回最高优先级元素 T pop() { if (isEmpty()) { throw std::runtime_error("优先队列为空"); } T top = heap[0]; heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { heapifyDown(0); } return top; } // 查看最高优先级元素 T top() { if (isEmpty()) { throw std::runtime_error("优先队列为空"); } return heap[0]; } // 判断队列是否为空 bool isEmpty() { return heap.empty(); } // 获取队列大小 size_t size() { return heap.size(); } }; int main() { stlPriorityQueueExample(); std::cout << "\n自定义优先队列实现:" << std::endl; // 最小堆 PriorityQueue<int> minHeap(true); minHeap.push(30); minHeap.push(10); minHeap.push(20); std::cout << "最高优先级元素: " << minHeap.top() << std::endl; // 输出: 10 std::cout << "移除的元素: " << minHeap.pop() << std::endl; // 输出: 10 std::cout << "队列大小: " << minHeap.size() << std::endl; // 输出: 2 // 最大堆 PriorityQueue<int> maxHeap(false); maxHeap.push(30); maxHeap.push(10); maxHeap.push(20); std::cout << "最高优先级元素: " << maxHeap.top() << std::endl; // 输出: 30 return 0; }
测验答案
- 优先队列按照元素的优先级决定出队顺序.
- 入队操作的时间复杂度是O(log n),因为需要进行上浮操作来维护堆。
- Java中的PriorityQueue默认是最小堆。可以通过提供一个自定义的Comparator来创建最大堆,例如:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());- 二叉堆是一种特殊的完全二叉树,它有两种类型:最小堆(父节点值小于等于子节点)和最大堆(父节点值大于等于子节点)。它的特性包括:完全二叉树结构、父子节点间的大小关系、可以高效地找到最大/最小元素。