Öncelik Sırası Nedir?

Bir Öncelik Kuyruğu, bir tür Öğeler (değerler) koleksiyonunu tutan bir tür veri yapısıdır ve her öğe, kuyruk sırasını belirleyen ilişkili bir öncelik ile sıralanır. En düşük önceliğe sahip öğeler ilk önce kuyruğa
alınır . Adında “ Queue ” olsa bile , PriorityQueue türü eşit önceliğe sahip öğeler için ilk giren ilk çıkar (FIFO) semantiğini garanti etmez .

Öncelik sıraları, grafik problemlerinde, ağaç problemlerinde, zamanlama görevlerinde, Bant genişliği yönetiminde ve daha fazlasında kullanılır.

Arka planda, Microsoft, öncelik sırasını yönetmek için bir dizi kullanır,
öncelik sıraları aynı ilkelerden oluştukları için min\max yığınları olarak kullanılabilir.
Varsayılan olarak Min Heap bu sınıf tarafından uygulanır ancak bu, farklı bir karşılaştırıcı sağlanarak değiştirilebilir.

Min yığınlarında, her öğe altındaki öğelerden daha küçüktür.
Maksimum yığınlarda, her öğe altındaki öğelerden daha büyüktür.
Eklenen her yeni eleman, yukarıdan aşağıya, soldan sağa bakarak bir sonraki boş noktaya eklenir,
Böylece ikili ağacın her seviyesinin sonuncusu hariç dolu olduğunu bildiğimizi varsayarsak, belirli bir eleman elde edebiliriz, ebeveyn, dizideki dizine göre çocuklar ve yükseklik. bu uygulamada min\max öğesi her zaman dizideki ilk öğe olarak görünür. bu da min öğesini sabit zamanda almayı sağlar.
Elemanları kuyruğa aldığımızda\sıkıştırdığımızda, öbeği bir kez daha geçerli kılmak için öbeği “yığınlamak” istiyoruz, bu da ögeyi bir sonraki öğeye (yukarıdan aşağıya, soldan sağa) taşır ve eleman doğru yerde.

Öncelik Sırası Nasıl Kullanılır?

Kullanımı oldukça basittir,
PriorityQueue<TElement,TPriority> iki tür sınıfı kabul eder
TElement, öğenin türüdür
ve TPriority, öncelik türüdür.
bir öncelik türü seçerken, varsayılan bir karşılaştırıcıya veya uyguladığınız bir karşılaştırıcıya sahip olduğundan emin olun.

Bu örnekte, bir öncelik olarak tamsayılarla bir dizi öğelerinin öncelik kuyruğunu başlatıyoruz,
varsayılan olarak PriorityQueue öğeleri artan düzende (en az önce) sıralar.
Bu programın çıktısı aşağıdaki gibidir:

John Lennon 1940'ta
doğdu Ringo Starr3 1940'ta
doğdu Ringo Starr2 1940'ta doğdu
Ringo Starr1 1940'ta doğdu
Paul McCartney 1942'de
doğdu George Harrison 1943'te doğdu

İşlem çıkış kodu 0 ile tamamlandı.

bu, öncelik sırasının neden FIFO olarak düzenlenmediğini gösteren harika bir örnektir; Görüldüğü gibi hem John Lennon hem de Ringo Starr(1\2\3) 1940 doğumludur, ancak onları ekleme sırasına göre alamıyoruz.

Özel Karşılaştırıcı Nasıl Kullanılır?

PriorityQueue sınıfı, bir karşılaştırma nesnesini kabul eden bir kurucuya sahiptir.
daha spesifik olarak, bir IComparer<TPriority>
Örneğin, bir maksimum yığın simüle etmek istiyorsak farklı bir karşılaştırıcı sağlarız:

Kaputun altındaki CompareTo, mevcut öğeyi sağlanan öğeyle karşılaştırıyor, ilki daha büyükse -1
, ikincisi daha büyükse 1
, eşitlerse 0 döndürürüz.

//actual IL code:
public int CompareTo(int value)
{
 if (m_value < value) return -1;
 if (m_value > value) return 1;
 return 0;
}

aynı mantığa dayalı diğer sınıf türleri için bazı özel Karşılaştırıcıları kolayca uygulayabiliriz.

Beklendiği gibi çıktı:

George Harrison 1943'te doğdu
Paul McCartney 1942'de doğdu Ringo Starr2
1940'ta
doğdu Ringo Starr1 1940'ta doğdu
Ringo Starr3 1940'ta doğdu
John Lennon 1940'ta doğdu

İşlem çıkış kodu 0 ile tamamlandı.

LeetCode!

Bu makaleyi bitirmek için basit bir LeetCode sorusunu çözmek için öncelik sırası sınıfını kullanacağız.
(2) Dizideki K. En Büyük Öğe — LeetCode

Bir tamsayı dizisi numsve bir tamsayı verildiğinde, dizideki en büyük öğeyik döndürür . kth

Bunun ayrı öğe kth değil, sıralı düzendeki en büyük öğe olduğuna dikkat edin .kth

Tabii ki, diziyi sıralayabilir ve öğeyi elde etmek için K kez çalıştırabiliriz,
bu O(N log N)'de olur, oysa N dizideki öğelerin sayısı
ve sabit bir Uzay karmaşıklığıdır (sıralamak için gereken alanı yok sayarsak) dizi).

ancak öğeyi bir min-yığın kullanarak elde etmek için bir alan değiş tokuşu ile daha az zaman kullanabiliriz.

Nums dizisinde görünen her sayı için bunu yığına atıyoruz, ancak yığın boyutu K'yi aştığında o yığından min öğesini çıkaracağız,

sonuçta K En büyük öğeleri bu yığında tutar, böylece döngünün sonuna geldiğimizde, yığının tepesi istediğimiz sayı olacaktır.

Örneğin, çalışma zamanı günlükleri:

iteration 1 (3, 3) Count =1
iteration 2 (2, 2) (3, 3) Count = 2
iteration 3 (1, 1) (3, 3) (2, 2) Count = 3 → after dequeue min (3, 3) (2, 2)
iteration 4 (2, 2) (3, 3) (5, 5) Count = 3 → after dequeue min (3, 3) (5, 5)
iteration 5 (3, 3) (5, 5) (6, 6) Count = 3 → after dequeue min (5, 5) (6, 6)
iteration 6 (4, 4) (6, 6) (5, 5) Count = 3 → after dequeue min (6, 6) (5, 5)
pq.Peek() will return the min element in that heap, in that case it is (5, 5)

bu çözüm O(N * Log K) zaman karmaşıklığında ve O(K) Uzay karmaşıklığında çalışır

Bu makalenin bu kısmına geldiyseniz, okuduğunuz için teşekkür etmek istiyorum ve umarım sizin için yararlı bir yazı olmuştur.
Daha fazla öğrenmem için bana motivasyon verdiğiniz için teşekkür ederim :)