# 優先隊列 > 原文： [https://www.programiz.com/dsa/priority-queue](https://www.programiz.com/dsa/priority-queue) #### 在本教程中，您將學習什么是優先隊列。 另外，您還將找到 C，C++ ，Java 和 Python 中優先隊列操作的工作示例。 優先隊列是一種特殊的隊列，其中每個元素都與一個優先級相關聯，并根據其優先級進行服務。 如果出現具有相同優先級的元素，則會根據其在隊列中的順序為其提供服務。 通常，元素本身的值被認為用于分配優先級。 例如：具有最高值的元素被視為最高優先級元素。 但是，在其他情況下，我們可以將具有最低值的元素視為最高優先級元素。 在其他情況下，我們可以按需設置優先級。  優先級最高的元素先出隊 * * * ### 優先隊列與隊列有何不同？ 在隊列中，實現**先進先出規則**，而在優先隊列中，基于優先級刪除值**。 優先級最高的元素將首先被刪除。** * * * ## 優先隊列的實現 可以使用數組，鏈表，堆數據結構或二叉搜索樹來實現優先隊列。 在這些數據結構中，堆數據結構提供了優先隊列的有效實現。 下面給出優先隊列的不同實現的比較分析。 | ? | 獲取 | 插入 | 刪除 | | --- | --- | --- | --- | | 鏈表 | `O(1)` | `O(n)` | `O(1)` | | 二叉堆 | `O(1)` | `O(log n)` | `O(log n)` | | 二叉搜索樹 | `O(1)` | `O(log n)` | `O(log n)` | * * * ## 優先隊列操作 優先隊列的基本操作是插入，刪除和查看元素。 在研究優先隊列之前，請參考[堆數據結構](/dsa/heap-data-structure)，以更好地了解二叉堆，因為該二叉堆用于實現本文中的優先隊列。 * * * ### 從優先隊列插入元素 通過以下步驟將元素插入優先隊列（最大堆）。 1. 在樹的末尾插入新元素。  在隊列的末尾插入元素 2. 對樹建堆。  插入后堆 將元素插入優先隊列的算法（最大堆） ``` If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array ``` 對于最小堆，對上述算法進行了修改，以使`parentNode`始終小于`newNode`。 * * * ### 從優先隊列中刪除元素 從優先隊列（最大堆）中刪除元素的操作如下： 1. 選擇要刪除的元素。  選擇要刪除的元素 2. 將其與最后一個元素交換。  與最后一個葉節點元素 交換 3. 刪除最后一個元素。  刪除最后一個元素/葉子 4. 對樹建堆。  堆處理隊列 刪除優先隊列中元素的算法（最大堆） ``` If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array ``` 對于最小堆，對上述算法進行了修改，以使`childNodes`均小于`currentNode`。 * * * ### 從優先隊列中窺視（查找最大值/最小值） 窺視操作從最大堆中返回最大元素，或者從最小堆中返回最小元素，而不刪除節點。 對于最大堆和最小堆 ``` return rootNode ``` * * * ### 從優先隊列中提取最大/最小 從最大堆中刪除節點后，`Extract-Max`返回具有最大值的節點，而從最小堆中刪除節點后，`Extract-Min`返回具有最小值的節點。 * * * ## Python，Java，C/C++ 示例 ```py # Max-Heap data structure in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r # Swap and continue heapifying if root is not largest if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array[i]: break array[i], array[size - 1] = array[size - 1], array[i] array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = [] insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) ``` ```java // Max-Heap data structure in Java import java.util.ArrayList; class Heap { // Function to heapify the tree void heapify(ArrayList<Integer> hT, int i) { int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && hT.get(l) > hT.get(largest)) largest = l; if (r < size && hT.get(r) > hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } // Function to insert an element into the tree void insert(ArrayList<Integer> hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } // Function to delete an element from the tree void deleteNode(ArrayList<Integer> hT, int num) { int size = hT.size(); int i; for (i = 0; i < size; i++) { if (num == hT.get(i)) break; } int temp = hT.get(i); hT.set(i, hT.get(size - 1)); hT.set(size - 1, temp); hT.remove(size - 1); for (int j = size / 2 - 1; j >= 0; j--) { heapify(hT, j); } } // Print the tree void printArray(ArrayList<Integer> array, int size) { for (Integer i : array) { System.out.print(i + " "); } System.out.println(); } // Driver code public static void main(String args[]) { ArrayList<Integer> array = new ArrayList<Integer>(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); } } ``` ```c // Max-Heap data structure in C #include <stdio.h> int size = 0; void swap(int *a, int *b) { int temp = *b; *b = *a; *a = temp; } // Function to heapify the tree void heapify(int array[], int size, int i) { if (size == 1) { printf("Single element in the heap"); } else { // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && array[l] > array[largest]) largest = l; if (r < size && array[r] > array[largest]) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) { swap(&array[i], &array[largest]); heapify(array, size, largest); } } } // Function to insert an element into the tree void insert(int array[], int newNum) { if (size == 0) { array[0] = newNum; size += 1; } else { array[size] = newNum; size += 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); } } } // Function to delete an element from the tree void deleteRoot(int array[], int num) { int i; for (i = 0; i < size; i++) { if (num == array[i]) break; } swap(&array[i], &array[size - 1]); size -= 1; for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); } } // Print the array void printArray(int array[], int size) { for (int i = 0; i < size; ++i) printf("%d ", array[i]); printf("\n"); } // Driver code int main() { int array[10]; insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); } ``` ```cpp // Max-Heap data structure in C++ #include <iostream> #include <vector> using namespace std; // Function to swap position of two elements void swap(int *a, int *b) { int temp = *b; *b = *a; *a = temp; } // Function to heapify the tree void heapify(vector<int> &hT, int i) { int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < size && hT[l] > hT[largest]) largest = l; if (r < size && hT[r] > hT[largest]) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) { swap(&hT[i], &hT[largest]); heapify(hT, largest); } } // Function to insert an element into the tree void insert(vector<int> &hT, int newNum) { int size = hT.size(); if (size == 0) { hT.push_back(newNum); } else { hT.push_back(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } // Function to delete an element from the tree void deleteNode(vector<int> &hT, int num) { int size = hT.size(); int i; for (i = 0; i < size; i++) { if (num == hT[i]) break; } swap(&hT[i], &hT[size - 1]); hT.pop_back(); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } // Print the tree void printArray(vector<int> &hT) { for (int i = 0; i < hT.size(); ++i) cout << hT[i] << " "; cout << "\n"; } // Driver code int main() { vector<int> heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); } ``` * * * ## 優先隊列應用 優先隊列的一些應用是： * Dijkstra 算法 * 用于實現棧 * 用于操作系統中的負載平衡和中斷處理 * 用于霍夫曼代碼中的數據壓縮