Trong hướng dẫn này, bạn sẽ tìm hiểu hàng đợi ưu tiên là gì. Ngoài ra, bạn sẽ tìm hiểu về các triển khai của nó trong Python, Java, C và C ++.
Hàng đợi ưu tiên là một loại hàng đợi đặc biệt trong đó mỗi phần tử được liên kết với một mức độ ưu tiên và được phục vụ theo mức độ ưu tiên của nó. Nếu các phần tử có cùng mức độ ưu tiên xảy ra, chúng sẽ được phân phát theo thứ tự của chúng trong hàng đợi.
Nói chung, giá trị của bản thân phần tử được xem xét để gán mức độ ưu tiên.
Ví dụ: Phần tử có giá trị cao nhất được coi là phần tử có mức ưu tiên cao nhất. Tuy nhiên, trong các trường hợp khác, chúng ta có thể giả sử phần tử có giá trị thấp nhất là phần tử có mức ưu tiên cao nhất. Trong các trường hợp khác, chúng ta có thể đặt mức độ ưu tiên theo nhu cầu của mình.
Xóa yếu tố ưu tiên cao nhất
Sự khác biệt giữa hàng đợi ưu tiên và hàng đợi bình thường
Trong một hàng đợi, quy tắc nhập trước xuất trước được thực hiện trong khi trong hàng đợi ưu tiên, các giá trị được xóa trên cơ sở mức độ ưu tiên . Phần tử có mức ưu tiên cao nhất sẽ bị xóa trước.
Triển khai hàng đợi ưu tiên
Hàng đợi ưu tiên có thể được triển khai bằng cách sử dụng một mảng, một danh sách được liên kết, một cấu trúc dữ liệu đống hoặc một cây tìm kiếm nhị phân. Trong số các cấu trúc dữ liệu này, cấu trúc dữ liệu heap cung cấp việc triển khai hiệu quả các hàng đợi ưu tiên.
Do đó, chúng tôi sẽ sử dụng cấu trúc dữ liệu heap để triển khai hàng đợi ưu tiên trong hướng dẫn này. Một triển khai max-heap được thực hiện trong các hoạt động sau. Nếu bạn muốn tìm hiểu thêm về nó, vui lòng truy cập max-heap và mean-heap.
Dưới đây là một phân tích so sánh về các triển khai khác nhau của hàng đợi ưu tiên.
| Hoạt động | nhìn trộm | chèn | xóa bỏ |
|---|---|---|---|
| Danh sách liên kết | O(1) | O(n) | O(1) |
| Binary Heap | O(1) | O(log n) | O(log n) |
| Cây tìm kiếm nhị phân | O(1) | O(log n) | O(log n) |
Hoạt động hàng đợi ưu tiên
Các hoạt động cơ bản của hàng đợi ưu tiên là chèn, loại bỏ và duyệt các phần tử.
Trước khi nghiên cứu hàng đợi ưu tiên, vui lòng tham khảo cấu trúc dữ liệu heap để hiểu rõ hơn về heap nhị phân vì nó được sử dụng để triển khai hàng đợi ưu tiên trong bài viết này.
1. Chèn một phần tử vào hàng đợi ưu tiên
Việc chèn một phần tử vào hàng đợi ưu tiên (max-heap) được thực hiện theo các bước sau.
- Chèn phần tử mới vào cuối cây.
Chèn một phần tử vào cuối hàng đợi - Làm nặng cây.
Làm đông đúc sau khi chèn
Thuật toán chèn một phần tử vào hàng đợi ưu tiên (max-heap)
Nếu không có nút, hãy tạo một NewNode. else (một nút đã có mặt) chèn newNode vào cuối (nút cuối cùng từ trái sang phải.) heapify mảng
Đối với Min Heap, thuật toán trên được sửa đổi để parentNodeluôn nhỏ hơn newNode.
2. Xóa một phần tử khỏi hàng đợi ưu tiên
Việc xóa một phần tử khỏi hàng đợi ưu tiên (max-heap) được thực hiện như sau:
- Chọn phần tử sẽ bị xóa.
Chọn phần tử sẽ bị xóa - Trao đổi nó với phần tử cuối cùng.
Trao đổi với phần tử nút lá cuối cùng - Loại bỏ phần tử cuối cùng.
Loại bỏ lá phần tử cuối cùng - Làm nặng cây.
Xếp chồng lên hàng đợi ưu tiên
Thuật toán xóa một phần tử trong hàng đợi ưu tiên (max-heap)
Nếu nodeToBeDeleted là leafNode thì loại bỏ node Khác hoán đổi nodeToBeDeleted với cuối cùngLeafNode xóa noteToBeDeleted heapify mảng
Đối với Min Heap, thuật toán trên được sửa đổi để cả hai childNodesđều nhỏ hơn currentNode.
3. Nhìn trộm từ Hàng đợi Ưu tiên (Tìm tối đa / phút)
Phép toán Peek trả về phần tử lớn nhất từ Max Heap hoặc phần tử tối thiểu từ Min Heap mà không xóa nút.
Đối với cả Max heap và Min Heap
trả về rootNode
4. Trích xuất-Max / Min từ Hàng đợi Ưu tiên
Extract-Max trả về nút có giá trị lớn nhất sau khi xóa nó khỏi Max Heap trong khi Extract-Min trả về nút có giá trị nhỏ nhất sau khi xóa nó khỏi Min Heap.
Triển khai hàng đợi ưu tiên bằng Python, Java, C và C ++
Python Java C C ++ # Priority Queue implementation 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))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList 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 hT.get(largest)) largest = l; if (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 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 hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); 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); ) )
// Priority Queue implementation in C #include 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 array(largest)) largest = l; if (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 = 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(""); ) // 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); )
// Priority Queue implementation in C++ #include #include 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 &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 hT(largest)) largest = l; if (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 &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 &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector 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); )
Ứng dụng hàng đợi ưu tiên
Một số ứng dụng của hàng đợi ưu tiên là:
- Thuật toán Dijkstra
- để triển khai ngăn xếp
- để cân bằng tải và xử lý ngắt trong hệ điều hành
- để nén dữ liệu trong mã Huffman
