Öncelik Kuyruk Veri Yapısı

İçindekiler

Öncelik Kuyruğunun Uygulanması
Öncelik Kuyruk İşlemleri
Python, Java, C ve C ++ 'da Öncelikli Kuyruk Uygulamaları
Öncelikli Kuyruk Uygulamaları

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); )