Bu eğitimde, öncelik sırasının ne olduğunu öğreneceksiniz. Ayrıca, Python, Java, C ve C ++ 'daki uygulamaları hakkında bilgi edineceksiniz.
Öncelik sırası, her bir öğenin bir öncelik ile ilişkilendirildiği ve önceliğine göre sunulduğu özel bir kuyruk türüdür. Aynı önceliğe sahip öğeler ortaya çıkarsa, bunlar kuyruktaki sıralarına göre sunulur.
Genel olarak, önceliğin atanması için öğenin kendisinin değeri dikkate alınır.
Örneğin, en yüksek değere sahip öğe, en yüksek öncelikli öğe olarak kabul edilir. Bununla birlikte, diğer durumlarda, en düşük değere sahip öğeyi en yüksek öncelikli öğe olarak kabul edebiliriz. Diğer durumlarda, ihtiyaçlarımıza göre öncelikler belirleyebiliriz.
En Yüksek Öncelik Öğesini Kaldırma
Öncelik Kuyruğu ve Normal Kuyruk arasındaki fark
Bir sıra olarak, ilk-giren-ilk çıkar kuralı bir öncelik sırasına değerleri çıkarılır ise uygulanan öncelik bazında . Önce en yüksek önceliğe sahip öğe kaldırılır.
Öncelik Kuyruğunun Uygulanması
Öncelik kuyruğu bir dizi, bağlantılı liste, yığın veri yapısı veya ikili arama ağacı kullanılarak uygulanabilir. Bu veri yapıları arasında, yığın veri yapısı, öncelikli kuyrukların verimli bir şekilde uygulanmasını sağlar.
Bu nedenle, bu öğreticide öncelik sırasını uygulamak için yığın veri yapısını kullanacağız. Aşağıdaki işlemlerde bir maks-yığın uygulamasıdır. Bununla ilgili daha fazla bilgi edinmek istiyorsanız, lütfen max-heap ve mean-heap sayfasını ziyaret edin.
Öncelik kuyruğunun farklı uygulamalarının karşılaştırmalı bir analizi aşağıda verilmiştir.
| Operasyonlar | dikizlemek | eklemek | sil |
|---|---|---|---|
| Bağlantılı liste | O(1) | O(n) | O(1) |
| İkili Yığın | O(1) | O(log n) | O(log n) |
| İkili Arama Ağacı | O(1) | O(log n) | O(log n) |
Öncelik Kuyruk İşlemleri
Öncelikli bir kuyruğun temel işlemleri öğeleri ekleme, çıkarma ve gözetlemedir.
Öncelik kuyruğunu incelemeden önce, bu makaledeki öncelik kuyruğunu uygulamak için kullanıldığı için ikili yığın hakkında daha iyi bir anlayış için lütfen yığın veri yapısına bakın.
1. Öncelik Kuyruğuna Bir Eleman Ekleme
Öncelik sırasına (max-heap) bir eleman eklemek aşağıdaki adımlarla yapılır.
- Yeni öğeyi ağacın sonuna ekleyin.
Kuyruğun sonuna bir öğe ekleyin - Ağacı yığınlayın.
Ekledikten sonra yığınla
Öncelik kuyruğuna bir elemanın eklenmesi için algoritma (max-heap)
Düğüm yoksa, yeni bir Düğüm oluşturun. Aksi takdirde (bir düğüm zaten mevcut) newNode'u sonuna (soldan sağa son düğüm) yerleştirin.
Min Heap için, yukarıdaki algoritma parentNode, her zaman daha küçük olacak şekilde değiştirilir newNode.
2. Öncelik Kuyruğundan Bir Eleman Silme
Bir öncelik kuyruğundan (maks-yığın) bir öğeyi silmek şu şekilde yapılır:
- Silinecek öğeyi seçin.
Silinecek öğeyi seçin - Son elementle değiştirin.
Son yaprak düğüm öğesi ile değiştirin - Son öğeyi kaldırın.
Son eleman yaprağını kaldırın - Ağacı yığınlayın.
Öncelik kuyruğunu yığınla
Öncelik kuyruğundaki bir öğenin silinmesi için algoritma (max-heap)
NodeToBeDeleted, leafNode ise lastLeafNode ile Else swap nodeToBeDeleted düğümünü kaldırın noteToBeDeleted diziyi heapify edin
Min Heap için, yukarıdaki algoritma, her ikisi childNodesde daha küçük olacak şekilde değiştirilir currentNode.
3. Öncelik Kuyruğundan Göz Atma (Maksimum / dakika bulun)
Peek işlemi, düğümü silmeden Max Heap'ten maksimum elementi veya Min Heap'ten minimum elementi döndürür.
Hem Max heap hem de Min Heap için
rootNode döndür
4. Öncelik Kuyruğundan Maks / Min Çıkar
Extract-Max, Max Heap'ten kaldırıldıktan sonra maksimum değeri olan düğümü döndürürken Extract-Min, Min Heap'ten çıkardıktan sonra minimum değeri olan düğümü döndürür.
Python, Java, C ve C ++ 'da Öncelikli Kuyruk Uygulamaları
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); )
Öncelikli Kuyruk Uygulamaları
Öncelik kuyruğunun bazı uygulamaları şunlardır:
- Dijkstra algoritması
- yığını uygulamak için
- bir işletim sisteminde yük dengeleme ve kesinti işleme için
- Huffman kodunda veri sıkıştırma için
