TechCodeview

Öncelik kuyruğu, her öğenin bir önceliğe sahip olması dışında normal kuyruğa benzer şekilde davranan soyut bir veri türüdür; yani en yüksek önceliğe sahip öğe, öncelik kuyruğunda ilk sırada gelir. Öncelik kuyruğundaki öğelerin önceliği, öğelerin öncelik kuyruğundan kaldırılma sırasını belirleyecektir.

Öncelik kuyruğu yalnızca karşılaştırılabilir öğeleri destekler; bu, öğelerin artan veya azalan sırada düzenlendiği anlamına gelir.

javascript yorumu

Örneğin, 1, 3, 4, 8, 14, 22 gibi bazı değerlerin bir öncelik sırasına eklendiğini ve değerlere en küçükten en büyüğe doğru bir sıralama uygulandığını varsayalım. Bu nedenle 1 numarası en yüksek önceliğe sahip olurken 22 numarası en düşük önceliğe sahip olacaktır.

Öncelik kuyruğunun özellikleri

Öncelik kuyruğu, aşağıdaki özellikleri içeren bir kuyruğun uzantısıdır:

• Öncelik kuyruğundaki her öğenin kendisiyle ilişkilendirilmiş bir önceliği vardır.
• Daha yüksek önceliğe sahip bir öğe, daha düşük önceliğe sahip olanın silinmesinden önce silinecektir.
• Öncelik kuyruğundaki iki öğe aynı önceliğe sahipse FIFO ilkesi kullanılarak düzenlenecektir.

Öncelik kuyruğunu bir örnek üzerinden anlayalım.

Aşağıdaki değerleri içeren bir öncelik sıramız var:

1, 3, 4, 8, 14, 22

Tüm değerler artan sırada düzenlenmiştir. Şimdi aşağıdaki işlemleri gerçekleştirdikten sonra öncelik sırasının nasıl görüneceğini gözlemleyeceğiz:

anket():Bu işlev, en yüksek öncelikli öğeyi öncelik kuyruğundan kaldıracaktır. Yukarıdaki öncelik kuyruğunda '1' öğesi en yüksek önceliğe sahiptir, dolayısıyla öncelik kuyruğundan kaldırılacaktır.ekle(2):Bu işlev öncelik sırasına '2' öğesini ekleyecektir. 2, tüm sayılar arasında en küçük eleman olduğundan en yüksek önceliği alacaktır.anket():En yüksek öncelik sırasına sahip olduğu için '2' öğesini öncelik kuyruğundan kaldıracaktır.ekle(5):5, 4'ten büyük ve 8'den küçük olduğundan, 4'ten sonra 5 öğesini ekleyecektir, böylece öncelik kuyruğunda üçüncü en yüksek önceliği elde edecektir.

Öncelik Sırası Türleri

İki tür öncelik sırası vardır:

Artan sıra öncelik sırası:Artan öncelik sıralamasında, daha düşük bir öncelik numarası, bir öncelikte daha yüksek öncelik olarak verilir. Örneğin 1'den 5'e kadar sayıları 1,2,3,4,5 gibi artan şekilde sıralayarak alıyoruz; bu nedenle en küçük sayı, yani 1, öncelik kuyruğunda en yüksek öncelik olarak verilir.
Azalan öncelik sırası sırası:Azalan öncelik kuyruğunda, bir öncelikte daha yüksek öncelik olarak daha yüksek bir öncelik numarası verilir. Örneğin 1'den 5'e kadar olan sayıları 5, 4, 3, 2, 1 gibi azalan şekilde sıralayarak alıyoruz; bu nedenle en büyük sayı, yani 5, öncelik kuyruğunda en yüksek öncelik olarak verilir.

Öncelik kuyruğunun temsili

Şimdi öncelik sırasının tek yönlü bir liste aracılığıyla nasıl temsil edileceğini göreceğiz.

Aşağıda verilen listeyi kullanarak öncelik kuyruğunu oluşturacağız. BİLGİ liste veri öğelerini içerir, PRN liste, mevcut her veri öğesinin öncelik numaralarını içerir. BİLGİ LINK temel olarak bir sonraki düğümün adresini içerir.

Öncelik kuyruğunu adım adım oluşturalım.

Java'yı tostlamak

Öncelik kuyruğu durumunda, daha düşük öncelik numarası daha yüksek öncelik olarak kabul edilir; düşük öncelik numarası = yüksek öncelik.

Aşama 1: Listede, veri değeri 333 olan düşük öncelikli numara 1 olduğundan, aşağıdaki diyagramda gösterildiği gibi listeye eklenecektir:

Adım 2: 333 eklendikten sonra öncelik numarası 2 daha yüksek önceliğe sahip olur ve bu önceliğe ilişkin veri değerleri 222 ve 111 olur. Yani bu veriler FIFO prensibine göre eklenecektir; bu nedenle önce 222, sonra 111 eklenecektir.

Aşama 3: Öncelik 2'ye ait elemanların eklenmesinden sonra, bir sonraki yüksek öncelik numarası 4'tür ve 4 öncelik numarasıyla ilişkili veri elemanları 444, 555, 777'dir. Bu durumda elemanlar FIFO prensibine göre eklenecektir; bu nedenle önce 444, sonra 555 ve ardından 777 eklenecektir.

Adım 4: Öncelik 4'ün elemanları eklendikten sonra, bir sonraki yüksek öncelik numarası 5'tir ve öncelik 5 ile ilişkili değer 666'dır, dolayısıyla kuyruğun sonuna eklenecektir.

Öncelik Sırasının Uygulanması

Öncelik kuyruğu, diziler, bağlantılı liste, yığın veri yapısı ve ikili arama ağacını içeren dört yolla uygulanabilir. Yığın veri yapısı, öncelik kuyruğunu uygulamanın en etkili yoludur, bu nedenle bu başlıkta öncelik kuyruğunu bir yığın veri yapısı kullanarak uygulayacağız. Şimdi öncelikle yığının neden diğer tüm veri yapıları arasında en verimli yol olduğunu anlıyoruz.

Farklı uygulamalar kullanılarak karmaşıklıkların analizi

Yığın Nedir?

Yığın, tam bir ikili ağaç oluşturan ve yığın özelliğini karşılayan ağaç tabanlı bir veri yapısıdır. A, B'nin ana düğümü ise, bir yığındaki tüm A ve B düğümleri için A, B düğümüne göre sıralanır. Bu, ana düğümün değerinin alt düğümün değerinden büyük veya ona eşit olabileceği veya üst düğümün değerinin alt düğümün değerinden küçük veya ona eşit olabileceği anlamına gelir. Bu nedenle iki tür yığın olduğunu söyleyebiliriz:

Maksimum yığın:Maksimum yığın, ana düğümün değerinin alt düğümlerin değerinden büyük olduğu bir yığındır.
Minimum yığın:Min yığını, ana düğümün değerinin alt düğümlerin değerinden daha az olduğu bir yığındır.

Her iki yığın da ikili yığındır, çünkü her biri tam olarak iki alt düğüme sahiptir.

Öncelikli Sıra İşlemleri

Öncelik kuyruğunda gerçekleştirebileceğimiz genel işlemler ekleme, silme ve göz atmadır. Heap veri yapısını nasıl koruyabileceğimizi görelim.

Öğeyi öncelik sırasına ekleme (maksimum yığın)

Öncelik sırasına bir eleman eklersek yukarıdan aşağıya ve soldan sağa bakarak boş yuvaya geçecektir.

Eleman doğru yerde değilse ana düğümle karşılaştırılır; bozuk olduğu tespit edilirse elemanlar değiştirilir. Bu işlem eleman doğru pozisyona yerleştirilene kadar devam eder.

Minimum öğeyi öncelik kuyruğundan kaldırma

Bildiğimiz gibi bir maksimum yığında maksimum öğe kök düğümdür. Kök düğümü kaldırdığımızda boş bir yuva oluşur. Son eklenen eleman bu boş yuvaya eklenecektir. Daha sonra bu öğe alt düğümlerle (sol çocuk ve sağ çocuk) karşılaştırılır ve ikisinden küçük olanla değiştirilir. Yığın özelliği geri yüklenene kadar ağaçta aşağı doğru hareket etmeye devam eder.

Öncelik kuyruğu uygulamaları

Öncelik kuyruğunun uygulamaları şunlardır:

Java dizeleri birleştirir

• Dijkstra'nın en kısa yol algoritmasında kullanılır.
• Prim'in algoritmasında kullanılır
• Huffman kodu gibi veri sıkıştırma tekniklerinde kullanılır.
• Yığın sıralamasında kullanılır.
• Ayrıca işletim sisteminde öncelikli planlama, yük dengeleme ve kesme yönetimi gibi durumlarda da kullanılır.

İkili maksimum yığını kullanarak öncelik kuyruğunu oluşturan program.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>