Bölüm 11: Öncelikli Kuyruklar ve Heap

11.1Öncelikli kuyruk ADT'si

Bir veri yapısı iki düzeyde anlatılabilir. Birinci düzey yapının ne yaptığını söyler: hangi işlemler vardır, her işlem neyi değiştirir ve ne döndürür. İkinci düzey bunun nasıl yapıldığını söyler: veriler bellekte hangi biçimde durur, her işlem hangi adımlarla yürür. Birinci düzeydeki tarife soyut veri tipi (abstract data type, kısaca ADT) denir. Öncelikli kuyruk da bir ADT'dir. Aynı ADT birbirinden çok farklı veri yapılarıyla gerçeklenebilir ve bu bölümün ana fikirlerinden biri, seçilen veri yapısının çalışma süresini nasıl değiştirdiğidir.

11.1.1Öncelikli kuyruk nedir?

Sıkışık bir trafiği düşünelim. Araçlar şeritlerde geliş sırasıyla ilerler; öndeki araç önce geçer. Arkadan sireni açık bir ambulans geldiğinde ise sürücüler kenara çekilir ve ambulans hepsinin önüne geçer. Ambulansın öne geçmesinin nedeni erken gelmiş olması değildir. Önceliği yüksektir.

Şekil 11.1 bu düzeni gösteriyor. Aynı düzen bilgisayar sistemlerinde de sık görülür. İşletim sistemi bekleyen süreçler arasından en önemlisini çalıştırır. Bir yazıcı kuyruğunda yöneticinin acil belgesi öne alınabilir. Bir olay simülasyonu, zamanı en erken olan olayı işler. Bu durumların hepsinde bekleyen öğeler bir “öncelik” bilgisi taşır ve sıradaki öğe bu bilgiye göre seçilir.

Tanımın vurguladığı nokta şudur: öncelikli kuyruk yalnız “sıradaki en önemli öğe hangisi?” sorusuna hızlı cevap vermek zorundadır. Bütün öğeleri sıralı tutmak zorunda değildir. Kuyruğun ortasındaki öğelerin kendi aralarında hangi düzende durduğu kullanıcıyı ilgilendirmez. Bu serbestlik, verimli gerçeklemelerin anahtarıdır.

İşlemlerin maliyeti seçilen gerçeklemeye bağlıdır. Öğeler sırasız bir listede tutulursa en öncelikli öğeye yalnız bakmak bile bütün listeyi taramayı, yani O(n) zamanı gerektirir. İkili heap ile ise en öncelikli öğeye bakmak O(1), onu çıkarmak O(log n) sürer.

11.1.2Anahtar, değer ve öncelik

Öncelikli kuyruktaki her öğe iki parçadan oluşur. Birinci parça anahtardır (key): öğenin önceliğini taşır. İkinci parça değerdir (value): kuyrukta saklanmak istenen asıl veridir. Acil servis örneğinde (1, "kalp krizi") ve (4, "burkulma") iki öğedir. Birinci öğenin anahtarı 1, değeri “kalp krizi” metnidir.

Hangi yönün seçildiği bir alışkanlık meselesidir. Goodrich, Tamassia ve Goldwasser'in ders kitabı ADT'yi min-öncelikli kuyruk olarak tanımlar ve işlemlere min(), removeMin() adlarını verir. Bu notta da ADT bu biçimde verilir. Heap kodlarının çoğu ise max-heap üzerindedir; orada işlemler ekle ve silMax adını alır. İki yön arasındaki tek fark karşılaştırmanın yönüdür: min-kuyruk kodundaki her < işareti > ile değiştirilirse max-kuyruk elde edilir. Bu yüzden bir yönde öğrenilen her şey öbür yöne doğrudan taşınır.

En yüksek öncelikli öğe, kuyruğun “önündeki” öğedir. Min-kuyrukta bu, anahtarı en küçük olan öğedir; max-kuyrukta anahtarı en büyük olan öğedir. Aynı en küçük anahtardan birden çok olabilir. O durumda bunlardan herhangi biri önde sayılabilir.

Bu son gözlem önemli bir soruyu doğurur: eşit öncelikli öğeler hangi sırayla çıkar? Öncelikli kuyruk ADT'si bu konuda hiçbir söz vermez. Eşit anahtarlı iki öğeden önce gelenin önce çıkacağı, yani FIFO (first-in, first-out: ilk giren ilk çıkar) düzeninin korunacağı kendiliğinden garanti değildir. Bazı gerçeklemeler bu sırayı tesadüfen korur, bazıları korumaz. Java'nın PriorityQueue sınıfı da bu konuda bir garanti vermez.

Eşitlikte geliş sırasının korunması gerekiyorsa çözüm basittir: anahtara bir geliş sıra numarası eklenir. Her yeni öğe bir sayaçtan artan bir numara alır. Karşılaştırma önce önceliğe bakar; öncelikler eşitse küçük sıra numaralı, yani önce gelmiş öğe önde sayılır. Sıra numaraları hep farklı olduğu için iki öğe artık hiçbir zaman tam eşit olmaz ve sıra kesinleşir.

11.1.3Kuyruk mu, öncelikli kuyruk mu?

Sıradan kuyrukla öncelikli kuyruk arasındaki farkı küçük bir örnek açıkça gösterir.

Ali kuyruğa ilk girdiği hâlde öncelikli kuyruktan en son çıkmıştır. Kuyrukta çıkış sırasını geliş zamanı belirler; öncelikli kuyrukta öncelik belirler. Ece ile Naz'ın göreli sırası ise ADT'nin değil, gerçeklemenin kararıdır. Tabloda geliş sırası korunmuş, ama başka bir gerçekleme Naz'ı Ece'den önce de çıkarabilirdi.

Öncelikli kuyruğu sıradan kuyruğun bir genellemesi olarak da görmek mümkündür. Her öğenin anahtarı geliş zamanı olarak seçilirse, min-öncelikli kuyruk en eski öğeyi, yani kuyruğun önündeki öğeyi verir. Aynı şekilde anahtar olarak geliş zamanının eksisi seçilirse en yeni öğe çıkar ve yapı yığın gibi davranır.

11.1.4Kullanım alanları

Öncelikli kuyruk, “bekleyenler arasından her seferinde en iyisini seç” biçimindeki bütün problemlerde kullanılır. Dört tipik alan şunlardır:

• İşletim sistemleri. Görev (süreç) çizelgelemede yüksek öncelikli süreç işlemciyi önce alır. Örneğin bir kesme işleyicisi kullanıcı arayüzünden, arayüz de arka plandaki yedekleme işinden önce gelir.
• Çizge algoritmaları. Dijkstra'nın en kısa yol algoritması ve A* araması, sıradaki en yakın düğümü bir öncelikli kuyruktan alır. Anahtar, düğümün kaynağa o ana kadar bilinen uzaklığıdır.
• Acil durum yönetimi. Hasta triyajında ve olay yönetiminde en acil vaka önce ele alınır.
• Veri sıkıştırma. Huffman kodlaması her adımda frekansı en düşük iki düğümü birleştirir. Bu iki düğüm bir min-öncelikli kuyruktan iki kez removeMin ile alınır, birleşim düğümü kuyruğa geri eklenir.

Bu örneklerin ortak yanı, öğelerin kuyruğa farklı zamanlarda girmesi ve çıkarma ile ekleme işlemlerinin iç içe gelmesidir. Bütün veri baştan belli olsaydı diziyi bir kez sıralamak yeterdi. Dijkstra algoritmasında ise bir düğüm çıkarıldıktan sonra komşuları kuyruğa eklenir; sıralı bir diziyi her eklemede yeniden düzenlemek pahalıya mal olur. Öncelikli kuyruk tam bu durum için tasarlanmıştır.

11.1.5Temel işlemler ve Java arayüzü

Min-öncelikli kuyruk ADT'si beş işlemle tanımlanır. Tablo 11.2 bu işlemleri ve anlamlarını listeliyor.

Java'da bir ADT'nin sözleşmesi doğal olarak bir arayüzle (interface) yazılır. Arayüz yalnız işlemlerin adlarını, parametrelerini ve dönüş tiplerini verir; işlemlerin nasıl yapılacağını söylemez:

public interface PriorityQueue<K, V> {
    void insert(K key, V value);
    Entry<K, V> min();        // boşsa null
    Entry<K, V> removeMin();  // boşsa null
    int size();
    boolean isEmpty();
}

Arayüz iki tip parametresi alır: anahtar tipi K ve değer tipi V. Entry<K, V> bir (anahtar, değer) çiftini temsil eden küçük bir tiptir; min() ve removeMin() öğenin yalnız değerini değil, anahtarını da döndürsün diye bu tip kullanılır. Yorumlar boş kuyruktaki davranışı belirtir: iki metot da null döndürür. Bazı kütüphaneler bu durumda istisna fırlatır. Hangisinin seçildiği sözleşmenin parçasıdır ve arayüzü kullanan kodun bunu bilmesi gerekir.

Max-öncelikli kuyrukta aynı işlemler max() ve removeMax() adını alır. Bu notun heap kodları max-heap kullanır ve işlemleri Türkçe adlarla verir: ekleme ekle, en büyüğü çıkarma silMax.

Arayüzün kendisi hiçbir maliyet bilgisi taşımaz. Maliyet, arayüzü gerçekleyen sınıfa bağlıdır. Aynı PriorityQueue<K, V> arayüzünü bir sırasız liste, bir sıralı liste ve bir heap ayrı ayrı gerçekleyebilir; kullanıcı kodu değişmez, yalnız çalışma süresi değişir.

11.1.6Örnek işlem dizisi

ADT'nin davranışını bir işlem dizisiyle somutlaştıralım. Boş bir min-öncelikli kuyruğa sırasıyla aşağıdaki işlemler uygulanıyor. Tabloda her işlemin döndürdüğü değer ve işlemden sonraki içerik verilmiştir. İçerik küme parantezleriyle yazıldı, çünkü kuyruğun iç düzeni ADT düzeyinde tanımlı değildir; okumayı kolaylaştırmak için öğeler anahtar sırasıyla dizildi.

Tablodaki üç ayrıntıya dikkat etmek gerekir. Birincisi, min() ile removeMin() aynı öğeyi döndürmüştür, ama yalnız ikincisi onu kuyruktan çıkarır. min()'den sonra içerik değişmemiştir. İkincisi, (3,B) kuyruğa (5,A) ve (9,C)'den sonra girmesine karşın ilk çıkan öğedir; sırayı anahtar belirler. Üçüncüsü, (7,D) en son eklenen öğelerden biridir ama (9,C)'den önce çıkar. Son satırda boş kuyrukta removeMin() çağrılmış ve arayüzün sözleşmesine uygun olarak null dönmüştür.

11.2Liste ile gerçekleme

Öncelikli kuyruğu gerçeklemenin en kolay yolu, öğeleri bir listede tutmaktır. Bu listede öğelerin düzeni için iki seçenek vardır: öğeler ya geldikleri gibi sırasız durur ya da her zaman önceliğe göre sıralı tutulur. İki seçenek de doğru çalışır, ama maliyetleri birbirinin aynadaki görüntüsü gibidir. Birinde ekleme ucuz, çıkarma pahalıdır; öbüründe tersi geçerlidir. Bu kesim iki seçeneği kodla ve izlemelerle karşılaştırır. Kazanılan sezgi, ikili heap'in neden gerekli olduğunu da açıklar.

11.2.1Sırasız liste ve sıralı liste

Sırasız liste (unsorted list) gerçeklemesinde yeni öğe listenin sonuna eklenir. Hiçbir karşılaştırma yapılmaz; ekleme O(1)'dir. Bedel çıkarmada ödenir. En küçük anahtarlı öğe listenin herhangi bir yerinde olabilir. Onu bulmak için listenin bütün öğelerine bakmak gerekir: min ve removeMin O(n) sürer.

Sıralı liste (sorted list) gerçeklemesinde öğeler her zaman anahtar sırasıyla durur. En küçük öğe hep listenin bir ucundadır; min ve removeMin bu uca bakar ve O(1) sürer. Bu kez bedel eklemede ödenir. Yeni öğe sona atılamaz; sırayı bozmamak için doğru yerinin bulunması ve öğelerin kaydırılması gerekir. En kötü durumda bütün öğeler yer değiştirir ve ekleme O(n) olur.

Şekil 11.2 iki durumu yan yana gösteriyor. İki gerçekleme de işlemlerden birini hızlı, öbürünü yavaş yapar. Biri eklemede, diğeri çıkarmada üstündür. Öncelikli kuyruk uygulamalarında ekleme ve çıkarma genellikle yaklaşık eşit sayıda yapılır. Bu durumda yavaş işlem toplam süreyi belirler ve iki gerçekleme de n ekleme ile n çıkarma için O(n²) zaman harcar. İki işlemi dengeleyen yapı ikili heap'tir: orada ikisi de O(log n) sürer.

Sıralı listede sıralamanın yönü bir gerçekleme kararıdır. Şekildeki liste küçükten büyüğe sıralıdır ve en küçük öğe baştadır. Dizi ile gerçeklemede ise en küçüğü dizinin sonunda tutmak daha akıllıcadır. Bunun nedeni, iki temsilde ucuz ucun farklı olmasıdır: dizide son hücreyi silmek, bağlı listede ise baştaki düğümü silmek sabit sürer.

11.2.2Kod izleme: sırasız dizide removeMin()

Sırasız gerçeklemeyi bir dizi üzerinde yazalım. Öğeler a[0]'dan a[n − 1]'e kadar dizide durur ve n öğe sayısını tutar. Ekleme tek satırdır: a[n] = x; n++;. Çıkarma ise şöyledir:

// sırasız dizi: insert(x) { a[n] = x; n++; }  O(1)
public int removeMin() {        // n > 0 olmalı
  int enk = 0;                  // en küçüğün indisi
  for (int k = 1; k < n; k++)
    if (a[k] < a[enk]) enk = k;
  int min = a[enk];
  a[enk] = a[n - 1];  n--;      // son öğe boşluğa
  return min;
}

Kod üç iş yapar. Birinci iş en küçüğün yerini bulmaktır. enk değişkeni o ana kadar görülen en küçük öğenin indisini tutar ve ilk aday olarak 0 alınır. for döngüsü k = 1'den n − 1'e kadar her öğeyi o anki adayla karşılaştırır; daha küçük bir öğe bulunca enk güncellenir. Döngü bittiğinde enk en küçük öğenin indisidir. İkinci iş bu öğeyi min değişkeninde saklamaktır.

Üçüncü iş, çıkarılan öğenin bıraktığı boşluğu kapatmaktır. Dizi sırasız olduğu için öğelerin düzenini korumak gerekmez. Boşluğu kapatmak için sağdaki bütün öğeleri birer sola kaydırmak yerine son öğe boşluğa taşınır ve n bir azaltılır. Bu, tek bir atamadır ve O(1) sürer. Sıralı bir dizide aynı hile kullanılamazdı, çünkü son öğeyi ortaya taşımak sırayı bozardı.

Kodu a = [5, 9, 3, 7, 4], n = 5 dizisi üzerinde izleyelim. Tablo 11.4 döngünün her adımını veriyor.

Beş öğeli dizide 4 karşılaştırma yapıldı. Genel olarak n öğeli dizide döngü n − 1 kez döner. En küçük öğe nerede olursa olsun bu sayı değişmez; en küçük ilk hücrede olsa bile algoritma bunu ancak bütün diziyi gördükten sonra bilebilir. Bu yüzden removeMin her durumda Θ(n) zamanlıdır. min() da aynı taramayı yapar ve maliyeti aynıdır; yalnız sondaki taşıma adımı yoktur.

Sonuçta kalan dizi [5, 9, 4, 7]'dir ve sırasızdır. Bu bir sorun değildir: sırasız gerçekleme zaten düzen tutmaz. Taşıma hilesinin dizinin düzenini değiştirdiğine dikkat edilmeli. 4 dizinin sonundan ortasına geçmiştir.

11.2.3Kod izleme: sıralı dizide insert(4)

Sıralı gerçeklemede en küçüğü dizinin hangi ucunda tutacağımızı seçmek gerekir. En küçük a[0]'da durursa onu çıkarmak, kalan bütün öğeleri birer sola kaydırmayı gerektirir; removeMin O(n) olur ve sıralı gerçeklemenin tek üstünlüğü kaybolur. Doğrusu, diziyi büyükten küçüğe sıralı tutmaktır. O zaman en küçük öğe hep a[n − 1]'dedir ve onu çıkarmak yalnız n'yi bir azaltmaktır:

// sıralı dizi: büyükten küçüğe, min hep a[n-1]
public void insert(int x) {
  int k = n - 1;
  while (k >= 0 && a[k] < x) {    // x'ten küçükler
    a[k + 1] = a[k];              // bir sağa kaydır
    k--;
  }
  a[k + 1] = x;  n++;
}
public int removeMin() { n--; return a[n]; }

insert metodu, yeni öğe x'in yerini sondan başa doğru arar. k son öğeden başlar. a[k] < x olduğu sürece a[k], x'ten küçüktür ve büyükten küçüğe düzende x'ten sonra gelmelidir. Bu yüzden bir sağa, a[k + 1]'e kaydırılır ve k bir azalır. Döngü iki durumda biter: k −1'e iner (yani x bütün öğelerden büyüktür) ya da a[k] ≥ x olan bir öğeye gelinir. İki durumda da x'in yeri k + 1'dir. Koşuldaki k >= 0 denetiminin a[k]'ye erişimden önce yazıldığına dikkat edilmeli: && kısa devre yaptığı için k = −1 olduğunda a[−1] hiç okunmaz.

Kodu a = [9, 7, 5, 3, 2], n = 5 dizisinde insert(4) için izleyelim.

İzlemede iki öğe (2 ve 3) birer sağa kaydı. Kaydırma sırasında dizide geçici olarak aynı değerden iki tane görülür: a[5] = a[4]'ten sonra 2 iki hücrededir. Bu bir hata değildir. a[4]'teki kopyanın üzerine bir sonraki adımda 3, en sonda da 4 yazılır. Kaydırma, “bir öğeyi sağa kopyala, boşalan yere sonrakini yaz” düşüncesiyle çalışır ve takastan daha az atama yapar.

Maliyet, kaydırılan öğe sayısıyla orantılıdır. Yeni öğe en küçükse hiçbir öğe kaymaz ve ekleme sabit sürer. En kötü durum, yeni öğenin bütün öğelerden büyük olmasıdır: o zaman n öğenin hepsi bir sağa kayar ve ekleme O(n) olur. Ortalamada da yaklaşık n/2 öğe kayar; bu da O(n)'dir. Buna karşılık removeMin() tek satırlıktır ve O(1)'dir: en küçük zaten sondadır.

11.2.4Dizi ve bağlı liste temsili

Sıralı gerçeklemeyi dizi yerine bir bağlı listeyle de yazmak mümkündür. İki temsilin maliyetleri benzer, ama farklı yerlerden gelir.

Dizi temsilinde öğeler ardışık hücrelerde durur. Sıralı tutmak için ekleme sırasında öğeler kaydırılır; bu O(n)'dir. En öncelikli öğe dizinin başında tutulursa her çıkarmada bütün dizi sola kaydırılmak zorundadır. Bu yüzden en öncelikli öğe dizinin sonunda tutulur ve çıkarma O(1) olur.

Bağlı liste temsilinde kaydırma yoktur. Yeni düğüm için yer aramak yine O(n)'dir, çünkü bağlı listede bir konuma ancak baştan yürüyerek ulaşılır. Yer bulunduktan sonra düğümü listeye bağlamak iki referans atamasıdır ve O(1) sürer. Bağlı listede en öncelikli öğe baştadır: baştan silmek tek atamalık bir iştir. Sondan silmek ise tek yönlü listede sondan bir önceki düğümü bulmayı gerektirdiği için pahalıdır. Dizide son, bağlı listede baş ucuz uçtur; en öncelikli öğe her temsilde ucuz uca konur. Bağlı listenin bedeli bellektir: her düğüm, verinin yanında bir de sonraki düğümün referansını taşır.

Son iki adımın sırası önemlidir. Önce onceki.sonraki = yeni yazılsaydı 5'ten 7'ye giden tek bağ silinirdi. 7 ve ondan sonraki düğümlere artık hiçbir referans ulaşmaz ve listenin geri kalanı kaybolurdu. Doğru sırada önce yeni düğüm listenin geri kalanına bağlanır, sonra liste yeni düğüme bağlanır.

11.2.5Kod: sıralı dizi ile öncelikli kuyruk

Sıralı dizi gerçeklemesini, öğelerin bir veri ve bir öncelik taşıdığı genel bir sınıfa dönüştürelim. Bu sınıf max-öncelikli çalışır: büyük öncelik değeri önce çıkar. Önce her öğeyi temsil eden küçük bir sınıf tanımlanır:

class Oge<T> {
    T veri;
    int oncelik;
    Oge(T v, int p) { veri = v; oncelik = p; }
}

Oge<T> jenerik bir sınıftır: veri alanı her tipten olabilir, oncelik ise bir tam sayıdır. Kuyruk sınıfı bu öğeleri bir dizide tutar:

// OncelikliKuyruk<E> alanları
private Oge<E>[] dizi =
    (Oge<E>[]) new Oge[10];
private int boyut = 0;

Dizinin başlangıç kapasitesi 10'dur; boyut içerideki öğe sayısını tutar. Java jenerik tipte dizi oluşturmaya izin vermediği için önce ham Oge dizisi oluşturulur, sonra (Oge<E>[]) ile dönüştürülür. Derleyici bu satır için “denetlenmeyen dönüşüm” uyarısı verir; dizi yalnız sınıfın içinde kullanıldığı için bu güvenlidir. Ekleme metodu şöyledir:

public void ekle(E veri, int p) {
    if (boyut == dizi.length)
        dizi = Arrays.copyOf(dizi, 2 * boyut);
    int i = boyut;
    while (i > 0 && dizi[i-1].oncelik < p) {
        dizi[i] = dizi[i - 1];  // sağa kaydır
        i--;
    }
    dizi[i] = new Oge<>(veri, p);
    boyut++;
}

Metot önce kapasiteyi denetler. Dizi doluysa Arrays.copyOf ile iki kat büyüklükte yeni bir dizi oluşturulur ve eski öğeler oraya kopyalanır. Ardından yer arama başlar. i, ilk boş hücre olan boyut'tan başlar ve sola doğru ilerler. Solundaki öğenin önceliği yeni önceliği p'den küçük olduğu sürece o öğe bir sağa kaydırılır. Döngü durduğunda i, yeni öğenin yeridir. Bu düzende en büyük öncelik dizi[0]'da durur. Çıkarma metodu bu öğeyi alır:

public E cikar() {
    if (bosMu()) return null;
    E sonuc = dizi[0].veri;
    for (int i = 1; i < boyut; i++)
        dizi[i - 1] = dizi[i];
    dizi[--boyut] = null;
    return sonuc;
}

cikar, boş kuyrukta null döndürür. Aksi hâlde dizi[0]'daki verinin bir kopyasını alır ve kalan öğeleri birer sola kaydırır. Son hücreye null yazılması, çıkan nesnenin referansının dizide kalıp çöp toplayıcıdan kaçmasını önler. dizi[--boyut] ifadesi önce boyut'u azaltır, sonra o indise yazar.

Bu sınıf, “en öncelikli öğeyi dizinin sonunda tut” önerisine uymaz: en büyük öncelik başta durur ve cikar bu yüzden O(n) sürer. ekle da en kötü durumda bütün öğeleri kaydırdığı için O(n)'dir. Kod okunması kolay olsun diye bu düzeni seçmiştir. Öncelik dizinin sonunda tutulsaydı cikar tek satıra inerdi.

Koşuldaki < işaretinin bir anlamı daha vardır. Kaydırma yalnız solundaki öğe kesin olarak daha düşük öncelikliyse yapılır. Eşit öncelikli bir öğe kaydırılmaz ve yeni öğe onun sağına yerleşir. Böylece eşit öncelikli öğeler geliş sırasıyla durur ve geliş sırasıyla çıkar: kuyruk eşitlikte FIFO'dur.

11.2.6Kod izleme: eşit öncelikte ekleme

Boş kuyruğa ekle(A, 2), ekle(B, 5), ekle(C, 1) uygulandıktan sonra dizi [B:5, A:2, C:1] olur (her hücre “veri:öncelik” biçiminde yazıldı). Şimdi ekle(D, 5) çağrılıyor. D'nin önceliği B'ninkine eşittir; asıl soru D'nin B'nin önüne mi, arkasına mı gireceğidir.

public void ekle(E veri, int p) {
  if (boyut == dizi.length)
    dizi = Arrays.copyOf(dizi, 2 * boyut);
  int i = boyut;
  while (i > 0 && dizi[i-1].oncelik < p) {
    dizi[i] = dizi[i - 1];  // sağa kaydır
    i--;
  }
  dizi[i] = new Oge<>(veri, p);
  boyut++;
}

Kritik adım i = 1'deki karşılaştırmadır: 5 < 5 yanlıştır ve B kaydırılmaz. D, B'nin hemen arkasına yerleşir. Kuyruktan iki kez cikar() yapılırsa önce B, sonra D çıkar. Kuyruk, eşit öncelikli B ile D arasında geliş sırasını korumuştur.

Koşul <= olarak yazılsaydı tablonun son karşılaştırması 5 <= 5, yani doğru olurdu. B de bir sağa kayar ve D başa geçerdi: [D:5, B:5, A:2, C:1]. Dizi yine büyükten küçüğe sıralı kalır, ama eşit öncelikte yeni gelen öne geçer. Tek bir karakter, kuyruğun eşitlikteki davranışını FIFO'dan LIFO'ya çevirir.

11.2.7Maliyet karşılaştırması

İki liste gerçeklemesini ikili heap ile aynı tabloda karşılaştıralım.

* Öğeler önce sıralanarak.   ** Aşağıdan yukarıya heap oluşturma ile.

Tablonun son satırı, kuyruk boşken n öğenin hep birlikte verildiği durumu gösterir. Sırasız listede öğeleri olduğu gibi kopyalamak yeter. Sıralı listede öğeler önce sıralanır; bu, iyi bir sıralama algoritmasıyla O(n log n)'dir. Heap'te ise öğeleri tek tek eklemek yerine diziyi yerinde düzenleyen özel bir algoritma O(n) sürede heap kurar.

Tek tek işlemlerden çok, bir işlem dizisinin toplam maliyeti önemlidir. Boş bir kuyruğa n öğe eklenip ardından n kez removeMin yapıldığını düşünelim.

• Sırasız liste: n · O(1) + n · O(n) = O(n²). Eklemeler ucuzdur, ama her çıkarma kalan bütün öğeleri tarar.
• Sıralı liste: n · O(n) + n · O(1) = O(n²). Bu kez pahalı olan eklemelerdir.
• İkili heap: 2n · O(log n) = O(n log n).

Farkın büyüklüğünü bir sayıyla görelim. n = 10⁶ için n² = 10¹², n log₂ n ≈ 10⁶ · 19,93 ≈ 2 · 10⁷'dir. Oran n / log₂ n ≈ 50.000'dir. Heap'li bir programın bir saniyede bitirdiği iş, liste kullanan programda yaklaşık 50.000 saniye, yani on dört saatten fazla sürer. Asimptotik karmaşıklık bu tür farkları önceden görmeye yarar.

11.3İkili heap

Liste gerçeklemeleri iki uç noktadır. Sırasız liste hiç düzen tutmaz ve ekleme bedava olur; sıralı liste tam düzen tutar ve çıkarma bedava olur. İkili heap ikisinin arasında durur: kısmi bir düzen tutar. Bu düzen en öncelikli öğenin hep aynı yerde olmasını garanti edecek kadar güçlü, ama her işlemde yalnız birkaç öğenin yer değiştirmesine izin verecek kadar gevşektir.

11.3.1İki özellik

İkili heap (binary heap), öncelikli kuyruğu gerçeklemek için en yaygın kullanılan veri yapısıdır. Öğeler bir ikili ağacın düğümlerinde tutulur ve ağaç aynı anda iki koşulu sağlar.

Şekil 11.7 bir max-heap gösteriyor. Kök 9'dur; çocukları 7 ve 8'dir. 7'nin çocukları 3 ve 5, 8'in tek çocuğu 6'dır. Her ebeveyn çocuklarından büyüktür: 9 ≥ 7, 8; 7 ≥ 3, 5; 8 ≥ 6. Son seviye soldan sağa dolmuştur ve tek boşluk en sağdadır.

Heap-sıra özelliği yalnız ebeveyn ile çocuk arasında bir şey söyler. Ama bu yerel kural zincirleme olarak uygulanınca güçlü bir sonuç verir: bir düğümün anahtarı çocuğundan, çocuğun anahtarı torunundan büyüktür ve bu böyle sürer. Yani her düğüm, kendi alt ağacındaki bütün düğümlerden büyük ya da onlara eşittir. Kök bütün ağacın alt ağacı olduğundan en büyük anahtar köktedir. En öncelikli öğeye bakmak bu yüzden O(1)'dir.

Aynı kural, kardeşler arasında hiçbir şey söylemez. Şekil 11.7'de 7 ile 8 yer değiştirse ağaç yine heap olur: 9 iki çocuğundan da büyüktür ve 8 ile 7 kendi çocuklarından büyük kalır. Heap'in sıralı bir yapı olmamasının nedeni budur. Kökten başka hiçbir düğümün konumu, onun bütün öğeler içindeki sırası hakkında kesin bilgi vermez.

İkinci özellik ağacın biçimini sınırlar. Tam ikili ağaç olabilecek en “sıkışık” ikili ağaçtır: belli sayıda düğümle olabilecek en kısa ağaç budur. Bu özelliğin iki önemli sonucu vardır. Birincisi, ağacın yüksekliği ⌊log₂ n⌋'dir. İkincisi, ağaç bir dizide boşluksuz tutulabilir; işaretçi gerekmez.

Bu iki özellik birlikte heap işlemlerinin hızını açıklar. Ekleme ve çıkarma, kökten bir yaprağa uzanan tek bir yol üzerinde çalışır. Yolun uzunluğu en çok ağacın yüksekliği kadardır ve yükseklik logaritmik olduğu için iki işlem de O(log n)'dir.

11.3.2Min-heap ve max-heap

İki heap türü, heap-sıra özelliğindeki eşitsizliğin yönüyle ayrılır. Min-heap'te her ebeveynin anahtarı çocuklarınınkinden küçük ya da eşittir: anahtar(ebeveyn) ≤ anahtar(çocuk). En küçük anahtar köktedir ve min-heap min-öncelikli kuyruğu gerçekler. Max-heap'te eşitsizlik terstir: anahtar(ebeveyn) ≥ anahtar(çocuk). Kökte en büyük anahtar durur.

Şekil 11.8'deki min-heap'te 7 ile 3 kardeştir ve 7 > 3'tür. Bu bir sorun değildir: sıra yalnız ebeveyn ile çocuk arasında geçerlidir. Aynı ağaçta 7, 3'ün çocukları olan 5 ve 6'dan da büyüktür. Farklı dallardaki düğümler arasında herhangi bir ilişki beklenmez.

Heap-sıra özelliğinin geometrik bir okunuşu da vardır: kökten herhangi bir yaprağa giden her yol sıralıdır. Min-heap'te yol boyunca anahtarlar artar; max-heap'te azalır. Şekildeki max-heap'te 9 → 3 → 2, 9 → 3 → 1, 9 → 6 → 5 ve 9 → 6 → 4 yollarının dördü de azalan sıradadır. Heap'i, kökte birleşen sıralı yollardan oluşan bir demet gibi düşünmek mümkündür. Ekleme ve çıkarma da bu yollardan yalnız birini düzeltir.

11.3.3Tam ikili ağaç ve yükseklik

Tam ikili ağaç tanımı ilk okumada “dolu ağaç” ile karıştırılabilir. Fark, son seviyededir. Tam ağaçta son seviyenin dolu olması gerekmez; yalnız düğümlerin soldan başlayarak boşluksuz dizilmesi gerekir. Şekil 11.9 üç ağacı karşılaştırıyor.

Soldaki ağaçta 1 kök, 2 ve 3 onun çocukları, 4 ve 5 ise 2'nin çocuklarıdır. Son seviye 2'nin altında soldan dolmuş ve 3'ün altı boş kalmıştır; ağaç tamdır. Ortadaki ağaçta 2'nin sağ çocuğu yokken 3'ün sol çocuğu vardır. Son seviyede bir boşluk oluşmuştur. Sağdaki ağaçta son seviyedeki iki düğüm 3'ün altındadır; 2'nin altındaki konumlar boştur. Bu ağaçların ikisi de heap olamaz.

Teoremi iki örnekle sınayalım. n = 7 için log₂ 7 ≈ 2,81 ve h = 2'dir: kök, iki çocuk ve dört torun tam üç seviye doldurur. n = 1000 için 2⁹ = 512 ≤ 1000 < 1024 = 2¹⁰ olduğundan h = 9'dur. Bin öğeli bir heap'te kökten en derin yaprağa giden yol yalnız 9 kenar uzunluğundadır; bir milyon öğede bu sayı 19'a çıkar. Logaritmik büyümenin pratik anlamı budur: öğe sayısı bin kat artarken yol yalnız 10 adım uzar.

Tam ağaç özelliğinin heap için ikinci önemli sonucu, yeni düğümün yerinin hiçbir zaman tartışmalı olmamasıdır. Yeni öğe her zaman “son seviyedeki en soldaki boş yere” gelir. Son seviye doluysa yeni bir seviye açılır ve öğe onun en soluna yerleşir. Dizi gösteriminde bu konum tam olarak n indisidir. Silmede de durum benzerdir: tam ağaçtan bir düğüm çıkarmanın biçimi bozmayan tek yolu, son seviyenin en sağındaki düğümü, yani dizinin son öğesini kaldırmaktır.

11.3.4Heap mi, değil mi?

Bir ağacın heap olup olmadığını anlamak için iki özellik ayrı ayrı denetlenir. Önce biçime bakılır: ağaç tam mı? Sonra her ebeveyn–çocuk çiftine bakılır: eşitsizlik hep aynı yönde mi?

(d) ağacı önemli bir dersi gösterir: heap-sıra özelliği tek başına yetmez. Biçim bozukken dizi gösteriminde boşluk oluşur. (d) ağacı dizide [10, 8, 9, _, _, 7, 6] biçiminde, iki boş hücreyle yazılmak zorundadır. Heap'in indis formülleri ve “yeni öğe n indisine gelir” kuralı boşluksuz dizi varsayımına dayanır.

11.3.5Kod izleme: heapMi()

Bir dizinin max-heap olup olmadığını denetleyen kod kısadır. Dizi gösteriminde ağaç kendiliğinden tamdır, çünkü dizide boşluk yoktur. Bu yüzden yalnız heap-sıra özelliği denetlenir. Dizideki i indisli düğümün ebeveyni (i − 1) / 2 indisindedir (Tanım 11.5).

static boolean heapMi(int[] a) {  // max-heap mi?
  for (int i = 1; i < a.length; i++) {
    int e = (i - 1) / 2;           // ebeveyn
    if (a[e] < a[i]) return false; // sıra bozuk
  }
  return true;
}

Döngü kök dışındaki her düğümü, yani i = 1'den n − 1'e kadar her indisi bir kez ziyaret eder. Her düğüm yalnız kendi ebeveyniyle karşılaştırılır. Bir ebeveyn çocuğundan küçükse sıra bozuktur ve metot hemen false döndürür. Döngü sona kadar giderse bütün ebeveyn–çocuk çiftleri denetlenmiştir ve dizi bir max-heap'tir.

Her ebeveyn–çocuk çifti tam bir kez denetlenir, çünkü her düğümün tek bir ebeveyni vardır. Ayrıca çocuklar üzerinden gitmek, ebeveynler üzerinden gidip iki çocuğu denetlemekten daha basit bir döngü verir: sağ çocuğun var olup olmadığını sorgulamak gerekmez.

Kodu a = [10, 8, 9, 3, 5, 7, 4, 6] dizisi üzerinde izleyelim.

İlk yedi öğe, yani [10, 8, 9, 3, 5, 7, 4] geçerli bir max-heap'tir; Java ile çalıştırıldığında bu yedi öğelik dizi için metot true döndürür. Sona eklenen 6 ise ebeveyni 3'ten büyüktür ve heap-sıra özelliğini bozar. Bu durum, ekleme işleminin neden ek bir düzeltme adımına ihtiyaç duyduğunu da gösteriyor: yeni öğeyi sona yazmak biçimi korur, sırayı korumayabilir.

En kötü durumda, yani dizi gerçekten bir heap olduğunda, döngü n − 1 karşılaştırma yapar. heapMi'nin zaman maliyeti O(n), ek bellek maliyeti O(1)'dir. Daha hızlı bir denetim mümkün değildir: herhangi bir ebeveyn–çocuk çifti atlanırsa o çiftteki bozukluk gözden kaçabilir.

Boş ve tek öğeli dizilerde döngü hiç dönmez ve metot true döndürür. Bu doğru bir sonuçtur: hiç ebeveyn–çocuk çifti olmayan bir ağaç, heap-sıra özelliğini kendiliğinden sağlar. Metodun min-heap sürümü için koşulu ters çevirmek yeter: if (a[e] > a[i]) return false;.

11.3.6Dizi gösterimi

Ağaçlar çoğunlukla düğüm nesneleri ve aralarındaki referanslarla temsil edilir. Heap'te buna gerek yoktur. Düğümler kökten başlayarak seviye seviye, her seviyede soldan sağa (level order, seviye sırası) bir diziye yazılır. Kök heap[0]'a, onun çocukları heap[1] ve heap[2]'ye, torunlar heap[3]'ten heap[6]'ya gider ve bu böyle sürer.

Şekil 11.12 yedi düğümlü bir max-heap'i ve onun dizisini gösteriyor. Ağaç tam olduğu için seviye sırasıyla yazılan dizide boşluk kalmaz: n öğe tam olarak heap[0]'dan heap[n − 1]'e kadar olan hücrelere sığar. Ebeveyn ve çocuk bağlantıları için referans saklamak gerekmez; bunlar indislerden hesaplanır.

Dizi gösteriminin üç pratik üstünlüğü vardır. Birincisi bellektir: düğüm başına iki çocuk referansı yerine yalnız öğenin kendisi saklanır. İkincisi hızdır: ardışık bellek hücreleri işlemcinin önbelleğine bloklar hâlinde gelir ve dizide gezinmek, bellekte dağınık düğümleri izlemekten çok daha hızlıdır. Üçüncüsü sadeliktir: “son öğe” ve “ilk boş konum” tek bir sayaçla, n ile bilinir.

Bu notta indisler 0'dan başlar ve kök heap[0]'dadır. Bazı kitaplar indisleri 1'den başlatır; iki seçenek eşdeğerdir ve formülleri biraz değişir.

11.3.7Ebeveyn ve çocuk indisleri

Seviye sırası düzeninde bir düğümün çocuklarının ve ebeveyninin indisi basit formüllerle bulunur.

Formüllerin neden doğru olduğunu görmek için seviyelerin dizide nereden başladığına bakalım. d. seviye 2^d − 1 indisinden başlar: 0. seviye 0'dan, 1. seviye 1'den, 2. seviye 3'ten, 3. seviye 7'den. Bir seviyenin j'inci düğümünün (0'dan sayarak) çocukları, bir alt seviyenin 2j'inci ve 2j + 1'inci düğümleridir, çünkü her düğüm soldan sağa sırayla iki çocuk alır. İndis olarak yazılırsa düğüm i = 2^d − 1 + j, sol çocuğu 2^d+1 − 1 + 2j = 2(2^d − 1 + j) + 1 = 2i + 1'dir. Sağ çocuk bir sonraki hücredir. Ebeveyn formülü bu ilişkinin tersidir: 2i + 1 ve 2i + 2'den 1 çıkarıp 2'ye bölünce aşağı yuvarlanmış değer iki durumda da i olur.

Java'da tam sayı bölmesi pozitif sayılarda zaten aşağı yuvarlar. Bu yüzden ebeveyn formülü kodda doğrudan (i - 1) / 2 olarak yazılır. Çocuk formülleri de yalnız toplama ve çarpma içerir. Bu işlemler sabit sürede yapılır; heap'te bir düğümden komşusuna geçmek, bağlı yapıda bir referansı izlemek kadar ucuzdur.

1 tabanlı gösterim. Bazı kitaplar heap[0]'ı boş bırakır ve kökü heap[1]'e koyar. O zaman k indisli düğümün çocukları 2k ve 2k + 1, ebeveyni ⌊k/2⌋'dir. Formüller biraz daha kısadır, ama bir hücre boşa gider. İki gösterim eşdeğerdir; önemli olan birini seçip baştan sona tutarlı kullanmaktır.

11.4Ekleme ve silme

Heap'in iki temel işlemi aynı kalıbı izler. Önce ağacın biçimi korunur: öğe, tam ağaç özelliğini bozmayacak tek yere konur ya da oradan alınır. Bu adım heap-sıra özelliğini bir noktada bozabilir. İkinci adım bu yerel bozukluğu, öğeyi tek bir yol boyunca yukarı ya da aşağı taşıyarak onarır. Yukarı taşımaya up-heap (yukarı süzme), aşağı taşımaya down-heap (aşağı süzme) denir. Bu kesimdeki kodlar max-heap içindir.

11.4.1Ekleme: up-heap

Max-heap'e yeni bir öğe eklemek üç adımdır:

1. Biçimi koru. Yeni öğe ağacın ilk boş konumuna, yani heap[n]'e yazılır ve n bir artar. Ağaç tam kalır.
2. Bozukluğu bul. Heap-sıra özelliği yalnız yeni öğe ile ebeveyni arasında bozulmuş olabilir. Yeni öğe ebeveyninden büyükse ikisi yer değiştirir.
3. Tekrarla. Öğe bir seviye yukarı çıkınca aynı soru yeni ebeveyn için sorulur. Öğe köke ulaşınca ya da ebeveyni kendisinden büyük veya ona eşit olunca durulur.

Şekil 11.14 bir örnek gösteriyor. 10, 8'in sağ çocuğu olarak indis 6'ya yazılır. Ebeveyni 8, 10'dan küçüktür: takas yapılır ve 10 indis 2'ye çıkar. Yeni ebeveyn kök 9'dur; 9 < 10 olduğu için bir takas daha yapılır. 10 artık köktedir ve işlem biter. Sonuç [10, 7, 9, 3, 5, 6, 8]'dir.

Bu işlemin adları kaynaktan kaynağa değişir: up-heap, bubble-up, sift-up, swim. Hepsi aynı şeyi anlatır. Bu notun kodunda metodun adı yuzdur'dur: hafif bir cismin suyun yüzeyine çıkması gibi büyük anahtar köke doğru yükselir.

İspatın özü tek cümleyle şöyle söylenebilir: yer değiştirmede aşağı inen ebeveyn, zaten diğer çocuğundan büyüktü. Bu yüzden takas, yukarıdaki bozukluğu düzeltirken aşağıda yeni bir bozukluk yaratmaz.

11.4.2Kod: ekle() ve yuzdur()

Max-heap sınıfı bir int dizisi ve bir öğe sayacı tutar. Ekleme metodu ve up-heap şöyledir:

public class MaxHeap {
  private int[] heap = new int[4];
  private int n = 0;                // öğe sayısı

public void ekle(int x) {
  if (n == heap.length) buyut(2 * heap.length);
  heap[n] = x;  n++;              // ilk boş konum
  yuzdur(n - 1);
}
private void yuzdur(int i) {      // up-heap
  while (i > 0) {
    int ebeveyn = (i - 1) / 2;
    if (heap[ebeveyn] >= heap[i]) return;
    yerDegistir(i, ebeveyn);  i = ebeveyn;
  }
}
private void yerDegistir(int a, int b) {
  int t = heap[a];  heap[a] = heap[b];  heap[b] = t;
}
}  // MaxHeap

Sınıfın başlangıç kapasitesi 4'tür. ekle önce dizinin dolu olup olmadığına bakar: n == heap.length ise buyut kapasiteyi iki katına çıkarır. Ardından x ilk boş konum olan heap[n]'e yazılır, n artırılır ve yeni öğenin indisi n − 1 ile yuzdur çağrılır.

yuzdur(i), i kökten farklı olduğu sürece döner. Her turda ebeveynin indisi (i − 1) / 2 ile hesaplanır. Ebeveyn öğeden büyük ya da ona eşitse sıra sağlanmıştır ve metot return ile hemen biter. Aksi hâlde yerDegistir iki hücreyi takas eder ve i ebeveynin indisine çıkar. yerDegistir(a, b) üç atamalık bir yardımcı metottur: geçici bir değişken üzerinden heap[a] ile heap[b]'yi değiştirir.

Döngünün iki çıkışı vardır. Birincisi while koşuludur: i = 0 olduğunda öğe köktedir ve ebeveyni yoktur. İkincisi döngü içindeki return'dür: ebeveyn ≥ öğe olduğunda daha yukarıya bakmaya gerek yoktur, çünkü yukarıdaki yol zaten sıralıdır. Koşulun >= olması, eşit anahtarlarda gereksiz takası önler.

Maliyet: yuzdur her turda sabit iş yapar ve en çok ⌊log₂ n⌋ tur döner; O(log n)'dir. ekle'nin kendisi, buyut çağrısı dışında sabit iştir. buyut ise nadiren çalışır ve maliyeti eklemelere dağıtılınca amortize O(1)'dir. Ekleme bu yüzden amortize O(log n)'dir.

11.4.3Kod izleme: ekle(10), ekle(8)

Başlangıçta heap [9, 3, 6, 2, 1, 5, 4]'tür: n = 7, kapasite 16. Her ebeveyn çocuklarından büyük ya da eşittir ve en büyük öğe 9 köktedir. Ardı ardına ekle(10) ve ekle(8) çağrılıyor.

ekle(10) en kötü durumu gösterir: yeni öğe bütün öğelerden büyüktür ve yapraktan köke kadar çıkar. Sekiz öğeli heap'in yüksekliği ⌊log₂ 8⌋ = 3'tür ve tam 3 takas yapılmıştır. ekle(8) ise yolun yarısında durur: 8, 3 ile yer değiştirdikten sonra ebeveyni 9 ile karşılaşır ve 9 ≥ 8 olduğu için metot döner. İki eklemede toplam 4 takas yapılmıştır.

Tabloda dikkat çekici bir ayrıntı vardır: ekle(8)'de ilk karşılaştırılan ebeveyn 3'tür. Bu 3, ekle(10) sırasında indis 1'den indis 3'e inmiş olan öğedir. Her up-heap, kendi yolundaki öğeleri bir seviye aşağı iter; sonraki eklemeler bu yeni düzen üzerinde çalışır.

11.4.4Boş heap'e art arda ekleme

Heap'in boştan nasıl kurulduğunu görmek için kapasitesi 4 olan boş bir max-heap'e sırasıyla 4, 5, 2, 6, 1, 3 ekleyelim. Tablo 11.10 her eklemeden sonraki durumu veriyor.

İlk ekleme hiçbir karşılaştırma yapmaz: tek öğe zaten köktür. ekle(6), o ana kadarki en büyük öğe olduğu için yapraktan köke çıkar. ekle(1) anında dizi doludur (n = 4 = heap.length). Önce kapasite 8'e büyütülür, sonra 1 yazılır. 1, ebeveyni 5'ten küçük olduğu için hiç hareket etmez. Son eklemede 3, ebeveyni 2 ile yer değiştirir ve 6'nın altında durur.

Son dizi [6, 5, 3, 4, 1, 2] sıralı değildir, ama geçerli bir max-heap'tir: 6 ≥ 5, 3; 5 ≥ 4, 1; 3 ≥ 2. Aynı öğeler farklı sırayla eklenseydi farklı bir heap ortaya çıkabilirdi. Bir öğe kümesinin tek bir heap'i yoktur; heap'in biçimi kesin, öğelerin yerleşimi ise ekleme sırasına bağlıdır.

11.4.5Kapasite büyütme

Java dizilerinin boyu oluşturulduktan sonra değişmez. Kapasiteyi büyütmek, daha büyük yeni bir dizi oluşturup eski öğeleri ona kopyalamak demektir:

private void buyut(int kapasite) {
  int[] yeni = new int[kapasite];
  for (int k = 0; k < n; k++)
    yeni[k] = heap[k];          // kopyala
  heap = yeni;                  // eski dizi çöpe
}

buyut(kapasite) önce istenen boyda yeni bir dizi ayırır. Java yeni bir int dizisinin bütün hücrelerini 0 ile doldurur. Döngü, eski dizinin ilk n öğesini aynı indislerle yeni diziye kopyalar. Son satır heap alanını yeni diziye yönlendirir. Eski diziye artık hiçbir referans kalmaz ve çöp toplayıcı onu daha sonra serbest bırakır.

Tek bir büyütmenin maliyeti O(n)'dir, çünkü n öğe kopyalanır. Ancak büyütme seyrek yapılır. Kapasite her seferinde iki katına çıktığı için büyütmeler 4, 8, 16, … öğe dolduğunda olur. Boş heap'e n ekleme yapıldığında kopyalanan toplam öğe sayısı 4 + 8 + 16 + … biçiminde bir toplamdır ve son terimi n'den küçüktür. Her terimi öncekinin iki katı olan böyle bir toplam, son teriminin iki katından küçüktür. Toplam kopya bu yüzden 2n'den azdır ve ekleme başına düşen kopya maliyeti sabittir: büyütme amortize O(1)'dir.

Kapasiteyi iki katına çıkarmak yerine sabit bir miktar (örneğin 4 hücre) artırmak kötü bir seçim olurdu. O zaman her 4 eklemede bir büyütme yapılır ve toplam kopya 4 + 8 + 12 + … ≈ n²/8 olur: ekleme başına O(n).

Silme işleminde de simetrik bir küçültme yapılabilir: öğe sayısı kapasitenin dörtte birine inince dizi yarıya indirilir. Eşik dörtte bir seçilir, yarı seçilmez. Yarı seçilseydi tam eşikte art arda yapılan bir ekleme ve bir silme her seferinde büyütme ve küçültmeye yol açardı. Küçültme isteğe bağlıdır ve bu notun kodunda yer almaz.

11.4.6En büyüğü çıkarma: down-heap

Max-heap'te en büyük öğe köktedir. Onu çıkarmak, ekleme gibi iki aşamada yapılır.

1. Kökü sakla. Kökteki öğe döndürülecek değerdir; bir değişkene alınır.
2. Biçimi koru. Tam ağaçtan biçimi bozmadan çıkarılabilecek tek düğüm sonuncusudur. Ağacın son öğesi heap[n − 1] köke taşınır ve n bir azalır.
3. Bozukluğu onar. Yeni kök büyük olasılıkla küçük bir öğedir ve çocuklarından küçük olabilir. Kök, çocuklarından büyük olanla yer değiştirir.
4. Tekrarla. Öğe yaprağa ulaşana ya da iki çocuğundan da büyük veya onlara eşit olana kadar aşağı iner.

Şekil 11.18 süreci gösteriyor. 9 çıkarılır ve son öğe 4 köke gelir. Kökün çocukları 7 ve 8'dir; büyük olan 8 ile takas yapılır. 4 şimdi indis 2'dedir ve tek çocuğu 6'dır; 4 < 6 olduğu için bir takas daha yapılır. 4 bir yaprağa ulaşmıştır. Sonuç [8, 7, 6, 3, 5, 4]'tür.

Neden büyük çocuk? Kök hangi çocukla yer değiştirirse o çocuk yeni kök olur ve diğer çocuğun ebeveyni olur. Yukarı çıkan çocuk büyük olan ise diğerinden büyük ya da ona eşittir ve heap-sıra özelliği yeni kökte sağlanır. Küçük çocuk yukarı çıksaydı, kendisinden büyük bir çocuğun ebeveyni olurdu; bozukluk düzelmez, yalnız yer değiştirirdi. Min-heap'te aynı akıl yürütme küçük çocuğu seçtirir.

Maliyet: her seviyede iki karşılaştırma yapılır. Biri iki çocuk arasında büyüğü seçmek, diğeri öğeyi o çocukla karşılaştırmak içindir. Öğe en çok h = ⌊log₂ n⌋ seviye iner. Toplam iş O(log n)'dir.

11.4.7Kod: silMax() ve batir()

public int silMax() {           // n > 0 olmalı
  int max = heap[0];
  yerDegistir(0, n - 1);  n--;  // son öğe köke
  batir(0);
  return max;
}
private void batir(int i) {       // down-heap
  while (2 * i + 1 < n) {       // sol çocuk var mı?
    int j = 2 * i + 1;            // j: büyük çocuk
    if (j + 1 < n && heap[j + 1] > heap[j]) j++;
    if (heap[i] >= heap[j]) return;
    yerDegistir(i, j);  i = j;    // bir seviye in
  }
}

silMax kökü max'ta saklar. Sonra kökü son öğeyle takas eder ve n'yi azaltır. Takas, son öğeyi köke getirirken eski kökü de dizinin sonuna, artık heap'e ait olmayan bir hücreye taşır. Heap sort bu ayrıntıdan yararlanır: art arda yapılan çıkarmalar en büyük öğeleri dizinin sonunda biriktirir. Ardından batir(0) çağrılır ve max döndürülür. Boş heap'te heap[0] anlamsız olduğu için gerçek bir sınıfta metodun başına if (n == 0) denetimi ve bir istisna eklenir.

batir(i) down-heap'tir; adı bir cismin suya batması benzetmesinden gelir. Döngü koşulu 2 * i + 1 < n, i'nin sol çocuğu var mı sorusudur. Tam ağaçta sol çocuğu olmayan düğümün sağ çocuğu da olamaz; bu yüzden sol çocuk yoksa i bir yapraktır ve döngü biter. Döngü içinde j önce sol çocuğa ayarlanır. Sağ çocuk varsa ve daha büyükse j bir artırılır. Böylece j büyük çocuğu gösterir. Öğe bu çocuktan büyük ya da ona eşitse sıra sağlanmıştır ve metot döner; değilse takas yapılır ve öğe bir seviye iner.

Sağ çocuk denetimindeki j + 1 < n koşulu kritik önemdedir. silMax'tan sonra eski kök dizinin n indisinde durmaya devam eder. Koşul unutulursa heap[j + 1] bu silinmiş öğeyi okuyabilir ve onu “büyük çocuk” sanıp heap'e geri taşıyabilir. Bu hatanın etkisi Örnek 11.5'te görülür.

11.4.8Kod izleme: silMax()

Heap [9, 3, 6, 2, 1, 5, 4] (n = 7) üzerinde silMax() çağrılıyor.

İlk turda kökün iki çocuğu vardır ve büyüğü 6'dır. İkinci turda indis 2'deki 4'ün yalnız sol çocuğu vardır: j = 5, sağ çocuk adayı j + 1 = 6 ise n = 6'dan küçük değildir. Bu noktada heap[6] hâlâ 9'dur. j + 1 < n denetimi sayesinde bu silinmiş değer hiç okunmaz. Toplam 3 karşılaştırma ve 2 takas yapılmıştır; yükseklik ⌊log₂ 6⌋ = 2 olduğundan bu, olabilecek en çok takas sayısıdır.

11.4.9Kod izleme: art arda iki silMax()

Up-heap izlemesinin sonunda elde edilen [10, 9, 6, 8, 1, 5, 4, 2, 3] heap'inden art arda iki kez en büyük öğeyi çıkaralım.

İki çıkarma 10 ve 9'u döndürür. İlk çıkarmada inen öğe 3, yaprağa varmadan durur: indis 3'te tek çocuğu 2'dir ve 3 ≥ 2'dir. İkinci çıkarmada inen öğe 2 bir yaprağa kadar iner. Dizinin tamamına bakıldığında son iki hücrede 9 ve 10 durur: [8, 3, 6, 2, 1, 5, 4 | 9, 10]. Çıkarılan öğeler dizinin sonunda büyükten küçüğe doğru, sağdan sola birikmiştir.

11.4.10Min-heap'te insert ve removeMin

Min-heap'te iki işlem aynı biçimde çalışır; yalnız karşılaştırmaların yönü terstir. Yukarı süzmede öğe ebeveyninden küçükse yukarı çıkar. Aşağı süzmede öğe çocuklarının küçüğüyle yer değiştirir. Başlangıç min-heap'i [2, 5, 3, 9, 6, 8, 4] olsun: en küçük öğe 2 köktedir.

Bu örnekte ekleme ve çıkarmanın birbirini tam olarak geri aldığı görülüyor: son dizi başlangıç diziyle aynıdır. Bu bir rastlantıdır. Eklenen öğe en küçük olduğu için yol boyunca her öğeyi bir seviye aşağı itmiştir; çıkarma sırasında köke gelen 9 da aynı yoldan inmiştir. Genel olarak bir ekleme ve onu izleyen bir çıkarma heap'i başlangıç durumuna döndürmez.

Max-heap kodundan min-heap kodu elde etmek için iki karşılaştırmayı çevirmek yeter: yuzdur'da heap[ebeveyn] >= heap[i] yerine heap[ebeveyn] <= heap[i], batir'da büyük çocuk yerine küçük çocuk seçimi ve heap[i] <= heap[j] durma koşulu. Bir başka yol, anahtarları eksiyle çarpıp max-heap'e koymaktır: en büyük −x, en küçük x'e karşılık gelir.

11.4.11Heap işlemlerinin maliyeti

* Dizi büyütme ve küçültme dahil amortize maliyet.

Logaritmik maliyetin pratik karşılığını yükseklik formülü verir. n = 10⁶ öğeli bir heap'in yüksekliği ⌊log₂ 10⁶⌋ = 19'dur; ekleme ya da çıkarma en çok 19 takas yapar. Sıralı bir dizide aynı ekleme yarım milyon öğeyi kaydırabilirdi.

Heap'in bellek maliyeti de düşüktür: n öğe için O(n) hücre. İki katına büyütme nedeniyle dizinin en çok yarısı boş kalabilir. Bağlı ağaç gerçeklemesinde ise her düğüm iki çocuk referansı ve çoğu zaman bir ebeveyn referansı taşırdı.

Tablonun son satırı, heap'in neyi yapmadığını hatırlatır. Heap yalnız en öncelikli öğeyi hızlı bulur. “7 kuyrukta mı?” sorusuna cevap vermek için bütün diziyi taramak gerekir. Belirli bir öğenin önceliğini değiştirmek ya da onu silmek de önce bu öğenin bulunmasını gerektirir. Bu sorunun çözümü uyarlanabilir öncelikli kuyruktur.

11.4.12Uyarlanabilir öncelikli kuyruk

Bazı uygulamalarda kuyruktaki bir öğenin önceliği bekleme sırasında değişir. Dijkstra algoritmasında bir düğüme daha kısa bir yol bulununca o düğümün uzaklığı, yani anahtarı küçülür. Acil serviste bekleyen bir hastanın durumu ağırlaşır. Bazen de bir öğe çıkmadan kuyruktan ayrılır: hasta beklemekten vazgeçer, bir süreç iptal edilir.

Bu işlemlerin asıl zorluğu, e öğesinin heap dizisinde nerede olduğunu bilmektir. Heap sıralı olmadığı için öğeyi aramak O(n)'dir. Goodrich ve arkadaşlarının çözümü konum farkında öğedir (location-aware entry). Her öğe nesnesi, anahtarı ve değerinin yanında heap dizisindeki kendi indisini de saklar. Heap'te her takas yapıldığında takas edilen iki öğenin indis alanı da güncellenir.

Konum bilindiğinde iki işlem de heap'in bildik araçlarıyla yapılır:

• replaceKey(e, k). heap[e.indis]'in anahtarı değiştirilir. Max-heap'te anahtar büyüdüyse öğe yalnız ebeveyniyle çatışabilir ve up-heap uygulanır. Küçüldüyse yalnız çocuklarıyla çatışabilir ve down-heap uygulanır.
• remove(e). Öğe dizinin son öğesiyle takas edilir ve n bir azaltılır. Yerine gelen öğe, ebeveyninden büyük de olabilir, çocuklarından küçük de. Bu yüzden ona duruma göre up-heap ya da down-heap uygulanır.

Konum alanı olmadan bu işlemlerin her biri önce O(n)'lik bir arama gerektirirdi. Konumla öğeye O(1)'de ulaşılır ve işlemler O(log n)'e iner. Bedeli, her takasta iki indis alanının da güncellenmesidir; bu da sabit bir ek iştir.

11.4.13Kod izleme: anahtar büyütme ve küçültme

Bu notun basit max-heap sınıfı öğe nesneleri yerine tam sayılar tutar. Bu yüzden öğe indisle verilir: anahtarDegistir(i, yeni), heap[i]'yi yeni yapar ve sırayı onarır.

public void anahtarDegistir(int i, int yeni) {
  int eski = heap[i];
  heap[i] = yeni;
  if (yeni > eski) yuzdur(i);  // büyüdü: yukarı
  else batir(i);               // küçüldü: aşağı
}
private void yuzdur(int i) {     // up-heap
  while (i > 0) {
    int ebeveyn = (i - 1) / 2;
    if (heap[ebeveyn] >= heap[i]) return;
    yerDegistir(i, ebeveyn);  i = ebeveyn;
  }
}

Metot eski değeri saklar, yeni değeri yazar ve ikisini karşılaştırarak yönü seçer. Anahtar büyüdüyse yuzdur(i), küçüldüyse batir(i) çağrılır. Eşitse batir çağrılır ama hiçbir şey yapmadan döner, çünkü öğe çocuklarından zaten büyük ya da eşittir. Ağacın biçimi hiç değişmez; yalnız tek bir yol boyunca değerler yer değiştirir.

Anahtar büyütme. Heap [9, 3, 6, 2, 1, 5, 4] üzerinde anahtarDegistir(4, 8) çağrılsın.

8 bir seviye yukarı çıkmış ve kökün altında durmuştur. Yalnız 4 → 1 → 0 yolu incelenmiştir. İspattaki gözlem burada da görülüyor: aşağı inen 3, 8'in eski yerine, yani bir yaprağa iner ve altında çocuk kalmaz. 3, indis 1'deyken öbür çocuğu 2'den zaten büyüktü.

Anahtar küçültme. Aynı heap'in yeni hâli [9, 8, 6, 2, 3, 5, 4] üzerinde bu kez kökün anahtarı küçültülsün: anahtarDegistir(0, 1).

1 iki seviye inmiş, 8 köke çıkmıştır. Kökün anahtarını küçültüp batir(0) çağırmak, silMax'ın aşağı süzme adımıyla aynı işi yapar. silMax'ta köke gelen değer son öğedir, burada ise kullanıcının verdiği yeni değerdir.

İki yönde de maliyet, değişen öğenin izlediği yolun uzunluğuyla sınırlıdır: O(log n). İndis bilinmeseydi önce öğeyi aramak gerekirdi ve maliyet O(n)'e çıkardı.

11.5Heap oluşturma ve heap sort

Şimdiye kadar heap'e öğeler tek tek eklendi. Bazen ise bütün öğeler baştan elimizdedir: bir dosyadan okunan sayılar, bir dizide bekleyen görevler. Bu durumda heap'i öğeleri tek tek ekleyerek kurmak gerekmez; diziyi yerinde düzenleyen daha hızlı bir yöntem vardır. Aynı yöntem, heap'i bir sıralama algoritmasına dönüştürmenin de ilk adımıdır.

11.5.1n öğeden heap oluşturmanın iki yolu

Birinci yol: n kez ekleme. Boş bir heap'e öğeler sırayla eklenir. Her ekleme up-heap yapar ve O(log n) sürer; toplam O(n log n)'dir. Öğeler tek tek ve zaman içinde geliyorsa, yani algoritma bütün girdiyi önceden göremiyorsa (online, çevrim içi durum) tek seçenek budur.

İkinci yol: aşağıdan yukarıya oluşturma (bottom-up heap construction). Bütün öğeler bir dizide hazırsa dizi olduğu gibi tam ikili ağaç sayılır; biçim zaten doğrudur. Yalnız heap-sıra özelliği eksiktir. Bunu sağlamak için son iç düğümden köke doğru her düğüme down-heap uygulanır:

for (int k = n / 2 - 1; k >= 0; k--)   // son iç düğümden köke
    batir(k);                            // alt ağaçları heap olan k'yi batır

Döngünün başladığı ⌊n/2⌋ − 1 indisi, sol çocuğu olan son düğümdür. Bundan sonraki indislerin hepsi yapraktır, çünkü i ≥ ⌊n/2⌋ için 2i + 1 ≥ n olur. Yapraklar tek başlarına zaten heap'tir; onlara dokunmaya gerek yoktur. Dizinin yarısı bu yüzden hiç işlenmez.

Algoritmanın doğruluğu döngünün yönüne dayanır. batir(k) çağrıldığında k'nın iki alt ağacı zaten heap'tir: o alt ağaçların kökleri k'dan büyük indislidir ve onlar daha önce işlenmiştir ya da yapraktır. Down-heap tam bu durumu onarmak için tasarlanmıştır: alt ağaçları heap olan bir kökü doğru yerine indirir. Döngü köke ulaştığında bütün ağaç bir heap olur.

11.5.2Kod izleme: heapOlustur()

Max-heap sınıfına aşağıdan yukarıya oluşturma metodu eklenir. Metot, dizide hazır duran n öğeyi heap'e çevirir:

public void heapOlustur() {     // rastgele dizi
  for (int k = n / 2 - 1; k >= 0; k--)
    batir(k);                   // alt ağaçlar heap
}
private void batir(int i) {       // down-heap
  while (2 * i + 1 < n) {       // sol çocuk var mı?
    int j = 2 * i + 1;            // j: büyük çocuk
    if (j + 1 < n && heap[j + 1] > heap[j]) j++;
    if (heap[i] >= heap[j]) return;
    yerDegistir(i, j);  i = j;    // bir seviye in
  }
}

Girdi, Cormen ve arkadaşlarının kitabındaki klasik örnektir: [4, 1, 3, 2, 16, 9, 10, 14, 8, 7], n = 10. Dizi bir heap değildir; örneğin kök 4, çocuğu 16'dan küçüktür. İndis 5'ten 9'a kadar olan düğümler yapraktır. Döngü k = 10/2 − 1 = 4'ten başlar.

İzlemede yedi takas yapılmıştır. Üst düğümler daha uzun yollar yürümüştür: k = 0'daki 4 üç seviye inmiştir. Buna karşılık bu düğümlerin sayısı azdır. Alt seviyedeki düğümler ise ya hiç işlenmemiş (yapraklar) ya da en çok bir takas yapmıştır. Toplam işin neden doğrusal kaldığı bu dengeden gelir.

11.5.3Aşağıdan yukarıya oluşturma neden O(n)?

İlk bakışta aşağıdan yukarıya oluşturmanın maliyeti O(n log n) gibi görünür: yaklaşık n/2 düğüme down-heap uygulanır ve her biri O(log n) sürebilir. Bu üst sınır doğrudur ama gevşektir. Bir down-heap'in maliyeti, düğümün yüksekliği kadardır, yani düğümden altındaki en derin yaprağa kadar olan uzaklık kadardır. Düğümlerin çoğu ağacın altında ve yükseklikleri küçüktür.

15 düğümlü mükemmel bir ikili ağaçla (bütün seviyeleri dolu, yükseklik 3) hesaplayalım.

Düğümlerin yarısından fazlası yapraktır ve hiç iş yapmaz. Çok iş yapan yüksek düğümlerden ise yalnız birkaç tane vardır. Toplam 11 takas, düğüm sayısı 15'ten bile küçüktür. Java ile 1'den 15'e artan bir dizi (max-heap için en kötü girdi) üzerinde çalıştırıldığında da tam 11 takas sayılır.

Aynı ağacı 15 kez ekleme ile kurmak çok daha pahalıdır. Up-heap'in maliyeti düğümün derinliğine, yani kökten uzaklığına bağlıdır ve düğümlerin çoğu derindir. Artan sırada gelen öğelerde her yeni öğe köke kadar çıkar: derinliği 1 olan 2 düğüm, derinliği 2 olan 4 düğüm ve derinliği 3 olan 8 düğüm vardır. Toplam 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34 takas eder. Java ile sayılan değer de 34'tür.

Serinin toplamının 1 olduğu kolayca görülebilir. S = 1/4 + 2/8 + 3/16 + … olsun. S/2 = 1/8 + 2/16 + …'dir. Farkları alınırsa S − S/2 = 1/4 + 1/8 + 1/16 + … = 1/2 bulunur; buradan S = 1 çıkar.

Teoremin özü şu cümlededir: down-heap'in maliyeti yüksekliğe, up-heap'in maliyeti derinliğe bağlıdır ve düğümlerin çoğu aşağıdadır. Aşağıdaki düğümler için yükseklik küçük, derinlik büyüktür. Aşağıdan yukarıya yöntem işi ucuz yapan yönü seçer.

11.5.4Heap sort

Heap, bir sıralama algoritmasının temelini de oluşturur. Fikir şudur: max-heap'ten art arda en büyük öğe çıkarılırsa öğeler büyükten küçüğe sırayla gelir. silMax çıkarılan kökü dizinin sonuna, heap'in hemen dışındaki hücreye taşıdığı için bu öğeler ayrı bir diziye bile yazılmaz: dizinin sonunda kendiliğinden birikir.

Heap sort iki aşamadan oluşur:

1. Heap oluştur. Dizi aşağıdan yukarıya max-heap'e çevrilir: O(n).
2. n − 1 kez en büyüğü sona al. Kök (o anki en büyük öğe) heap'in son öğesiyle takas edilir. Heap bir küçülür ve kök için down-heap yapılır. Her tur O(log n)'dir; toplam O(n log n).

Şekil 11.25 algoritmanın ortasından bir anı gösteriyor. Dizi ikiye bölünmüştür. Baştaki kısım bir max-heap'tir ve her turda bir küçülür. Sondaki kısım sıralıdır ve her turda bir büyür. Bu kısımdaki öğeler heap'teki bütün öğelerden büyük ya da onlara eşittir; yani kesin yerlerindedir. İki kısım aynı dizide durduğu için ek dizi gerekmez.

Heap sort'un dört özelliği öne çıkar:

• Yerinde çalışır. Heap, sıralanan dizinin kendisinde kurulur; birkaç değişken dışında ek bellek gerekmez: O(1).
• En kötü durumda bile O(n log n)'dir. Hızlı sıralama (quick sort) ortalamada çok hızlıdır ama kötü seçilen pivotlarla O(n²)'ye düşebilir. Heap sort'un böyle bir kötü durumu yoktur.
• Kararlı değildir. Kök ile sondaki öğe arasındaki uzak takaslar eşit anahtarlı öğelerin göreli sırasını değiştirebilir.
• Yön. Max-heap artan sıralama üretir, çünkü en büyük öğe en sona yerleşir. Min-heap ile aynı algoritma azalan sıralama üretir.

11.5.5Kod: heapSort()

public static void heapSort(int[] a) {
  int n = a.length;
  // 1) oluştur: son iç düğümden köke
  for (int k = n / 2 - 1; k >= 0; k--)
    batir(a, k, n);
  // 2) sırala: en büyüğü sona al
  for (int son = n - 1; son > 0; son--) {
    yerDegistir(a, 0, son);
    batir(a, 0, son);           // heap boyutu = son
  }
}
static void batir(int[] a, int i, int n) {
  while (2 * i + 1 < n) {
    int j = 2 * i + 1;
    if (j + 1 < n && a[j + 1] > a[j]) j++;
    if (a[i] >= a[j]) return;
    yerDegistir(a, i, j);  i = j;
  }
}

Kod, sınıftan bağımsız static metotlardan oluşur. batir burada üç parametre alır: dizi, indis ve heap'in o anki boyu. Gövdesi sınıftaki batir ile aynıdır; yalnız heap ve n alanları yerine parametreler kullanılır. Heap boyunun parametre olması önemlidir: sıralama aşamasında dizinin boyu değişmez, ama heap her turda bir küçülür.

Birinci döngü aşağıdan yukarıya oluşturmadır. İkinci döngüde son, heap'in son öğesinin indisidir. Her turda kök ile a[son] takas edilir; en büyük öğe kesin yerine oturur. Ardından batir(a, 0, son) çağrılır. Üçüncü parametre son, heap'in yeni boyudur: son indisi ve sağındaki hücreler artık heap'e ait değildir ve batir onlara dokunmaz. Döngü son = 1'de son kez çalışır; tek öğe kalan heap'e işlem gerekmez.

Kodda kullanılan yerDegistir(a, i, j), dizinin iki hücresini takas eden üç satırlık bir yardımcı metottur:

static void yerDegistir(int[] a, int i, int j) {
  int t = a[i];  a[i] = a[j];  a[j] = t;
}

Klasik örnek dizi {4, 1, 3, 2, 16, 9, 10, 14, 8, 7} heap sort ile {1, 2, 3, 4, 7, 8, 9, 10, 14, 16} olur. Tablo 11.20 ikinci aşamanın her turundan sonraki diziyi veriyor.

11.5.6Kod izleme: heapSort([6, 5, 3, 4, 1, 2])

Daha küçük bir dizide ikinci aşamanın içine, yani her batir çağrısının adımlarına bakalım. Girdi a = [6, 5, 3, 4, 1, 2]'dir.

Birinci aşama. k = 2, 1, 0 için batir çağrılır. Bu dizi zaten bir max-heap'tir: 6 ≥ 5, 3; 5 ≥ 4, 1; 3 ≥ 2. Her çağrı ilk karşılaştırmada döner ve hiç takas yapılmaz.

Her turda sıralı kısım bir hücre büyür ve heap bir hücre küçülür. Beş turda kök ile son öğe arasındaki 5 takasa ek olarak batir 6 takas yapmıştır. İlk turlarda batir iki seviye iner; heap küçüldükçe yol da kısalır. Toplam maliyet log₂ n + log₂(n − 1) + … ≤ n log₂ n ile sınırlıdır: O(n log n).

11.5.7Öncelikli kuyrukla sıralama

Heap sort, daha genel bir fikrin özel bir durumudur. Herhangi bir öncelikli kuyrukla sıralama yapılabilir: bütün öğeler kuyruğa eklenir, sonra n kez removeMin ile sırayla çıkarılır. Çıkan öğeler artan sıradadır. Elde edilen algoritma ve çalışma süresi, kuyruğun hangi veri yapısıyla gerçeklendiğine bağlıdır.

Sırasız listede her removeMin kalan öğeler arasında en küçüğü arar ve onu çıkarır. Bu, seçimli sıralamanın tam tanımıdır: her adımda en küçüğü seç ve sıraya koy. Sıralı listede ise her insert yeni öğeyi sıralı kısımda doğru yerine yerleştirir; bu da eklemeli sıralamanın tanımıdır. Heap'te ise iki aşamanın da maliyeti dengelidir.

Bu tablo, ADT ile veri yapısı arasındaki ayrımın somut bir örneğidir. Algoritmanın metni (“hepsini ekle, sonra hepsini çıkar”) üç durumda da aynıdır. Yalnız kuyruğun gerçeklemesi değişmiş ve çalışma süresi O(n²)'den O(n log n)'e inmiştir.

11.5.8Heap türleri

İkili heap tek seçenek değildir. Farklı işlem karışımları için farklı heap türleri tasarlanmıştır.

d'li heap (d-ary heap), her düğümün en çok d çocuğu olduğu tam ağaçtır. Dizi gösterimi aynı mantıkla çalışır: 0 tabanlı gösterimde i indisli düğümün çocukları di + 1'den di + d'ye kadardır, ebeveyni ⌊(i − 1)/d⌋'dir. Örneğin 3'lü heap'te indis 7'nin ebeveyni ⌊6/3⌋ = 2'dir; indis 2'nin çocukları 7, 8 ve 9'dur.

d'li heap'in yüksekliği log_d n'dir ve d büyüdükçe ağaç alçalır. Up-heap her seviyede tek karşılaştırma yaptığı için ekleme hızlanır: O(log_d n). Down-heap ise her seviyede d çocuk arasından en büyüğünü seçmek zorundadır: silme O(d log_d n) olur. Eklemenin ve anahtar küçültmenin çok, silmenin az olduğu uygulamalarda (örneğin yoğun çizgelerde Dijkstra algoritması) d'li heap ikili heap'ten hızlı olabilir.

Binom heap ve Fibonacci heap tek bir ağaç değil, bir ağaç ormanıdır. Bu yapılar özellikle iki öncelikli kuyruğu birleştirme ve anahtar küçültme işlemlerini hızlandırmak için tasarlanmıştır. Fibonacci heap, Dijkstra ve Prim algoritmalarının kuramsal olarak en hızlı sürümlerinde kullanılır.

İkili heap'i birleştirmenin O(n) sürmesinin nedeni, iki dizinin uç uca eklenip aşağıdan yukarıya yeniden heap oluşturulmasıdır. Fibonacci heap'in kuramsal üstünlüğüne karşın uygulamada ikili heap çoğu zaman en hızlısıdır. Kodu basittir, sabit çarpanları küçüktür ve dizi yapısı önbelleği iyi kullanır. Java'nın PriorityQueue sınıfı ve Python'un heapq modülü de ikili heap kullanır.

11.6Java ve uygulamalar

Heap'i kendimiz yazmak, nasıl çalıştığını anlamanın en iyi yoludur. Gerçek programlarda ise çoğu zaman dilin hazır sınıfı kullanılır. Java'da bu sınıf java.util.PriorityQueue'dur. Bu kesim sınıfın kullanımını, içeride yaptığı işi ve heap'in iki tipik uygulamasını anlatır.

11.6.1Java'da hazır sınıf: PriorityQueue

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5); pq.offer(1); pq.offer(8);
pq.peek();   // 1  (min-heap, O(1))
pq.poll();   // 1  (O(log n))

// max-heap için ters karşılaştırıcı
PriorityQueue<Integer> maxPq =
    new PriorityQueue<>(Comparator.reverseOrder());

// hasta: öncelik küçük olan önce
PriorityQueue<Hasta> acil = new PriorityQueue<>(
    Comparator.comparingInt(h -> h.oncelik));

PriorityQueue<Integer> varsayılan olarak bir min-heap'tir: öğeleri doğal sıralarına göre karşılaştırır ve en küçüğü öne alır. offer ekleme, peek en öndeki öğeye bakma, poll en öndeki öğeyi çıkarma işlemidir. Üç offer'dan sonra peek() 1'i döndürür ve kuyruğu değiştirmez; poll() da 1'i döndürür ama onu çıkarır. Boş kuyrukta peek ve poll null döndürür. Aynı işleri yapan add, element ve remove metotları ise bu durumda istisna fırlatır.

Sıralama ölçütünü değiştirmek için kurucuya bir Comparator verilir. Comparator.reverseOrder() doğal sıranın tersini kullanır ve kuyruk bir max-heap gibi davranır: aynı 5, 1, 8 eklenirse peek() 8'i döndürür. Kendi tanımladığımız sınıflar için Comparator.comparingInt(h -> h.oncelik) gibi bir ifade, nesnenin hangi alanına göre karşılaştırılacağını söyler. Örnekteki acil kuyruğuna Ali (3), Ece (1), Can (2) ve Naz (1) eklenip sırayla çıkarılırsa önce önceliği 1 olan iki hasta, sonra Can, en son Ali çıkar.

Sınıfın dört özelliği bilinmelidir:

• İç yapı. İçeride dizi tabanlı bir ikili min-heap kullanır. Dizi dolunca kendiliğinden büyür.
• Maliyetler. offer ve poll O(log n); peek ve size O(1); remove(nesne) ve contains ise O(n)'dir, çünkü belirli bir nesne dizide doğrusal aranır.
• Eşzamanlılık. Sınıf iş parçacığı güvenli (thread-safe) değildir. Birden çok iş parçacığının aynı kuyruğu kullandığı programlarda PriorityBlockingQueue tercih edilir.
• Eşit öncelik. Eşit öncelikli öğeler için FIFO garantisi yoktur. Hasta örneğinde Ece'nin Naz'dan önce çıkması bu girdiye özgüdür; başka bir ekleme sırasında eşit öncelikli öğelerin sırası değişebilir.

11.6.2Kod izleme: PriorityQueue içeride ne yapar?

Aşağıdaki kısa program, sınıfın dışarıdan görünen davranışını gösterir. İzleme ise içerideki dizinin (Java kaynak kodundaki adıyla queue) her adımdaki durumunu verir.

PriorityQueue<Integer> pq =
    new PriorityQueue<>();        // min-heap
pq.offer(5);
pq.offer(1);
pq.offer(8);
System.out.println(pq.peek());    // bakar
System.out.println(pq.poll());    // çıkarır
System.out.println(pq.poll());
System.out.println(pq.size());

Programın çıktısı dört satırdır: 1 (peek), 1 ve 5 (iki poll), 1 (size). Java'nın kaynak kodundaki siftUp ve siftDown metotları, bu notta yuzdur ve batir adıyla yazılan up-heap ve down-heap işlemlerinin min-heap sürümleridir. Hazır sınıf, aynı algoritmayı genel bir Comparator ile çalışacak biçimde gerçekler.

PriorityQueue nesnesi println ile yazdırıldığında iç dizi olduğu gibi yazılır. Sıralı bir liste beklenmemelidir. Örneğin 3, 1, 2 eklenen kuyruk [1, 3, 2] olarak yazdırılır. Kuyruğun for-each ile gezilmesi de aynı iç düzeni verir. Öğeleri sıralı almanın tek yolu onları poll ile tek tek çıkarmaktır.

11.6.3k'ıncı en büyük öğe

Bir dizideki k'ıncı en büyük öğeyi bulmak sık karşılaşılan bir problemdir: bir sınavda en yüksek üçüncü not, bir sunucuda en yoğun onuncu saat gibi. Diziyi sıralamak bir çözümdür, ama O(n log n) sürer ve n öğenin hepsini bellekte tutmayı gerektirir. Boyutu en çok k olan bir min-heap daha iyi bir çözüm verir:

static int kinciEnBuyuk(int[] a, int k) {
  PriorityQueue<Integer> pq = new PriorityQueue<>();
  for (int x : a) {
    pq.offer(x);                    // O(log k)
    if (pq.size() > k) pq.poll();  // en küçüğü at
  }
  return pq.peek();       // k büyüğün en küçüğü
}

Algoritmanın değişmezi şudur: her adımın sonunda heap, o ana kadar görülen öğelerin en büyük k tanesini tutar. Min-heap olduğu için kökte bu k öğenin en küçüğü durur. Yeni bir öğe gelince heap'e eklenir. Heap k + 1 öğeye ulaşırsa en küçüğü atılır, çünkü elinde kendisinden büyük k öğe olan bir öğe en büyük k arasına giremez. Döngü bittiğinde kökteki öğe, dizinin en büyük k öğesinin en küçüğü, yani k'ıncı en büyük öğedir.

kinciEnBuyuk([5, 1, 9, 3, 7, 6], 3) çağrısını izleyelim.

Atılan öğeler 1, 3 ve 5'tir; hepsi en büyük üçün dışında kalan öğelerdir. Dizinin sıralı hâli [1, 3, 5, 6, 7, 9]'dur ve üçüncü en büyük gerçekten 6'dır.

Maliyet: heap en çok k + 1 öğe tutar. Her offer ve poll bu yüzden O(log k) sürer. n öğe için toplam zaman O(n log k), ek bellek O(k)'dir. k küçükse bu, sıralamadan belirgin biçimde hızlıdır. Bellek kazancı da önemlidir: öğeler bir dosyadan ya da ağdan akıyorsa hepsini saklamak gerekmez, yalnız k tanesi tutulur.

11.6.4k sıralı listeyi birleştirme

Heap'in bir başka tipik kullanımı, kendi içinde sıralı k listeyi tek bir sıralı listede birleştirmektir. Büyük dosyaların parça parça sıralanıp sonra birleştirildiği dış sıralama bu işi yapar. Toplam öğe sayısı N olsun.

Yöntem şöyledir. Her listenin ilk öğesi bir min-heap'e konur; heap'teki her öğe hangi listeden geldiğini de bilir. Sonra şu adım heap boşalana kadar tekrarlanır: en küçük öğe çıkarılır ve çıktıya yazılır; o öğenin geldiği listede sıradaki öğe varsa heap'e eklenir. Heap her an her listeden en çok bir öğe, yani en çok k öğe tutar.

Her öğe heap'e bir kez girer ve bir kez çıkar. Heap'in boyu en çok k olduğu için her işlem O(log k)'dir ve toplam maliyet O(N log k)'dir. Bütün öğeleri tek bir diziye toplayıp sıralamak O(N log N) sürerdi.

11.6.5Öncelikli çizelgeleyici

İşletim sistemindeki çizelgeleyici (scheduler), işlemciyi bekleyen süreçler arasından hangisinin çalışacağına karar verir. Öncelikli çizelgelemede her sürecin bir öncelik seviyesi vardır. Sık kullanılan bir düzen, her seviye için ayrı bir FIFO kuyruğu tutmaktır.

• Kesin öncelik. İşlemci her zaman en yüksek öncelikli, boş olmayan kuyruğun önündeki süreci seçer. Şekil 11.30'da önce P4 çalışır. Yüksek seviye boşalınca orta seviyedeki P1 ve P5'e sıra gelir.
• Seviye içinde FIFO. Aynı öncelikteki süreçler kendi kuyruklarında geliş sırasıyla çalışır. Her süreç belli bir zaman dilimi (quantum) kadar çalışıp kuyruğun sonuna dönüyorsa seviye içinde round robin uygulanmış olur.
• Açlık ve yaşlandırma. Yüksek öncelikli süreçler sürekli geliyorsa düşük öncelikliler hiç çalışamayabilir. Bu duruma açlık (starvation) denir. Yaygın çözüm yaşlandırmadır (aging): bir süreç bekledikçe önceliği adım adım artırılır ve sonunda üst seviyelere çıkıp çalışma fırsatı bulur.

Seviye sayısı az olduğunda her seviye için ayrı bir kuyruk tutmak en basit ve en hızlı çözümdür: en yüksek boş olmayan seviyeyi bulmak sabit sayıda adımdır. Öncelikler geniş bir aralıktan geliyorsa (örneğin her sürecin bir son teslim zamanı varsa) tek bir heap kullanılır. Anahtar olarak (öncelik, geliş sıra numarası) çifti seçilirse aynı öncelikteki süreçlerin FIFO düzeni de korunur. Yaşlandırma ise bir anahtar değiştirme işlemidir ve uyarlanabilir öncelikli kuyrukla O(log n)'de yapılır.

11.7Sık yapılan hatalar

Bölüm boyunca konuların yanında verilen hataların en sık görülenleri aşağıdaki tabloda toplanmıştır. Bir heap kodunu gözden geçirirken kontrol listesi olarak kullanılabilir.

Bu hataların çoğu küçük testlerde görünmez. Sağ çocuk sınırı hatası yalnız belirli boyutlarda, eşitlik hatası yalnız eşit anahtarlar varken ortaya çıkar. Bir heap gerçeklemesini sınamanın güvenilir yolu, her işlemden sonra heapMi ile diziyi denetlemek ve sonuçları hazır bir sınıfla (örneğin PriorityQueue) rastgele girdilerde karşılaştırmaktır.

11.8Özet

• Öncelikli kuyruk, öğelerin geliş sırasına göre değil önceliğe göre çıktığı bir ADT'dir. Her öğe bir (anahtar, değer) çiftidir. Temel işlemleri insert, min, removeMin, size ve isEmpty'dir. Max-öncelikli kuyrukta max ve removeMax kullanılır. Eşit anahtarlarda FIFO garantisi yoktur; gerekiyorsa anahtara sıra numarası eklenir.
• Liste ile gerçeklemede sırasız liste O(1)'de ekler ama O(n)'de çıkarır; sıralı liste tersini yapar. İkisinde de n ekleme ve n çıkarma O(n²) sürer. Sıralı dizide en öncelikli öğe sonda, bağlı listede başta tutulur.
• İkili heap, heap-sıra özelliğini (max-heap'te ebeveyn ≥ çocuk) ve tam ikili ağaç özelliğini birlikte sağlar. En öncelikli öğe köktedir. Yükseklik ⌊log₂ n⌋'dir. Heap sıralı değildir ve ikili arama ağacı değildir.
• Dizi gösteriminde düğümler seviye sırasıyla yazılır; boşluk ve referans yoktur. 0 tabanlı indislerde çocuklar 2i + 1, 2i + 2; ebeveyn ⌊(i − 1)/2⌋'dir.
• Ekleme öğeyi heap[n]'e yazar ve up-heap ile yukarı taşır; silMax son öğeyi köke koyar ve down-heap ile büyük çocuk yönünde aşağı indirir. İkisi de O(log n)'dir. Down-heap'te sağ çocuk için j + 1 < n denetimi şarttır. Kapasite iki katına büyütülür; büyütme amortize O(1)'dir.
• Uyarlanabilir öncelikli kuyruk replaceKey ve remove işlemlerini ekler. Öğe dizideki yerini bilirse bu işlemler bir up-heap ya da down-heap ile O(log n)'de yapılır.
• Aşağıdan yukarıya heap oluşturma son iç düğümden (⌊n/2⌋ − 1) köke doğru down-heap uygular ve O(n)'dir. Down-heap'in maliyeti yüksekliğe bağlıdır ve düğümlerin çoğu alçaktır. n kez ekleme ise O(n log n)'dir.
• Heap sort önce heap oluşturur, sonra n − 1 kez kökü sona alıp heap'i küçültür. Yerinde çalışır, en kötü durumda O(n log n)'dir, kararlı değildir. Öncelikli kuyrukla sıralama sırasız listede seçimli sıralamayı, sıralı listede eklemeli sıralamayı verir.
• Java'nın PriorityQueue sınıfı dizi tabanlı ikili min-heap'tir; max için Comparator.reverseOrder() verilir. Boyutu k olan bir min-heap k'ıncı en büyük öğeyi O(n log k)'de bulur; aynı fikir k sıralı listeyi O(N log k)'de birleştirir.

11.9Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• öncelikli kuyruk priority queue
• soyut veri tipi abstract data type (ADT)
• anahtar key
• değer value
• kuyruk queue
• ilk giren ilk çıkar FIFO
• arayüz interface
• jenerik generic
• ikili heap binary heap
• heap heap
• max-heap max-heap
• min-heap min-heap
• tam ikili ağaç complete binary tree
• mükemmel ikili ağaç perfect binary tree
• kök root
• yaprak leaf
• iç düğüm internal node
• ebeveyn parent
• çocuk child
• kardeş sibling
• seviye level
• seviye sırası level-order
• yükseklik height
• derinlik depth
• up-heap (yukarı süzme) up-heap
• down-heap (aşağı süzme) down-heap
• takas swap
• kapasite capacity
• dinamik dizi dynamic array
• amortize analiz amortized analysis
• uyarlanabilir öncelikli kuyruk adaptable priority queue
• aşağıdan yukarıya heap oluşturma bottom-up heap construction
• heap sort heap sort
• yerinde in-place
• kararlı stable (sort)
• seçimli sıralama selection sort
• eklemeli sıralama insertion sort
• hızlı sıralama quick sort
• round robin round robin
• yaşlandırma aging

11.10Kendini Dene

1. Boş bir min-öncelikli kuyruğa sırasıyla insert(7, a), insert(2, b), insert(9, c), removeMin(), insert(1, d), min(), removeMin(), removeMin() uygulanıyor. Değer döndüren çağrılar ne döndürür ve sonda kuyrukta ne kalır?

   Cevap

   İlk removeMin() (2, b)'yi döndürür; kuyruk {(7,a), (9,c)}. (1, d) eklenince en küçük odur: min() (1, d)'yi çıkarmadan döndürür. Sonraki removeMin() (1, d)'yi, ardından gelen (7, a)'yı döndürür. Sonda kuyrukta yalnız (9, c) kalır; size() 1'dir.

2. Kapasitesi 4 olan boş bir max-heap'e sırasıyla 3, 8, 6, 10, 1, 9 ekleniyor. Son dizi nedir? Toplam kaç takas yapılır ve kapasite ne zaman büyür?

   Cevap

   [3] → 8 eklenince 3 ile takas: [8, 3] → 6 yerinde kalır: [8, 3, 6] → 10 önce 3 ile, sonra 8 ile takas: [10, 8, 6, 3] → 1 eklenmeden önce dizi dolu olduğu için kapasite 8'e büyür; 1 yerinde kalır: [10, 8, 6, 3, 1] → 9, ebeveyni 6 ile takas edilir, 10'un altında durur. Son dizi [10, 8, 9, 3, 1, 6]; toplam 4 takas.

3. Max-heap [20, 15, 18, 7, 12, 16, 4] üzerinde art arda iki silMax() yapılıyor. Dönen değerler ve sondaki heap nedir?

   Cevap

   Birinci: 20 döner. 4 köke gelir: [4, 15, 18, 7, 12, 16]. Büyük çocuk 18: [18, 15, 4, 7, 12, 16]; indis 2'de tek çocuk 16: [18, 15, 16, 7, 12, 4]. İkinci: 18 döner. 4 köke gelir: [4, 15, 16, 7, 12]. Büyük çocuk 16: [16, 15, 4, 7, 12]; indis 2 yaprak. Son heap [16, 15, 4, 7, 12].

4. 25 öğeli bir ikili heap'in yüksekliği nedir? Aşağıdan yukarıya oluşturmada döngü hangi indisten başlar ve kaç düğüm yapraktır? 0 tabanlı gösterimde indis 20'nin ebeveyni hangi indistedir?

   Cevap

   Yükseklik ⌊log₂ 25⌋ = 4'tür (16 ≤ 25 < 32). Döngü ⌊25/2⌋ − 1 = 11'den başlar; indis 12'den 24'e kadar olan 13 düğüm yapraktır. İndis 20'nin ebeveyni ⌊19/2⌋ = 9'dur; çocuk adayı 41 ≥ 25 olduğundan 20 bir yapraktır.

5. [5, 13, 2, 25, 7, 17, 20, 8, 4] dizisi aşağıdan yukarıya yöntemle max-heap'e çevriliyor. Her batir(k)'dan sonra dizi nedir ve toplam kaç takas yapılır?

   Cevap

   n = 9, ilk k = 3. k = 3: 25 ≥ 8, 4; değişmez. k = 2: 2, büyük çocuk 20 ile takas: [5, 13, 20, 25, 7, 17, 2, 8, 4]. k = 1: 13, 25 ile takas; inen 13 ≥ 8, 4: [5, 25, 20, 13, 7, 17, 2, 8, 4]. k = 0: 5, sırasıyla 25, 13 ve 8 ile takas edilir: [25, 13, 20, 8, 7, 17, 2, 5, 4]. Toplam 5 takas.

6. [5, 2, 8, 1, 9] dizisi heap sort ile sıralanıyor. Oluşturmadan sonra ve her “kökü sona al + batir” turundan sonra dizi nedir?

   Cevap

   Oluşturma: k = 1'de 2 ↔ 9, k = 0'da 5 ↔ 9 ve ardından 5'in çocukları 1 ve 2'den büyük olduğu için durur: [9, 5, 8, 1, 2]. Turlar: [8, 5, 2, 1 | 9] → [5, 1, 2 | 8, 9] → [2, 1 | 5, 8, 9] → [1 | 2, 5, 8, 9]. Sonuç [1, 2, 5, 8, 9].

7. Max-heap [15, 9, 12, 4, 8, 10, 3] üzerinde anahtarDegistir(1, 2) çağrılıyor. Hangi işlem çalışır ve son dizi nedir?

   Cevap

   Anahtar 9'dan 2'ye küçüldüğü için batir(1) çalışır. İndis 1'in çocukları 4 ve 8'dir; büyük olan 8 (indis 4). 2 < 8, takas; indis 4 yapraktır. Son dizi [15, 8, 12, 4, 2, 10, 3]. Kökteki 15 ve sağ alt ağaç hiç incelenmedi.

8. kinciEnBuyuk([3, 11, 6, 2, 9, 14, 5], 2) ne döndürür? Döngü boyunca hangi öğeler atılır?

   Cevap

   Heap en çok iki öğe tutar. 3 ve 11'den sonra 6 gelince en küçük 3 atılır: {6, 11}. 2 eklenince hemen kendisi atılır. 9 gelince 6, 14 gelince 9, 5 gelince 5 atılır. Sonda heap {11, 14}'tür ve peek() 11'i döndürür: dizinin ikinci en büyük öğesi. Atılan öğeler sırasıyla 3, 2, 6, 9, 5'tir.

9. 1023 düğümlü mükemmel bir ikili ağaç (yükseklik 9) için en kötü durumda aşağıdan yukarıya oluşturma kaç takas yapar? Aynı öğeler artan sırada tek tek eklenseydi kaç takas yapılırdı?

   Cevap

   Yüksekliği h olan 2^9−h düğüm vardır ve her biri en çok h takas yapar: Σ h · 2^9−h = 1013. Bu, n − log₂(n + 1) = 1023 − 10'a eşittir ve n'den küçüktür. Artan sırada eklemede her öğe köke kadar çıkar; derinliği d olan 2^d düğüm d takas yapar: Σ d · 2^d = 8 · 2¹⁰ + 2 = 8194. Fark sekiz kattan fazladır.

10. Max-heap [10, 4, 9, 1, 3, 8, 7]'den indis 4'teki öğe (3) uyarlanabilir kuyruğun remove işlemiyle siliniyor. Yerine hangi öğe gelir, hangi süzme gerekir ve son dizi nedir?

    Cevap

    Silinen öğe son öğe 7 ile takas edilir ve n 6'ya iner: [10, 4, 9, 1, 7, 8]. 7, ebeveyni 4'ten büyüktür; down-heap değil up-heap gerekir. 7 ile 4 yer değiştirir; yeni ebeveyn 10 ≥ 7 olduğu için durulur. Son dizi [10, 7, 9, 1, 4, 8]. Son öğe, silinen düğümün alt ağacından değil, ağacın öbür dalından gelmiştir.

11.11İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), 9. bölüm: öncelikli kuyruk ADT'sini, liste ve heap gerçeklemelerini, konum farkında öğelerle uyarlanabilir öncelikli kuyruğu bu nottakine yakın bir Java koduyla anlatır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (4. baskı, 2022), 6. bölüm: heap'i, aşağıdan yukarıya oluşturmanın doğrusal maliyetinin ispatını, heap sort'u ve heap tabanlı öncelikli kuyrukları biçimsel bir dille verir; nottaki on öğeli örnek bu kitaptandır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 2.4: ikili heap'i 1 tabanlı dizide swim ve sink adlı işlemlerle anlatır; indeksli öncelikli kuyruk ve çok yollu birleştirme örnekleri içerir.
• R. W. Floyd, “Algorithm 245: Treesort 3” (1964): aşağıdan yukarıya heap oluşturmanın ilk yayımlandığı bir sayfalık kısa makaledir; Williams'ın heapsort'unu geliştirir.

11.12Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022.
2. R. W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 7(12), s. 701, 1964.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
4. Oracle, Java SE 17 API Specification: java.util.PriorityQueue belgesi.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
6. J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM, 7(6), s. 347–348, 1964.

İlgili sayfalar: Bölüm 11 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.