Dalam tutorial ini, Anda akan mempelajari apa itu antrian prioritas. Selain itu, Anda akan belajar tentang implementasinya dalam Python, Java, C, dan C ++.
Antrian prioritas adalah jenis antrian khusus di mana setiap elemen dikaitkan dengan prioritas dan disajikan sesuai dengan prioritasnya. Jika elemen dengan prioritas yang sama terjadi, mereka disajikan sesuai dengan urutannya dalam antrian.
Umumnya, nilai elemen itu sendiri dipertimbangkan untuk menetapkan prioritas.
Misalnya, elemen dengan nilai tertinggi dianggap sebagai elemen dengan prioritas tertinggi. Namun, dalam kasus lain, kita dapat mengasumsikan elemen dengan nilai terendah sebagai elemen prioritas tertinggi. Dalam kasus lain, kita dapat menetapkan prioritas sesuai dengan kebutuhan kita.
Menghapus Elemen Prioritas Tertinggi
Perbedaan antara Antrian Prioritas dan Antrian Normal
Dalam antrian, aturan pertama masuk pertama keluar diimplementasikan sedangkan dalam antrian prioritas, nilai-nilai dihapus berdasarkan prioritas . Elemen dengan prioritas tertinggi dihapus terlebih dahulu.
Penerapan Antrian Prioritas
Antrian prioritas dapat diimplementasikan menggunakan larik, daftar tertaut, struktur data heap, atau pohon pencarian biner. Di antara struktur data ini, struktur data heap menyediakan implementasi antrian prioritas yang efisien.
Karenanya, kami akan menggunakan struktur data heap untuk mengimplementasikan antrian prioritas dalam tutorial ini. Implementasi max-heap ada dalam operasi berikut. Jika Anda ingin mempelajarinya lebih lanjut, silakan kunjungi max-heap dan mean-heap.
Analisis komparatif dari berbagai implementasi antrian prioritas diberikan di bawah ini.
| Operasi | mengintip | memasukkan | menghapus |
|---|---|---|---|
| Daftar Tertaut | O(1) | O(n) | O(1) |
| Heap Biner | O(1) | O(log n) | O(log n) |
| Pohon Pencarian Biner | O(1) | O(log n) | O(log n) |
Operasi Antrian Prioritas
Operasi dasar antrian prioritas adalah memasukkan, menghapus, dan mengintip elemen.
Sebelum mempelajari antrean prioritas, harap lihat struktur data heap untuk lebih memahami heap biner karena digunakan untuk mengimplementasikan antrean prioritas dalam artikel ini.
1. Memasukkan Elemen ke Antrian Prioritas
Memasukkan elemen ke dalam antrian prioritas (max-heap) dilakukan dengan langkah-langkah berikut.
- Sisipkan elemen baru di ujung pohon.
Sisipkan elemen di akhir antrian - Heapify the tree.
Heapify setelah penyisipan
Algoritma untuk memasukkan elemen ke dalam antrian prioritas (max-heap)
Jika tidak ada node, buat newNode. else (node sudah ada) masukkan newNode di akhir (node terakhir dari kiri ke kanan.) heapify array
Untuk Min Heap, algoritma di atas dimodifikasi sehingga parentNodeselalu lebih kecil dari newNode.
2. Menghapus Elemen dari Antrian Prioritas
Menghapus elemen dari antrian prioritas (max-heap) dilakukan sebagai berikut:
- Pilih elemen yang akan dihapus.
Pilih elemen yang akan dihapus - Tukar dengan elemen terakhir.
Tukar dengan elemen simpul daun terakhir - Hapus elemen terakhir.
Hapus daun elemen terakhir - Heapify the tree.
Heapify antrian prioritas
Algoritma untuk penghapusan elemen dalam antrian prioritas (max-heap)
Jika nodeToBeDeleted adalah leafNode hapus node Lain tukar nodeToBeDeleted dengan lastLeafNode hapus noteToBeDeleted heapify array
Untuk Min Heap, algoritma di atas dimodifikasi sehingga keduanya childNodeslebih kecil dari currentNode.
3. Mengintip dari Antrean Prioritas (Temukan maks / mnt)
Operasi Peek mengembalikan elemen maksimum dari Max Heap atau elemen minimum dari Min Heap tanpa menghapus node.
Untuk tumpukan Max dan Min Heap
kembalikan rootNode
4. Ambil-Max / Min dari Antrian Prioritas
Extract-Max mengembalikan node dengan nilai maksimum setelah menghapusnya dari Max Heap sedangkan Extract-Min mengembalikan node dengan nilai minimum setelah menghapusnya dari Min Heap.
Implementasi Antrean Prioritas di Python, Java, C, dan C ++
Python Java 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 Antrian Prioritas
Beberapa aplikasi antrian prioritas adalah:
- Algoritma Dijkstra
- untuk mengimplementasikan tumpukan
- untuk penyeimbangan beban dan penanganan interupsi dalam sistem operasi
- untuk kompresi data dalam kode Huffman
