Dalam tutorial ini, anda akan mengetahui apa itu barisan keutamaan. Anda juga akan mengetahui pelaksanaannya di Python, Java, C, dan C ++.
Antrian keutamaan adalah jenis giliran khas di mana setiap elemen dikaitkan dengan keutamaan dan dilayan mengikut keutamaannya. Sekiranya elemen dengan keutamaan yang sama berlaku, elemen tersebut disajikan mengikut susunannya dalam barisan.
Secara amnya, nilai elemen itu sendiri dipertimbangkan untuk menetapkan keutamaan.
Contohnya, Elemen dengan nilai tertinggi dianggap sebagai elemen keutamaan tertinggi. Namun, dalam kes lain, kita dapat menganggap elemen dengan nilai terendah sebagai elemen keutamaan tertinggi. Dalam kes lain, kita dapat menetapkan keutamaan mengikut keperluan kita.
Membuang Elemen Keutamaan Tertinggi
Perbezaan antara Baris Prioriti dan Antrian Normal
Dalam antrian, peraturan first-in-first-out dilaksanakan sedangkan, dalam antrian prioritas, nilai dihapus berdasarkan prioritas . Elemen dengan keutamaan tertinggi dikeluarkan terlebih dahulu.
Pelaksanaan Baris Keutamaan
Baris keutamaan dapat dilaksanakan dengan menggunakan array, senarai terpaut, struktur data timbunan, atau pohon carian binari. Di antara struktur data ini, struktur data timbunan menyediakan pelaksanaan antrian keutamaan yang efisien.
Oleh itu, kami akan menggunakan struktur data timbunan untuk melaksanakan antrian keutamaan dalam tutorial ini. Max-heap yang dilaksanakan adalah dalam operasi berikut. Sekiranya anda ingin mengetahui lebih lanjut mengenainya, sila lawati timbunan maksimum dan timbunan rata-rata.
Analisis perbandingan pelbagai pelaksanaan antrian keutamaan diberikan di bawah.
| Operasi | mengintip | masukkan | padam |
|---|---|---|---|
| Senarai Terpaut | O(1) | O(n) | O(1) |
| Timbunan binari | O(1) | O(log n) | O(log n) |
| Pokok Carian Binari | O(1) | O(log n) | O(log n) |
Operasi Baris Keutamaan
Operasi asas barisan keutamaan adalah memasukkan, membuang, dan mengintip elemen.
Sebelum mempelajari antrian keutamaan, rujuk struktur data timbunan untuk pemahaman yang lebih baik mengenai timbunan binari kerana ia digunakan untuk melaksanakan antrian keutamaan dalam artikel ini.
1. Memasukkan Elemen ke dalam Baris Keutamaan
Memasukkan elemen ke dalam barisan keutamaan (max-heap) dilakukan dengan langkah-langkah berikut.
- Masukkan elemen baru di hujung pokok.
Masukkan elemen di hujung barisan - Memanaskan pokok.
Heapify setelah dimasukkan
Algoritma untuk memasukkan elemen ke dalam barisan keutamaan (max-heap)
Sekiranya tidak ada nod, buat Node baru. lain (simpul sudah ada) masukkan Node baru di hujung (simpul terakhir dari kiri ke kanan.) tumpukan array
Untuk Min Heap, algoritma di atas diubah suai agar parentNodeselalu lebih kecil daripada newNode.
2. Menghapus Elemen dari Baris Keutamaan
Menghapus elemen dari barisan keutamaan (max-heap) dilakukan seperti berikut:
- Pilih elemen yang akan dihapuskan.
Pilih elemen yang akan dihapuskan - Tukar dengan elemen terakhir.
Tukar dengan elemen simpul daun terakhir - Keluarkan elemen terakhir.
Keluarkan daun elemen terakhir - Memanaskan pokok.
Padamkan barisan keutamaan
Algoritma untuk penghapusan elemen dalam barisan keutamaan (max-heap)
Sekiranya nodeToBeDeleted adalah leafNode keluarkan simpul Else swap nodeToBeDeleted with the LastLeafNode remove noteToBeDeleted heapify array
Untuk Min Heap, algoritma di atas diubahsuai sehingga keduanya childNodeslebih kecil daripada currentNode.
3. Mengintip dari Baris Prioriti (Cari maksimum / min)
Operasi peek mengembalikan elemen maksimum dari Heap Maksimum atau elemen minimum dari Heap Min tanpa menghapus nod.
Untuk kedua Heap Max dan Min Heap
kembali rootNode
4. Ekstrak-Maks / Min dari Baris Keutamaan
Extract-Max mengembalikan node dengan nilai maksimum setelah mengeluarkannya dari Max Heap sedangkan Extract-Min mengembalikan node dengan nilai minimum setelah mengeluarkannya dari Min Heap.
Pelaksanaan Antrian Prioriti di Python, Java, C, dan 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); )
Aplikasi Baris Keutamaan
Beberapa aplikasi antrian keutamaan adalah:
- Algoritma Dijkstra
- untuk melaksanakan timbunan
- untuk pengimbangan beban dan pengendalian gangguan dalam sistem operasi
- untuk pemampatan data dalam kod Huffman
