Menü

Çizim ile C ++ 'da Öncelik Sırası Veri Yapısı

  • Ana
  • Diğer
  • Çizim ile C ++ 'da Öncelik Sırası Veri Yapısı

priority queue data structure c with illustration

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Çizim ile C ++ 'da Öncelik Kuyruğuna Giriş.

Priority Queue, son eğitimimizde bahsettiğimiz kuyruğun bir uzantısıdır.

Kuyruğa belirli açılardan benzemekle birlikte aşağıdaki noktalarda sıradan kuyruktan farklılık gösterir:

  • Öncelik kuyruğundaki her öğe bir öncelik ile ilişkilendirilir.
  • En yüksek önceliğe sahip öğe, kuyruktan kaldırılacak ilk öğedir.
  • Birden fazla öğe aynı önceliğe sahipse, kuyruktaki sıraları dikkate alınır.

=> Absolute C ++ Eğitim Serisi İçin Tıklayınız.

C ++

Öncelik kuyruğunu kuyruğun değiştirilmiş bir versiyonu olarak görselleştirebiliriz, tek fark, öğe kuyruktan çıkarıldığında, en yüksek önceliğe sahip öğe önce alınır. Bu nedenle, öğeleri önceliğe göre işlememiz gerektiğinde kuyruklar yerine öncelik kuyruklarını kullanmayı tercih ediyoruz.

Ne öğreneceksin:

Temel işlemler

Öncelik kuyruğu tarafından desteklenen bazı temel işlemleri tartışalım.

  • Ekle (öğe, öncelik): Öncelik sırasına belirli bir önceliğe sahip bir öğe ekler.
  • getHighestPriority (): En yüksek önceliğe sahip bir öğe döndürür.
  • deleteHighestPriority (): En yüksek önceliğe sahip bir öğeyi kaldırır.

Yukarıdaki işlemlerin dışında isEmpty (), isFull () ve peek () gibi normal kuyruk işlemlerini de kullanabiliriz.

İllüstrasyon

Öncelik kuyruğunun bir resmini görelim. Basitlik amacıyla, öncelik kuyruğundaki öğeler olarak ASCII karakterlerini kullanacağız. ASCII değeri ne kadar yüksekse, öncelik o kadar yüksektir.

Başlangıç ​​durumu - Öncelik Kuyruğu (PQ) - {} => boş

öncelik kuyruğunun resmi

Yukarıdaki çizimden, ekleme işleminin sıradan bir kuyruğa benzer olduğunu görüyoruz. Ancak öncelik kuyruğu için 'deleteHighestPriority' dediğimizde, en yüksek önceliğe sahip öğe önce kaldırılır.

Bu nedenle, bu işlevi ilk kez çağırdığımızda, O öğesi kaldırılırken, ikinci kez, G ve A'dan daha yüksek önceliğe sahip olduğundan M öğesi kaldırılır.

C ++ 'da Öncelik Sıralarının Uygulanması

Öncelik sıraları aşağıdakiler kullanılarak uygulanabilir:

# 1) Diziler / Bağlantılı listeler

Öncelik sıralarını dizileri kullanarak gerçekleştirebiliriz ve bu, öncelik sıralarının en basit uygulamasıdır.

Öncelik kuyruğundaki öğeleri temsil etmek için aşağıdaki gibi bir yapı tanımlayabiliriz:

struct pq_item{ int item; int priority; };

Her ürün için de önceliği ilan ettik.

Öncelik kuyruğuna yeni bir öğe eklemek için öğeyi dizinin sonuna eklememiz yeterlidir.

GetHighestPriority () kullanarak öğeyi kuyruktan almak için, diziyi baştan döndürmemiz ve en yüksek önceliğe sahip öğeyi döndürmemiz gerekir.

Benzer şekilde, deleteHighestPriority işlemini kullanarak öğeyi kuyruktan çıkarmak için, tüm dizide gezinmemiz ve en yüksek önceliğe sahip öğeyi silmemiz gerekir. Ardından, silinen öğeden sonraki tüm diğer öğeleri bir konum geriye taşıyın.

Bağlantılı bir liste kullanarak öncelik sırasını da uygulayabiliriz. Diziler gibi tüm işlemleri benzer şekilde gerçekleştirebiliriz. Tek fark, deleteHighestPriority'yi çağırdıktan sonra öğeleri taşımamız gerekmemesidir.

# 2) Yığınlar

Bir öncelik kuyruğu uygulamak için yığın kullanmak en verimli yoldur ve bağlantılı listeler ve dizilere kıyasla çok daha iyi performans sağlar. Bağlantılı liste ve dizinin aksine, yığın uygulaması, öncelik kuyruğunun ekleme ve silme işlemleri için O (logn) süresi alır. İşlemi alın, getHighestPriority O (1) süresi alır.

# 3) C ++ 'da Standart Şablon Kitaplığında (STL) Yerleşik Öncelik Sırası

C ++ 'da, en yüksek öğe kuyruktaki ilk öğe olacak ve tüm öğeler azalan sırada olacak şekilde tasarlanmış bir kapsayıcı uyarlamalı sınıf olarak bir öncelik kuyruğuna sahibiz.

Dolayısıyla, öncelik kuyruğundaki her öğenin sabit bir önceliği vardır.

STL'de öncelikli kuyruk uygulamasını içeren sınıfımız var.

Öncelik kuyruğu tarafından desteklenen çeşitli işlemler aşağıdaki gibidir:

  1. öncelik_queue :: size (): Sıranın boyutunu döndürür.
  2. Priority_queue :: empty (): Kuyruğun boş olup olmadığını kontrol eder ve durumunu döndürür.
  3. öncelik_queue :: top (): Öncelik kuyruğunun en üstteki öğesine bir başvuru döndürür.
  4. Priority_queue :: push (): Öncelik kuyruğunun sonuna bir öğe ekler.
  5. öncelik_queue :: pop (): İlk öğeyi öncelik kuyruğundan kaldırır.
  6. öncelik_queue :: takas (): Bir öncelik kuyruğunun içeriğini aynı tür ve boyuttaki başka biriyle değiştirmek için kullanılır.
  7. öncelik sırası değeri türü: Değer türü, bir öncelik kuyruğunda depolanan öğenin türünü verir. Bu aynı zamanda şablon parametresinin eşanlamlısıdır.
  8. öncelik_queue :: yerleştirme (): Kuyruğun en üstündeki öncelik kuyruğu kabına yeni bir öğe eklemek için kullanılır.

Bir sonraki programda, C ++ 'da STL'deki öncelik kuyruğunun işlevselliğini göreceğiz.

#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << ' '; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << ' Top element of the queue(pq.top()): ' << pq.top(); cout << ' The priority queue pq is : '; displaypq(pq); cout << ' Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; }

Çıktı:

sol dış birleşim vs sol birleşim

Sıranın boyutu (pq.size ()): 5
Sıranın en üst öğesi (pq.top ()): 9
Öncelik sırası pq: 9 7 5 3 1
Pq.pop () işleminden sonra öncelik sırası: 7 5 3 1

Öncelik Kuyruğu için Java Uygulaması

Java'da öncelik kuyruğu, kuyruktaki tüm öğelerin, kuyrukla birlikte sağlanan bir karşılaştırıcı kullanılarak doğal sıraya veya özel sıralamaya göre sıralandığı özel bir kuyruktur.

Java'da bir öncelik sırası aşağıda gösterildiği gibi görünür:

Öncelik sırası için Java Uygulaması

Java öncelik kuyruğunda, öğeler, en az öğe kuyruğun önünde ve en büyük öğe kuyruğun arkasında olacak şekilde düzenlenir. Bu nedenle, öğeyi öncelik sırasından kaldırdığımızda, kaldırılan her zaman en küçük öğedir.

Java'da öncelik kuyruğunu uygulayan sınıf 'PriorityQueue' dir ve Java'nın koleksiyon çerçevesinin bir parçasıdır. Java'nın 'Kuyruk' arayüzünü uygular.

Aşağıda, Java PriorityQueue sınıfı için sınıf hiyerarşisi verilmiştir.

Java PriorityQueue sınıfı için sınıf hiyerarşisi

Aşağıda, Java'da öğeler olarak tam sayıların kullanıldığı bir Öncelik Sırası işlevi Örneği verilmiştir.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println(' After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println(' After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( ' Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i

Çıktı:

peek () :: Baş değeri: 1
Öncelik sırası:
1 3 5 7
Anket () işlevinden sonra, öncelik sırası:
3 7 5
Kaldır (5) işlevinden sonra, öncelik sırası:
3 7
Öncelik sırası 3 içerir ?: true
Dizi öğeleri:
Değer: 3
Değer: 7

Yukarıdaki programda, Integer nesnesi içeren PriorityQueue nesnesini oluşturmak için Java'nın PriorityQueue sınıfını kullanıyoruz. 'Ekle' işlevini kullanarak sıraya elemanlar ekliyoruz. Daha sonra anket () işlevi çağrılır ve en az öğe olan öğeyi kuyruğun önünden siler.

Yine parametre olarak belirtilen öğeyi kuyruktan kaldıran 'remove ()' işlevini çağırıyoruz. Kuyrukta belirli bir öğenin olup olmadığını kontrol etmek için 'Contains ()' işlevini de kullanıyoruz. Son olarak, “toArray ()” işlevini kullanarak kuyruğu bir dizi nesnesine dönüştürüyoruz.

Uygulama

  • İşletim sistemi yük dengeleme ve kesme işleyicileri: Yük dengeleme ve kesintilerin işlenmesi gibi işletim sistemi işlevleri, öncelik sıraları kullanılarak gerçekleştirilir. Yük dengeleme faaliyeti, yük dengelememizi etkin bir şekilde gerçekleştirmek için kaynakları en yüksek önceliğe sahip planlar. Kesinti işleme, kesmelere en yüksek önceliğe sahip hizmet verilerek gerçekleştirilir. Bu işlevsellik, öncelik sıraları kullanılarak etkin bir şekilde uygulanabilir.
  • Yönlendirme: Yönlendirme, minimum geri dönüş süresi ile maksimum verim elde etmemiz için ağ kaynaklarını yönlendirmek için kullanılan bir işlevdir. Bu aynı zamanda öncelik kuyruğu kullanılarak da uygulanabilir.
  • Hastane Acil Durumu: Hastane acil servisinde, hastanın durumunun ne kadar ağır olduğuna göre hastalar bakıma alınır. Bu, öncelik sıraları kullanılarak simüle edilebilir.
  • Dijkstra’nın En Kısa Yol Algoritması: Burada grafik bir bitişiklik listesi olarak saklanır ve Dijkstra’nın en kısa yol algoritmasını uygulamak için minimum ağırlıklı kenarı bitişik listeden verimli bir şekilde çıkarmak için bir öncelik kuyruğu kullanabiliriz.
  • Öncelik kuyruğu, yayılma ağacını uygularken düğüm anahtarlarını depolamak ve minimum anahtar düğümünü çıkarmak için de kullanılabilir.

Sonuç

Öncelik sıraları, sıranın uzantısından başka bir şey değildir. Ancak FIFO yaklaşımını kullanarak öğe ekleyen / kaldıran kuyruklardan farklı olarak, öncelik kuyruğunda öğeler önceliğe göre kuyruktan kaldırılır. Böylece, kuyruktaki her öğe bir öncelik ile ilişkilendirilir ve en yüksek önceliğe sahip öğe, kuyruktan çıkarılacak ilk öğedir.

Öncelik kuyruğunun üç ana işlemi vardır: insert (), getHighestPriority () ve deleteHighestPriority (). Öncelik kuyruğu, diziler veya bağlantılı liste kullanılarak uygulanabilir, ancak çalışma çok verimli değildir. Öncelik kuyruğu yığınlar kullanılarak da uygulanabilir ve performans çok daha hızlıdır.

C ++ 'da, bir öncelik kuyruğunun işlevselliğini uygulayan bir konteyner sınıfımız da var. Java'da, bir öncelik kuyruğunun işlevselliğini sağlayan yerleşik bir sınıf öncelikli kuyruğu vardır.

Öncelik kuyruğu, temel olarak öğelerin önceliğe göre işlenmesini gerektiren uygulamalarda kullanılır. Örneğin, kesme işlemede kullanılır.

Yaklaşan eğitimimiz, kuyruğun bir başka uzantısı olan dairesel kuyrukla ilgili her şeyi keşfedecek.

=> Uzmanlardan Tam C ++ Kursu İçin Burayı Ziyaret Edin.

Önerilen Kaynaklar

^