Bölüm 13: Öncelikli Kuyruk ve Heap

13.1Öncelikli kuyruk

Kuyruk, öğelerin bir uçtan girip öbür uçtan çıktığı yapıdır. Bu düzen adildir: önce gelen önce hizmet alır. Ama her iş için doğru düzen bu değildir. Hastanenin acil servisinde hastalar geliş sırasına göre değil, durumlarının ağırlığına göre muayene edilir. Bu kesim, böyle bir düzeni tanımlayan veri yapısını ve ona neden gereksinim duyulduğunu anlatır.

13.1.1Kuyruktan farkı

Sıradan kuyrukta (queue) iki işlem vardır. Ekleme yeni öğeyi kuyruğun arkasına koyar; silme kuyruğun başındaki öğeyi alır. Bu kurala ilk giren ilk çıkar (first in, first out, FIFO) denir. Öncelikli kuyrukta ise her öğenin bir önceliği vardır ve silme işlemi bu önceliğe bakar.

Öncelik değerine çoğu kaynakta anahtar (key) denir. Bu notta iki sözcük aynı anlamda kullanılır. Hangi değerin “öncelikli” sayılacağı probleme bağlıdır. Bir yarışta en kısa süre en iyisidir; bir müzayedede en yüksek teklif. İki tür arasındaki fark yalnız karşılaştırmanın yönündedir. Bu yüzden not çoğunlukla maksimum öncelikli kuyruğu anlatır. Minimum sürüm, karşılaştırma işaretleri ters çevrilerek elde edilir.

Şekil 13.1 farkı dört öğe üzerinde gösterir. Öğelerin adı bir harf, önceliği bir sayıdır: A:3, B:9, C:5, D:7. Dört öğe bu sırayla gelmiştir. Sıradan kuyruk ilk geleni, yani A'yı verir. Maksimum öncelikli kuyruk ise önceliği en yüksek olan B'yi verir; B ikinci gelmiş olsa da sırası beklenmez. İkinci silmede sıradan kuyruk B'yi, öncelikli kuyruk D'yi verir. Öncelikli kuyruğun bütün çıkış sırası B, D, C, A'dır; öğeler önceliklerinin azalan sırasıyla çıkar.

Tanım, öğelerin yapıda nasıl dizildiğinden söz etmez. Yalnız hangi öğenin ilk çıkacağını söyler. Bu önemli bir serbestliktir. Kuyruğu gerçekleyen yapı, öğeleri istediği gibi düzenleyebilir; yeter ki istendiğinde en öncelikli öğeyi bulup verebilsin. Notun büyük bölümü bu serbestliği en iyi kullanan düzeni, heap'i anlatır.

13.1.2Neden gerekir?

Sunum öncelikli kuyruğa duyulan gereksinimi iki örnekle açıklar. İkisinde de geliş sırası doğru kararı vermez.

Fotokopi makinesi. Bir fotokopi makinesini kullanan herkes sabit bir ücret öder. Üç sayfa çeken de otuz sayfa çeken de aynı parayı verir. Makinenin sahibi kazancını en büyük yapmak ister, yani belli bir sürede olabildiğince çok kullanıcıya hizmet vermek ister. Bunun yolu, kullanım süresi en kısa olan kullanıcıya öncelik vermektir. Üç sayfalık iş önce yapılırsa o kullanıcı hemen ayrılır ve ücretini öder; otuz sayfalık iş beklese de toplam kazanç artar. Burada ilk ele alınacak öğe en küçük değerli öğedir: bu bir minimum öncelikli kuyruktur.

Havaalanı. Bir havaalanına inmek için sıra bekleyen uçakları düşünelim. Kuleye önce gelen uçağın önce indirilmesi ilk bakışta adil görünür. Ama yakıtı bitmek üzere olan bir uçağa “kuyruğun arkasındasın, sıranı bekle” denemez. İniş izni, kalan yakıtı en az olan uçağa verilir. Bu da bir minimum öncelikli kuyruktur: anahtar kalan yakıt miktarıdır.

Gerçek sistemler de böyle çalışır. Bir işletim sistemi, çalışmaya hazır işlemleri (process) öncelikli bir kuyrukta tutar. Bir kesme geldiğinde ya da bir işlemin süresi dolduğunda, işlemciye kuyruktaki en öncelikli işlem alınır. Bu tür sistemlerde kuyruk sürekli değişir: yeni işler gelir, biten işler çıkar. Bu yüzden yapının hem eklemeyi hem en öncelikli öğeyi almayı hızlı yapması gerekir. Asıl zorluk, bu iki işlemi birlikte ucuz tutmaktır.

13.1.3Soyut veri tipi

İşlemleri ve davranışları tanımlanan ama gerçeklemesi gizlenen tipe soyut veri tipi (abstract data type, ADT) denir. Öncelikli kuyruk da bir soyut veri tipidir. Sunum maksimum öncelikli kuyruğun arayüzünü şöyle verir:

/* maksimum öncelikli kuyruk arayüzü */
bool bos_mu(void);
bool dolu_mu(void);
void ekle(eleman item);     /* O(lg n) */
bool maks_al(eleman *cikan); /* sil + döndür */
bool maks_bak(eleman *ust);  /* silmeden bak */

Arayüzde beş işlem vardır. bos_mu ve dolu_mu kuyruğun durumunu sorar. Sabit kapasiteli bir gerçeklemede dolu kuyruğa ekleme yapılamaz; bu yüzden dolu_mu da arayüzdedir. ekle bir öğeyi önceliğiyle birlikte yapıya koyar. maks_al en öncelikli öğeyi hem döndürür hem yapıdan çıkarır; bu işleme sunumda al ya da sil denir. maks_bak ise en öncelikli öğeyi yapıdan çıkarmadan okur.

Alma ve bakma işlemleri öğeyi dönüş değeri olarak değil, bir işaretçi parametresi aracılığıyla verir. Dönüş değeri işlemin başarılı olup olmadığını söyleyen bir bool'dur. Boş kuyrukta alınacak öğe yoktur. Böyle bir durumda öğe döndüren bir fonksiyon “anlamsız” bir öğe uydurmak zorunda kalırdı. false dönüşü ise çağırana açıkça “öğe yok” der. Öğeyi bir yapı olarak döndüren bir fonksiyonda “boş” durumunu bildirecek uygun bir değer de yoktur.

Arayüz, kuyruğun nasıl gerçekleneceğini söylemez. Öncelikli kuyruk sırasız bir diziyle, sıralı bir diziyle, bağlı bir listeyle ya da bir heap'le gerçeklenebilir. Hepsi aynı arayüzü sunar ve kullanan program farkı görmez. Fark yalnız maliyettedir. Basit yapılar işlemlerden birini çok ucuz, ötekini çok pahalı yapar. Heap ise iki işlemi de O(lg n) sürede yapar. Bu dengesi, heap'i öncelikli kuyruğun en yaygın gerçeklemesi yapar.

13.2Heap yapısı

Heap iki kuralın birleşimidir. Birinci kural yapının şeklini belirler: heap bir tam ikili ağaçtır. İkinci kural değerlerin düzenini belirler: her düğüm çocuklarından büyük ya da onlara eşittir. Bu kesim önce şekil kuralını ve onun dizide nasıl saklandığını, sonra düzen kuralını anlatır.

Bir terim notu: sunumdaki C kodlarında heap'i tutan dizinin adı yigin'dir ve yordamlar maksimum_yigin_ekle gibi adlar taşır. Bu adlar ders kitabının Türkçe çevirisinden gelir. Bu derste yığın sözcüğü ise stack için kullanılır. Karışıklığı önlemek için not metinde yapının adını hep heap diye yazar; kodlardaki adlar olduğu gibi kalır. Heap sözcüğü malloc'un bellek ayırdığı heap bellek ile de karıştırılmamalıdır. İkisi arasında, adın dışında bir bağ yoktur.

13.2.1Dizide tam ikili ağaç

İkili ağaçta her düğümün en çok iki çocuğu vardır. Bir düğümün hemen üstündeki düğüme ebeveyn (parent) denir. Kökten aynı uzaklıktaki düğümler aynı düzeydedir (level). Bu notta kök 0. düzeydedir.

Tam ikili ağacın şekli yalnız düğüm sayısına bağlıdır. 6 düğümlü bir tam ikili ağaç tek bir şekilde çizilebilir: kök, onun iki çocuğu ve son düzeyde soldan üç düğüm. Bu katılık bir kazanç sağlar. Düğümler düzey düzey, her düzeyde soldan sağa numaralanırsa her düğümün numarası ağacın şeklinden kesin olarak bellidir. Kök 1 numarayı, onun sol çocuğu 2'yi, sağ çocuğu 3'ü alır; sonraki düzeyin düğümleri 4, 5, 6, 7 diye devam eder. Bu numaralar doğrudan dizi indisi olarak kullanılabilir.

Şekil 13.2 altı düğümlü bir tam ikili ağacı ve onun dizideki karşılığını gösterir. Ağaçtaki her düğüm, numarasıyla aynı indisteki dizi hücresinde durur. Kökteki 14 yigin[1]'de, kökün çocukları 12 ve 7 yigin[2] ile yigin[3]'te, son düzeydeki 10, 8 ve 6 sırasıyla yigin[4], yigin[5] ve yigin[6]'dadır. Dizinin 0. hücresi kullanılmaz. Bu küçük israf, indis formüllerini sadeleştirmek içindir.

Numaralamanın en önemli sonucu, ebeveyn ile çocuklar arasındaki ilişkinin basit aritmetikle bulunmasıdır. i. düğümün sol çocuğu 2i, sağ çocuğu 2i + 1, ebeveyni ise ⌊i/2⌋ indisindedir. C'de iki tamsayının bölümü küçük tarafa yuvarlandığı için i / 2 ifadesi bu tabanı doğrudan verir. Tablo 13.1 bu kuralları toplar.

Kuralların neden doğru olduğu küçük bir sayımla görülür. d. düzeyde 2^d düğüm vardır ve bu düzeyin ilk düğümünün numarası 2^d'dir: 1, 2, 4, 8, … i numaralı düğüm kendi düzeyinde soldan k. sırada olsun (0'dan sayarak); yani i = 2^d + k. Bu düğümün solundaki k düğümün her birinin iki çocuğu vardır. Bu yüzden onun sol çocuğu, bir alt düzeyde soldan 2k. sıradadır. Alt düzeyin ilk numarası 2^d+1 olduğundan sol çocuğun numarası 2^d+1 + 2k = 2(2^d + k) = 2i'dir. Sağ çocuk onun hemen sağındadır: 2i + 1. Ebeveynin formülü bunların tersidir. 2i de 2i + 1 de 2'ye bölününce taban olarak i verir.

Bazı kaynaklar diziyi 0. hücreden başlatır. O zaman bütün numaralar bir azalır ve formüller değişir: ebeveyn (i - 1) / 2, çocuklar 2i + 1 ve 2i + 2 olur. Her iki düzen de doğrudur; ama bir programda ikisi karıştırılmamalıdır. Sunum ve bu not, formülleri sade tutan 1 tabanlı düzeni kullanır.

Bu gösterimin bedeli yoktur. Bağlı bir ağaçta her düğüm iki çocuk işaretçisi taşır; bir int anahtar için düğüm başına 8 ya da 16 bayt fazladan bellek harcanır. Dizide bu işaretçilere gerek kalmaz, çünkü tam ikili ağaçta düğümler arasında boşluk yoktur ve çocukların yeri hesapla bulunur. Dizinin hücreleri bellekte yan yana durduğu için işlemci önbelleği (cache) de bu yapıyla iyi çalışır. Kazanç tam ikili ağaca özgüdür. Seyrek, dengesiz bir ağaç bu yolla saklansaydı dizinin büyük kısmı boş kalırdı. Heap'te şekil kuralı tam da bu yüzden vardır.

13.2.2Heap ikili arama ağacı değildir

Heap denince akla bir ikili arama ağacı değil, tam ikili ağaç gelmelidir. İki yapı da ikili ağaçtır ve ikisinde de değerler belli bir düzene uyar; ama düzenleri çok farklıdır. İkili arama ağacında (binary search tree) her düğümün sol alt ağacındaki değerler ondan küçük, sağ alt ağacındakiler ondan büyüktür: sol < kök < sağ. Heap'te ise yalnız ebeveyn ≥ çocuk kuralı vardır. Sol çocuk ile sağ çocuk arasında hiçbir sıra aranmaz.

Şekil 13.3 aynı dokuz değerin, 47, 26, 55, 17, 34, 49, 84, 52, 93'ün iki yapıdaki yerleşimini gösterir. İkili arama ağacında kök 47'dir; 26 solda, 55 sağdadır. Ağacın şekli değerlerin geliş sırasına bağlıdır. Örnekte 84'ün altında iki düğüm varken 17'nin hiç çocuğu yoktur; ağaç tam değildir. Heap'te kök en büyük değer olan 93'tür. Şekil tamdır: ilk üç düzey dolu, son düzeyde soldan iki düğüm vardır. Kökün sol çocuğu 84, sağ çocuğu 55'tir; bu iki değer arasında bir sıra kuralı yoktur.

İki yapı farklı soruları cevaplar. İkili arama ağacında bir değeri aramak kolaydır: her düğümde sola ya da sağa gidilir. Heap'te bir değeri aramak için böyle bir yön yoktur; 34'ü bulmak için kökün iki alt ağacına da bakmak gerekebilir. Buna karşılık heap'in cevapladığı tek soru çok hızlı cevaplanır: en büyük değer her zaman köktedir. Heap bir arama yapısı değil, öncelikli kuyruk yapısıdır.

13.2.3Maksimum ve minimum heap

Tanımdaki “küçük değilse” ifadesi bilinçli seçilmiştir. Ebeveyn çocuğuna eşit olabilir; aynı önceliği taşıyan iki öğe heap'te ebeveyn ve çocuk olarak durabilir. Tanımın iki parçası ayrı ayrı yeterli değildir. Heap özelliğini sağlayan ama tam olmayan bir ağaç heap değildir; tam olup heap özelliğini sağlamayan ağaç da değildir. Bu tanımlar maksimum ve minimum öncelikli kuyruğu gerçeklemek için verilmiştir. Maksimum heap maksimum öncelikli kuyruğu, minimum heap minimum öncelikli kuyruğu gerçekler.

Şekil 13.4 her türden üç örnek verir. Üstteki ilk maksimum heap notun ana örneğidir: 14, 12, 7, 10, 8, 6. Her ebeveyn çocuklarından büyüktür: 14 ≥ 12, 14 ≥ 7, 12 ≥ 10, 12 ≥ 8, 7 ≥ 6. Kökün sağ çocuğu 7, sol alt ağaçtaki 10 ve 8'den küçüktür. Bu bir sorun değildir; 7 ile 10 arasında ebeveyn–çocuk ilişkisi yoktur. Alttaki minimum heap'lerde kural terstir. İlk örnek 2, 7, 4, 10, 8, 6'da her ebeveyn çocuklarından küçüktür ve kökte en küçük değer, 2 durur.

Heap özelliği yalnız komşu düzeyleri bağlar. Ama zincirleme olarak çok daha güçlü bir sonuç verir: kökten bir yaprağa giden her yolda değerler azalmayan değil, artmayan bir dizi oluşturur. Bundan da kökün bütün ağacın en büyük değeri olduğu çıkar.

Kanıt. i numaralı bir düğüm alınsın. Ebeveyni ⌊i/2⌋, onun ebeveyni ⌊i/4⌋, … diye gidilirse sonlu adımda köke, 1 numaraya varılır, çünkü her adımda numara en az yarıya iner. Bu zincirdeki her ardışık çift bir ebeveyn–çocuk çiftidir ve heap özelliği gereği ebeveynin değeri çocuğunkinden küçük değildir. Eşitsizlikler zincirlenince yigin[1] ≥ … ≥ yigin[⌊i/2⌋] ≥ yigin[i] elde edilir. i herhangi bir düğüm olduğundan kök bütün değerlerden küçük değildir. ∎

Teorem öncelikli kuyruğun en sık sorusunu, “en büyük öğe hangisi?” sorusunu O(1)'de cevaplar: yigin[1]. Dizinin geri kalanı ise sıralı değildir. Örnek heap'te ikinci büyük değer 12, 2. indistedir; ama üçüncü büyük değer 10, 3. indiste değil 4. indistedir. Garanti yalnız 1. indis içindir. İkinci büyük değer her zaman kökün çocuklarından biridir. Üçüncü büyük ise kökün öbür çocuğu da olabilir, büyük çocuğun bir çocuğu da.

13.2.4Heap mi, değil mi?

Bir dizinin maksimum heap olup olmadığını anlamak için bütün ebeveyn–çocuk çiftlerine bakmak yeter. Dizi gösteriminde şekil kuralı kendiliğinden sağlanır, çünkü 1..n indisleri boşluksuz doludur. Geriye yalnız düzen kuralı kalır: her k ≥ 2 için yigin[k/2] ≥ yigin[k] olmalıdır. Kardeşler ya da kuzenler arasında bir sıra aranmaz. Aşağıdaki yardımcı fonksiyon bu sınamayı yapar:

bool heap_mi(eleman a[], int n) {
  for (int k = 2; k <= n; k++)
    if (a[k / 2].x < a[k].x) return false;  /* ebeveyn < çocuk */
  return true;
}

Döngü 2'den n'e kadar her düğümü bir kez ebeveyniyle karşılaştırır. Kök dışındaki her düğümün tek bir ebeveyni olduğu için bütün ebeveyn–çocuk çiftleri tam bir kez denetlenir. İlk ihlalde false döner. Maliyet en çok n − 1 karşılaştırmadır, yani O(n). Bu fonksiyon heap'in parçası değildir; ama yazılan yordamları sınamak için çok kullanışlıdır. Bu notun bütün sayıları, her işlemden sonra bu sınamayı yapan test programlarıyla doğrulanmıştır.

13.2.5C tanımları

Sunumdaki ilk gerçekleme, heap'i bir global dizi ve bir öğe sayacıyla tutar. Tanımlar şöyledir:

#define ELEMAN_SAYISI 200   /* maksimum öğe + 1 */
#define YIGIN_DOLUMU(n) ((n) == ELEMAN_SAYISI - 1)
#define YIGIN_BOSMU(n)  (!(n))

typedef struct {
  int x;          /* öncelik (anahtar) */
  /* diğer alanlar */
} eleman;

eleman yigin[ELEMAN_SAYISI];  /* [0] kullanılmaz */
int n = 0;                    /* öğe sayısı */

ELEMAN_SAYISI dizinin boyutudur. 0. hücre kullanılmadığı için heap en çok ELEMAN_SAYISI − 1 = 199 öğe alır; açıklamadaki “maksimum öğe + 1” bu yüzdendir. Kullanılan indisler 1..199'dur. YIGIN_DOLUMU(n) makrosu öğe sayısının bu sınıra ulaşıp ulaşmadığını, YIGIN_BOSMU(n) ise öğe sayısının sıfır olup olmadığını sınar. !(n) ifadesi n sıfırsa 1, değilse 0 verir.

Öğe tipi eleman bir yapıdır. Tek alanı x, önceliği tutar. Gerçek bir uygulamada yapıda başka alanlar da bulunur: bir işlemin numarası, bir uçağın kuyruk kodu gibi. Heap yordamları yalnız x'e bakar; öteki alanlar öğeyle birlikte taşınır. Bu yüzden yordamlar öğeleri tamsayı olarak değil, bütün yapı olarak kopyalar. yigin[i] = yigin[j] ataması yapının bütün alanlarını bir kerede kopyalar. Bu notun örneklerinde yapı tek bir int taşıdığı için 4 bayttır.

Makrolarda parametrenin parantez içinde yazılması bir alışkanlık değil, zorunluluktur. Makro bir fonksiyon değildir; önişlemci metni olduğu gibi yerine koyar. #define YIGIN_BOSMU(n) (!n) yazılmış olsun. YIGIN_BOSMU(a + b) çağrısı (!a + b)'ye açılır. ! işleci +'dan önce uygulandığı için bu ifade (!a) + b olarak hesaplanır; a = 0, b = 5 için sonuç 6'dır ve “boş” anlamına gelir. Doğru tanımla ifade (!(a + b)) olur ve 0 verir. Dış parantez de aynı amaçla konur: makronun sonucu daha büyük bir ifadenin içinde kullanıldığında bütün olarak kalmalıdır.

Global bir dizi ve global bir sayaç basit bir başlangıçtır, ama sınırları vardır. Programda yalnız bir heap olabilir. Kapasite derleme sırasında sabitlenir. Yordamlar hangi diziyle çalıştıklarını parametre olarak almaz. Bu sakıncalar bir yapı kullanılarak giderilebilir. Ama yordamların mantığı en sade biçimde global dizi üzerinde görülür; ekleme ve silme önce bu biçimde yazılır.

13.3Ekleme

Heap'e yeni bir öğe eklenince iki kural birden korunmalıdır. Ağaç tam kalmalı ve her ebeveyn çocuklarından küçük olmamalıdır. Ekleme bu iki kuralı sırayla ele alır: önce şekli, sonra düzeni düzeltir.

13.3.1Önce yer açılır, sonra kaydırılır

Tam ikili ağaca bir düğüm eklenecekse, yeni düğümün nereye geleceği bellidir: son düzeydeki ilk boş konum. Son düzey doluysa yeni bir düzey açılır ve en soldaki konum kullanılır. Dizi gösteriminde bu konumun indisi n + 1'dir. Yeni öğenin yeri bu yüzden kesinlikle hazırdır ve bundan kuşku yoktur. Önce bu konum açılır; ağaç yine tamdır.

Ama yeni öğe ebeveyninden büyük olabilir. O zaman heap özelliği bu ebeveyn–çocuk çiftinde bozulmuştur. Düzeltmek için yeni öğe yukarı doğru, uygun konumuna kaydırılır. Ebeveyni yeni öğeden küçükse ebeveyn bir düzey aşağı iner, yeni öğenin aday konumu bir düzey yukarı çıkar. Bu, yeni öğeden küçük olmayan bir ebeveyne ya da köke ulaşılana kadar sürer. Yukarı doğru bu harekete yukarı kaydırma (up-heap, yukarı süzme) denir.

Şekil 13.6 15'in 14, 12, 7, 10, 8, 6 heap'ine eklenişini beş anda gösterir. Başlangıçta heap'te altı öğe vardır. İlk boş konum 7'dir; bu konum 3. düğümün, yani 7 değerinin sağ çocuğudur. Yeni öğe 15, 7'den büyüktür; bu yüzden 7 bir düzey aşağı, 7. konuma kaydırılır ve boşluk 3. konuma çıkar. 3. konumun ebeveyni kökteki 14'tür. 15 bundan da büyüktür; 14 aşağı, 3. konuma iner ve boşluk 1. konuma, köke çıkar. Kökün ebeveyni yoktur. 15 köke yazılır ve heap özelliği yeniden sağlanır. Son durum 15, 12, 14, 10, 8, 6, 7'dir.

Hareketin yalnız tek bir yol üzerinde olduğuna dikkat edilmelidir. Yeni konumdan köke giden yol 7 → 3 → 1'dir. Heap'in geri kalanına, örneğin 12'nin alt ağacına hiç dokunulmaz. Bu, eklemenin ucuzluğunun kaynağıdır. Yolun uzunluğu ağacın yüksekliği kadardır ve tam ikili ağacın yüksekliği öğe sayısının logaritmasıyla büyür.

Yukarı kaydırma heap özelliğini neden korur? Yol üzerinde aşağı inen her ebeveyn, yeni öğeden küçüktür. İndiği konumun çocukları, eski konumunda zaten onun torunlarıydı; heap özelliği gereği onlardan küçük değildir. Yani aşağı inen ebeveyn yeni yerinde de kurala uyar. Yeni öğe ise durduğu yerde ebeveyninden büyük değildir. Çocuklarından da küçük değildir. Çocuklarından biri, yerinden aşağı kaydırdığı ebeveyndir; öbürü o ebeveynin eski çocuğudur. İkisi de yeni öğeden küçüktür. Böylece ekleme sonunda bütün ebeveyn–çocuk çiftleri yeniden kurala uyar.

13.3.2maksimum_yigin_ekle: takas değil, kaydırma

Sunumdaki ekleme yordamı şöyledir:

void maksimum_yigin_ekle(eleman item) {
  if (YIGIN_DOLUMU(n)) {
    yigin_dolu();             /* hata iletisi */
    return;
  }
  int i = ++n;
  while (i != 1) {            /* i == 1: kökteyiz */
    if (item.x <= yigin[i / 2].x) break;
    yigin[i] = yigin[i / 2];  /* ebeveyni aşağı kaydır */
    i /= 2;                   /* bir üst ebeveyne bak */
  }
  yigin[i] = item;
}

Yordam önce heap'in dolu olup olmadığına bakar. Doluysa yigin_dolu() çağrılır ve ekleme yapılmadan dönülür. yigin_dolu bir hata iletisi yazan basit bir yordamdır; sunumda gövdesi verilmez. Test programlarında standart hata akışına “heap dolu” yazan tek satırlık bir fonksiyon kullanılmıştır.

int i = ++n; satırı iki iş yapar. ++n önce öğe sayısını bir artırır, sonra artmış değeri verir; i bu yüzden ilk boş konumun, yani yeni son konumun indisini alır. Bu satırdan sonra yigin[i]'de henüz anlamlı bir değer yoktur. Yeni öğe hemen oraya yazılmaz, çünkü belki de yeri orası değildir. i, boşluğun o anki konumunu gösterir.

Döngü koşulu i != 1'dir. i 1 olduğunda boşluk köke ulaşmıştır ve kökün ebeveyni yoktur; daha yukarı çıkılamaz. Döngünün ilk satırı yeni öğeyi boşluğun ebeveyniyle karşılaştırır. item.x <= yigin[i / 2].x ise ebeveyn yeterince büyüktür, boşluk yeni öğenin yeridir ve döngü break ile biter. Değilse ebeveyn boşluğa, yani bir düzey aşağı kopyalanır: yigin[i] = yigin[i / 2]. Ardından i /= 2 ile boşluk ebeveynin eski konumuna çıkar. Döngü bittiğinde i yeni öğenin yerini gösterir ve yigin[i] = item öğeyi oraya yazar.

Yordamın adındaki fikir dikkat ister: takas yoktur. Birçok kaynak yukarı kaydırmayı, yeni öğeyi önce sona yazıp sonra ebeveyniyle yer değiştirerek anlatır. Her yer değiştirme bir geçici değişken ve üç atama ister. Buradaki boşluk (delik) yöntemi ise yeni öğeyi yol boyunca taşımaz. Yalnız büyük atalar birer düzey aşağı kaydırılır; her kaydırma tek bir atamadır. Yeni öğe en sonda bir kez yazılır. k düzey çıkan bir eklemede takasla 3k atama yapılırken bu yöntemle k + 1 atama yapılır. Öğe tipi büyük bir yapı olduğunda bu fark daha da önemlidir.

13.3.3Kod izleme: ekle(15)

Tablo 13.2, Şekil 13.6'daki eklemeyi kodun satırlarıyla izler. Satır numaraları sunumdaki izleme slaytına göredir: 2. satır dolu denetimi, 6. satır int i = ++n;, 7. satır döngü koşulu, 8. satır karşılaştırma, 9. satır kaydırma, 10. satır i /= 2, 12. satır son yazmadır. Başlangıçta heap 14, 12, 7, 10, 8, 6, n = 6'dır.

Tablodaki “boşluk” bir gösterim kolaylığıdır. Bellekte o hücre boş değildir; içinde eski değerin bir kopyası durur. yigin[7] = yigin[3] satırından sonra 7 değeri hem 3. hem 7. hücrededir. 3. hücredeki kopya artık anlamsızdır, çünkü bir sonraki adımda üzerine yazılacaktır. İzleme bu yüzden o hücreyi boşluk olarak gösterir. Aynı durum 14 için de olur: yigin[3] = yigin[1]'den sonra 14 iki hücrededir ve kökteki kopya en son satırda 15 ile ezilir.

Döngü iki kez tam döner ve üçüncü denetimde i == 1 olduğu için biter. Toplam iki karşılaştırma, iki kaydırma ve bir son yazma yapılır. Yeni öğe yol üzerinde iki düzey yukarı çıkmıştır. Kökte durması bir rastlantı değildir: 15 heap'teki her değerden büyüktür ve Teorem 13.1 gereği en büyük değer köke çıkmak zorundadır.

13.3.4Kod izleme: ekle(109)

İkinci eklemede heap 15, 12, 14, 10, 8, 6, 7, n = 7'dir ve 109 eklenir. 109 bütün öğelerden büyüktür; bu yüzden bu ekleme en kötü durumdur ve öğe köke kadar çıkacaktır. Son düzey (4, 5, 6, 7) doludur. Bu yüzden yeni konum 8, yeni bir düzeyin ilk konumudur ve 4. düğümün, yani 10'un sol çocuğudur.

Döngü üç kez tam döner: yeni konumdan köke kadar yol 8 → 4 → 2 → 1'dir ve bu yolda üç kenar vardır. Her turda bir karşılaştırma ve bir kaydırma yapılır. Dördüncü denetimde i == 1 olur ve döngü karşılaştırma yapmadan biter. Yolun üzerindeki üç öğe, 10, 12 ve 15, birer düzey aşağı inmiştir. Yolun dışındaki öğeler, 14, 8, 6 ve 7, yerinden kıpırdamamıştır. Bu ekleme 8 öğeli bir heap'te yapılabilecek en büyük işi yapmıştır. 8 öğeli tam ikili ağacın dört düzeyi vardır ve yeni öğe en alt düzeyden köke çıkmıştır.

13.3.5Art arda ekleme

Sunumun ekleme örneği beş değerden oluşur: 14, 12, 7, 10, 8, 6 heap'ine sırasıyla 15, 109, 107, 3 ve 15 eklenir. İlk ikisi yukarıda izlendi. Kalan üç ekleme farklı davranışlar gösterir; Tablo 13.4 her eklemenin yolunu ve sonucunu verir.

107'nin eklenmesinde ilk boş konum 9'dur; ebeveyni 4. konumdaki 12'dir. 107 > 12 olduğu için 12 aşağı, 9. konuma kayar ve boşluk 4'e çıkar. 4'ün ebeveyni 2. konumdaki 15'tir; 107 > 15 olduğu için 15 de aşağı kayar ve boşluk 2'ye çıkar. 2'nin ebeveyni kökteki 109'dur ve 107 ≤ 109'dur. Ebeveyn yeterince büyüktür, döngü durur ve 107 2. konuma yazılır. Bu ekleme köke kadar çıkmadan yolun ortasında durmuştur.

3'ün eklenmesinde yeni konum 10'dur ve ebeveyni 5. konumdaki 8'dir. 3 ≤ 8 olduğu için döngü daha ilk karşılaştırmada break ile biter. Hiç kaydırma yapılmaz ve 3 doğrudan 10. konuma yazılır. Bu, eklemenin en iyi durumudur: bir karşılaştırma ve bir yazma, yani heap ne kadar büyük olursa olsun sabit iş.

Son olarak ikinci 15 eklenir. Yeni konum 11'dir; ebeveyni yine 5. konumdaki 8'dir. 15 > 8 olduğu için 8 aşağı, 11. konuma kayar ve boşluk 5'e çıkar. 5'in ebeveyni 2. konumdaki 107'dir ve 15 ≤ 107'dir. 15, 5. konuma yazılır. Heap'te artık iki tane 15 vardır: biri 4., biri 5. konumda. Bu iki öğe kardeştir ve aralarında sıra kuralı yoktur. Tanımdaki “küçük değilse” ifadesi eşit öncelikli öğelere de izin verir.

Şekil 13.8 bu üç eklemenin sonuçlarını gösterir. Beş eklemedeki kaydırma sayıları 2, 3, 2, 0 ve 1'dir. 3'ün eklenmesi hiç kaydırma yapmamıştır; bu en iyi durumdur ve sabit sürer. 109 ise köke kadar çıkmıştır; bu en kötü durumdur ve yükseklikle orantılı sürer. Aynı yordamın maliyeti, eklenen değerin büyüklüğüne bağlı olarak bu iki uç arasında değişir.

13.3.6Eklemenin maliyeti

Eklemenin maliyeti döngünün tur sayısıyla belirlenir. Her tur sabit iş yapar: bir karşılaştırma, bir kaydırma ve bir bölme. Tur sayısı ise boşluğun kaç düzey yukarı çıktığıdır. Boşluk en alttan köke kadar çıkabilir; o hâlde tur sayısı en çok ağacın yüksekliği kadardır. Geriye tam ikili ağacın yüksekliğini bulmak kalır.

Kanıt. Ağacın düzeyleri 0'dan h'ye kadar numaralansın. 0'dan h − 1'e kadarki düzeyler doludur ve 1 + 2 + … + 2^h−1 = 2^h − 1 düğüm taşır. Son düzeyde en az 1, en çok 2^h düğüm vardır. Bu yüzden 2^h ≤ n ≤ 2^h+1 − 1 < 2^h+1'dir. Logaritma alınınca h ≤ lg n < h + 1, yani h = ⌊lg n⌋ bulunur. Düzey sayısı h + 1'dir. İkinci eşitlik için 2^h < n + 1 ≤ 2^h+1 eşitsizliğinden ⌈lg(n + 1)⌉ = h + 1 çıkar. Kökten en alt düzeydeki bir düğüme giden yolda h kenar vardır. ∎

Dizi gösteriminde bu sonucun basit bir karşılığı vardır. i indisli düğümün düzeyi ⌊lg i⌋'dir ve her i /= 2 düzeyi bir azaltır. n indisinden 1'e inmek için tam ⌊lg n⌋ kez ikiye bölmek gerekir. Örneğin n = 8 için 8 → 4 → 2 → 1 üç bölmedir ve ⌊lg 8⌋ = 3'tür. 109'un eklenmesi tam bu kadar kaydırma yapmıştı.

Tablo 13.5 sonucu toplar. Eklemenin zaman karmaşıklığı O(lg n)'dir; en iyi durumu ise Ω(1)'dir. Burada O üst sınırı, Ω alt sınırı anlatır. Bir işlemin en iyi ve en kötü durumu aynı büyüklükteyse maliyet Θ ile, yani sıkı sınırla yazılır. Eklemede iki uç farklı olduğu için tek bir Θ yazılamaz; en kötü durum ise Θ(lg n)'dir. Ek bellek O(1)'dir: yalnız i değişkeni ve item parametresi kullanılır.

Bu sayıların ölçekte anlamı büyüktür. Bir milyon öğeli bir heap'te ⌊lg 10⁶⌋ = 19'dur; en kötü eklemede bile 19 kaydırma yapılır. Bir milyar öğede bu sayı 29'dur. Öğe sayısı bin kat artarken iş yalnız 10 kaydırma artar.

Rastgele sırada gelen değerlerde ekleme çoğu zaman en kötü duruma hiç yaklaşmaz. Bir deneme, rastgele bir milyon değeri boş bir heap'e tek tek eklemiş ve toplam 1 279 942 kaydırma saymıştır; ekleme başına ortalama 1,3 kaydırma. Aynı sayılar artan sırada, yani her yeni değer öncekilerin hepsinden büyük olacak biçimde eklenince toplam 17 951 445 kaydırma olmuştur. Bu, her eklemenin köke kadar çıktığı en kötü durumdur ve toplam ⌊lg 1⌋ + ⌊lg 2⌋ + … + ⌊lg n⌋'ye eşittir. Rastgele bir değerin büyük olasılıkla yaprak düzeyinde kalmasının nedeni basittir: tam ikili ağaçta düğümlerin yaklaşık yarısı yapraktır, dörtte biri yaprakların bir üstündedir.

13.4Silme

Maksimum heap'ten bir öğe almak, öncelikli kuyruğun asıl işidir. Alınacak öğe bellidir: kökteki en büyük öğe. Onu okumak kolaydır. Zor olan, öğeyi çıkardıktan sonra kalan yapıyı yeniden heap yapmaktır. Silme de eklemede olduğu gibi önce şekli, sonra düzeni düzeltir; ama düzeltme bu kez yukarıdan aşağı doğru yürür.

13.4.1Kök alınır, sondaki öğe yerleştirilir

Kök çıkarılınca ağacın tepesinde bir boşluk oluşur. Ağaç tam kalacaksa öğe sayısı bir azaldığında boşalması gereken konum kök değil, son konumdur, yani n. Bu yüzden son konumdaki öğe yerinden alınır ve ona bir yer aranır. Yer arama kökteki boşluktan başlar.

Sondaki öğe büyük olasılıkla küçük bir değerdir, çünkü bir yapraktır. Kökün iki çocuğundan büyük değilse oraya konamaz. Her adımda üç değere bakılır: boşluğun iki çocuğu ve yerleştirilecek öğe. Üçünün en büyüğü boşluğa gelir. En büyük yerleştirilecek öğeyse yeri bulunmuştur. Değilse büyük çocuk bir düzey yukarı, boşluğa taşınır ve boşluk o çocuğun eski yerine iner. Bu aşağı doğru harekete aşağı kaydırma (down-heap, aşağı süzme) denir. Boşluğun çocuğu kalmadığında da yer bulunmuştur: boşluk bir yapraktır.

Şekil 13.10 bunu 30, 15, 28, 11, 14, 3, 6, 10, 9 heap'i üzerinde gösterir. İlk alınacak öğe kökteki 30'dur. Sondaki öğe 9, 9. konumdan çıkarılır; öğe sayısı 8'e iner. Kökün çocukları 15 ve 28'dir; büyüğü 28'dir. 28 > 9 olduğundan 28 köke çıkar ve boşluk 3. konuma iner. 3. konumun çocukları 6. konumdaki 3 ve 7. konumdaki 6'dır; büyüğü 6'dır. 9 ≥ 6 olduğundan 9 boşluğa, 3. konuma yerleşir. Yeni heap 28, 15, 9, 11, 14, 3, 6, 10'dur.

Büyük çocuğun seçilmesi keyfi değildir. Boşluğa gelen öğe, öbür çocuğun ebeveyni olacaktır. Küçük çocuk yukarı çıksaydı büyük çocuk onun çocuğu olurdu ve heap özelliği hemen bozulurdu. Büyük çocuk yukarı çıktığında ise hem küçük kardeşinden hem kendi eski çocuklarından küçük değildir; heap özelliği korunur.

13.4.2maksimum_yigin_al

Sunum, kitaptaki silme yordamının düzeltilmiş bir sürümünü verir:

bool maksimum_yigin_al(eleman *cikan) {
  if (YIGIN_BOSMU(n)) return false;
  *cikan = yigin[1];          /* kök döndürülecek */
  eleman deger = yigin[n--];  /* yeri aranacak */
  int i = 1, j = 2;
  while (j <= n) {
    if (j < n && yigin[j].x < yigin[j + 1].x) j++;
    if (deger.x >= yigin[j].x) break;
    yigin[i] = yigin[j];      /* çocuğu yukarı al */
    i = j; j *= 2;
  }
  yigin[i] = deger;
  return true;
}

Yordam önce heap'in boş olup olmadığına bakar. Boşsa false döndürür ve hiçbir şeye dokunmaz. Değilse kökteki öğe *cikan'a kopyalanır. cikan, çağıranın değişkenini gösteren bir işaretçidir; *cikan = yigin[1] ataması çağıranın değişkenine yazar. Tanım gereği ilk alınacak öğe dizinin ilk öğesidir.

eleman deger = yigin[n--]; satırı son konumdaki öğeyi deger'e kopyalar ve öğe sayısını bir azaltır. n-- sonek işlecidir: ifade önce n'nin eski değerini verir, sonra n azalır. Yani yigin[9] okunur ve n 8 olur. Bu andan sonra yigin[9] heap'e ait değildir. Tam ağaç bozulmasın diye sondaki öğe çıkarılmıştır ve şimdi ona kökten başlayarak yer aranacaktır.

i deger'in aday konumunu, yani boşluğu gösterir; başta köktür. j i'nin çocuklarını gösterir; başta sol çocuk olan 2'dir. Döngü j <= n olduğu sürece, yani i'nin en az bir çocuğu olduğu sürece döner. Döngünün ilk satırı büyük çocuğu seçer: sağ çocuk varsa ve soldakinden büyükse j bir artırılır. İkinci satır deger'i büyük çocukla karşılaştırır. deger ondan küçük değilse yer bulunmuştur ve döngü break ile biter. Değilse büyük çocuk boşluğa taşınır: yigin[i] = yigin[j]. Son satır boşluğu taşınan çocuğun eski yerine indirir: i = j, ve j'yi onun sol çocuğuna götürür: j *= 2. Döngüden çıkılınca deger boşluğa yazılır ve true döner.

j < n sınamasının işi önemlidir. j sol çocuğu gösterir; sağ çocuk j + 1'dedir. j == n ise sol çocuk heap'in son öğesidir ve sağ çocuk yoktur. Bu durumda yigin[j + 1] heap'e ait değildir. j < n koşulu, yigin[j+1] okunmadan önce sağ çocuğun var olduğunu garanti eder. && işleci kısa devreyle değerlendirildiği için koşul yanlışsa ikinci karşılaştırma hiç yapılmaz.

Sunum bu sürümü “düzeltilmiş” diye adlandırır. Kitaptaki sürüm öğeyi dönüş değeri olarak verir ve boş heap'te return 0; yazar. Dönüş tipi eleman gibi bir yapıysa bu satır derlenmez. Bir tamsayı bir yapıya dönüştürülemez. Bu satır bir test dosyasında denenmiş ve derleyici “returning 'int' from a function with incompatible result type 'eleman'” hatasıyla durmuştur. Önerilen çözüm, arayüzde olduğu gibi, dönüş değerini başarı ya da başarısızlık bildiren bir bool yapmak ve alınan öğeyi işaretçi parametreyle döndürmektir. Böylece boş heap için anlamsız bir öğe uydurmak gerekmez.

Yordam şöyle çağrılır:

eleman e;
if (maksimum_yigin_al(&e))
  printf("alınan: %d\n", e.x);
else
  printf("heap boş\n");

&e, e değişkeninin adresidir. Yordamın içindeki *cikan = yigin[1] ataması bu adrese, yani e'ye yazar. C'de fonksiyon parametreleri değer olarak aktarılır. Bir fonksiyonun çağıranın değişkenini değiştirebilmesi için o değişkenin adresini alması gerekir. İşaretçi parametre burada bunu sağlar.

13.4.3Kod izleme: birinci alma

Tablo 13.6 30, 15, 28, 11, 14, 3, 6, 10, 9 heap'inde ilk maksimum_yigin_al çağrısını satır satır izler. Satır numaraları sunumdaki izleme slaytına göredir: 2. satır boşluk denetimi, 3. satır kökün kopyalanması, 4. satır son öğenin çıkarılması, 6. satır döngü koşulu, 7. satır büyük çocuğun seçimi, 8. satır karşılaştırma, 9. satır taşıma, 10. satır ilerleme, 12. satır son yazmadır.

Döngü iki kez girilmiş, bir kez taşıma yapmış ve ikinci turda break ile bitmiştir. 9 en alta inmeden, 3. konumda yerleşmiştir. Bu bir “araya girme” örneğidir: sondaki öğe, kökten yaprağa giden yolun ortasında yerini bulmuştur. Toplam dört karşılaştırma yapılmıştır: her turda biri çocukları kıyaslamak, biri deger'i büyük çocukla kıyaslamak için. Tur başına iki karşılaştırma, aşağı kaydırmanın ekleme döngüsünden biraz daha pahalı olmasının nedenidir.

Tablonun son sütunundaki parantezli 9 bir inceliği gösterir. n--'den sonra 9. hücre silinmez; içinde 9'un bir kopyası durur. Ama n = 8 olduğu için yordamların hiçbiri o hücreye heap'in parçası olarak bakmaz. Bir sonraki eklemede o hücreye yeni öğe yazılacaktır. C dizisinde “silme” bir hücreyi boşaltmak değil, sınırı çekmektir.

13.4.4Kod izleme: ikinci alma

İkinci çağrıda heap 28, 15, 9, 11, 14, 3, 6, 10, n = 8'dir. Bu kez sondaki öğe, 10, yaprağa kadar inecektir. Tablo 13.7 döngünün turlarını özetler.

İlk turda kökün çocukları 15 ve 9'dur. Sol çocuk sağdakinden küçük olmadığı için j 2'de kalır. 10 < 15 olduğundan 15 köke çıkar ve boşluk 2'ye iner. İkinci turda 2'nin çocukları 11 ve 14'tür; sağdaki büyüktür ve j 5 olur. 10 < 14 olduğundan 14 yukarı çıkar ve boşluk 5'e iner. 5'in sol çocuğu 10. konumda olurdu; ama 10 > n = 7'dir, yani 5. konum bir yapraktır. Döngü koşulu yanlış olur ve 10 boşluğa yazılır. Çağıran 28'i alır; yeni heap 15, 14, 9, 11, 10, 3, 6'dır.

Bu çağrı silmenin en kötü durumudur: sondaki öğe kökten yaprağa kadar inmiştir. 8 öğeli heap'te yaprak düzeyi 2. ya da 3. düzeydir. 10, 7 öğeli heap'in 2. düzeyinde bir yaprakta durmuştur ve iki düzey inmiştir. İki alma birlikte silmenin iki davranışını gösterir: sondaki öğe yolun ortasında araya girebilir ya da en alta kadar inebilir.

13.4.5Heap boşalana dek almak

Heap'ten öğe almaya heap boşalana kadar devam edilirse ne olur? Tablo 13.8 kalan yedi almayı gösterir. Her satırda alınan öğe, o anda kökte olan en büyük öğedir; sondaki öğe aşağı kaydırma ile yeni yerine yerleşir.

Çıkış sırası 30, 28, 15, 14, 11, 10, 9, 6, 3'tür: öğeler azalan sırada çıkmıştır. Bu bir rastlantı değildir. Her alma o anda kalan öğelerin en büyüğünü verir; en büyüklerin art arda alınması da azalan bir sıra üretir. Tablonun bir ayrıntısı da dikkat çeker. 3 değeri art arda beş kez “sondaki öğe” olmuştur. Her seferinde kökten başlayan bir yolculukla yeniden yerleştirilmiştir. Altıncı almada 6 alınınca heap'te yalnız 3 kalır. Yedinci almada 3 hem kök hem son öğedir; deger = yigin[n--] onu alır, n 0 olur, döngüye girilmez ve 3 kullanılmayan 1. hücreye yazılır. Heap boşalmıştır ve sekizinci bir çağrı false döndürür.

Bu gözlem önemli bir algoritmanın fikridir. n öğe bir heap'e konur, sonra n kez kök alınırsa öğeler sıralı çıkar. Bu, heap sort'un fikridir. Her alma O(lg n) sürdüğü için sıralama O(n lg n) sürer. Heap sort'un ek dizi kullanmayan bir sürümü de bu notta yer alır.

13.4.6Silmenin maliyeti

Silmenin maliyeti de döngünün tur sayısıyla belirlenir. Her tur boşluğu bir düzey aşağı indirir ve en çok iki karşılaştırma ile bir taşıma yapar. Boşluk kökten başlar ve en alt düzeyde durmak zorundadır. Teorem 13.2 gereği en çok ⌊lg n⌋ tur yapılır. Silmenin en kötü durumu bu yüzden O(lg n)'dir; karşılaştırma sayısı en çok 2⌊lg n⌋'dir.

Silmede en iyi durum da Ω(1)'dir. Sondaki öğe kökün iki çocuğundan küçük değilse ilk turda yerleşir. Bu, örneğin heap'te iki öğe kalmışken olur: kök alınınca n 1'e iner, j = 2 > n olduğu için döngüye hiç girilmez ve sondaki öğe doğrudan köke yazılır. Aynı öncelikli öğelerin çok olduğu bir heap'te de sondaki öğe çoğu kez hemen yerleşir. Ama farklı değerli büyük bir heap'te sondaki öğe yapraktan geldiği için genellikle küçüktür ve aşağıya, yaprakların yakınına kadar iner. Bu yüzden silme, rastgele verilerde eklemeden farklı olarak ortalamada da en kötü duruma yakın çalışır. Rastgele bir milyon değerle kurulan bir heap'te ilk bin silme ortalama 18,93 tur yapmıştır; ⌊lg 10⁶⌋ = 19'dur. Ek bellek yine O(1)'dir: deger, i ve j.

13.4.7İki hatalı sürüm

Silme yordamı küçük görünür, ama iki satırındaki ayrıntılar doğruluğu belirler. Bu ayrıntıların neden gerektiği, onları bozan iki sürümle görülebilir.

Büyük çocuk yerine ilk çocuk. Döngüden if (j < n && yigin[j].x < yigin[j + 1].x) j++; satırı çıkarılırsa her turda sol çocuk seçilir. 30, 15, 28, 11, 14, 3, 6 heap'inde bu sürümle 30 alınmıştır. Sondaki öğe 6'dır. Sol çocuk 15, 6 < 15 olduğu için köke çıkar; boşluk 2'ye iner, orada sol çocuk 11 yukarı çıkar ve 6, 4. konuma yazılır. Sonuç 15, 11, 28, 6, 14, 3'tür. Kökteki 15, sağ çocuğu 28'den küçüktür; heap özelliği bozulmuştur. Bir sonraki alma en büyük öğe olarak 28'i değil 15'i verir. Program çökmez, yalnız yanlış öğeyi verir.

j < n sınaması olmadan. Bu sınama atlanırsa, j == n olduğunda yigin[n + 1] okunur. Bu hücre heap'in dışındadır. maksimum_yigin_al'da ilginç bir durum vardır: n--'den sonra yigin[n + 1]'de, yeri aranan deger'in kendi kopyası durur. Bu kopya seçilirse karşılaştırma deger.x >= deger.x olur ve döngü doğru yerde durur. Bu yüzden bu yordamda hata sonucu değiştirmez; karışık ekleme ve almalardan oluşan yarım milyon rastgele denemede bile yanlış bir sonuç görülmemiştir. Ama bu bir rastlantıdır ve kodun doğru olduğunu göstermez. Aynı döngü aşağıdan yukarı heap kurmada kullanıldığında a[n + 1] dizinin dışında kalabilir. 6 öğelik bir dizide bu sınama kaldırılınca dizinin hemen arkasındaki 99 değeri heap'e girmiş, dizideki 3 kaybolmuştur. j < n sınaması bu yüzden her aşağı kaydırma döngüsünde yazılmalıdır.

13.5Gerçeklemeyi geliştirmek

Ekleme ve silme yordamları doğru çalışır, ama global bir diziye bağlıdır. Bu kesim yordamları üç yönde geliştirir: heap'i bir yapıya taşımak, minimum heap'i yazmak ve önceliği zamanla değişen öğeleri ele almak.

13.5.1Global dizi yerine yapı

Global dizi ile programda tek bir heap olabilir. Bir işletim sistemi ise birçok kuyruk tutar: her işlemci için ayrı bir hazır kuyruğu, zamanlayıcılar için ayrı bir kuyruk. Kapasite de derleme sırasında sabittir. Sunum bu sakıncaları gidermek için dizi ile öğe sayısını bir yapıda toplar ve diziyi çalışma sırasında ayırır:

typedef struct { eleman *a; int n, kapasite; } Yigin;

Yigin *yigin_olustur(int kapasite) {
  Yigin *h = malloc(sizeof *h);
  if (h == NULL) return NULL;
  h->a = malloc((kapasite + 1) * sizeof *h->a);
  if (h->a == NULL) { free(h); return NULL; }
  h->n = 0; h->kapasite = kapasite;
  return h;
}
void yigin_yok_et(Yigin *h) { if (h) { free(h->a); free(h); } }

Yigin yapısının üç alanı vardır. a, heap bellekte ayrılan dizinin adresidir. n öğe sayısını, kapasite en çok kaç öğe alınabileceğini tutar. Her heap ayrı bir Yigin olduğu için programda istenen sayıda heap bulunabilir. Yordamlar hangi heap üzerinde çalışacaklarını parametre olarak alır.

yigin_olustur iki ayrı blok ayırır. İlki yapının kendisidir: malloc(sizeof *h). Burada sizeof *h, h'nin gösterdiği tipin, yani Yigin'in boyutudur. Tip adını tekrar yazmamak, tip sonradan değişirse satırı doğru tutar. İkinci blok dizidir. 0. hücre kullanılmadığı için kapasite + 1 hücre ayrılır. İki ayırmanın sonucu da denetlenir. İkinci ayırma başarısız olursa yalnız NULL döndürmek yetmez; önce ayrılmış olan yapı da free(h) ile geri verilir. Aksi hâlde o blok kimsenin gösteremediği bir bellek parçası olarak kalır, yani sızar.

yigin_yok_et blokları ayırmanın tersi sırayla bırakır. Önce dizi, sonra yapı bırakılır, çünkü dizinin adresi yapının içindedir; yapı önce bırakılsaydı h->a okunamazdı. if (h) denetimi NULL bir işaretçiyle çağrıyı zararsız yapar. Bu, free(NULL)'ın hiçbir şey yapmamasıyla tutarlı bir davranıştır.

Yapı sürümünün ekleme ve alma yordamları sunumda verilmez; öneri, başarının TRUE/FALSE ile bildirilmesi ve öğenin işaretçiyle aktarılmasıdır. Aşağıdaki iki yordam bu öneriyi uygular. Gövdeleri global sürümlerle aynıdır; yalnız yigin yerine h->a, n yerine h->n yazılır:

bool yigin_ekle(Yigin *h, eleman item) {
  if (h->n == h->kapasite) return false;   /* dolu */
  int i = ++h->n;
  while (i != 1 && item.x > h->a[i / 2].x) {
    h->a[i] = h->a[i / 2];
    i /= 2;
  }
  h->a[i] = item;
  return true;
}

bool yigin_al(Yigin *h, eleman *cikan) {
  if (h->n == 0) return false;             /* boş */
  *cikan = h->a[1];
  eleman deger = h->a[h->n--];
  int i = 1, j = 2;
  while (j <= h->n) {
    if (j < h->n && h->a[j].x < h->a[j + 1].x) j++;
    if (deger.x >= h->a[j].x) break;
    h->a[i] = h->a[j];
    i = j; j *= 2;
  }
  h->a[i] = deger;
  return true;
}

Ekleme yordamında dolu heap artık bir hata iletisiyle değil, false dönüşüyle bildirilir; ne yapılacağına çağıran karar verir. Döngü koşulu da biraz kısalmıştır: i != 1 ve “ebeveyni daha küçük” koşulları tek bir while'da birleşir. && kısa devreyle değerlendirildiği için i == 1 olduğunda h->a[0] hiç okunmaz. İki yazım aynı işi yapar.

Şekil 13.12 bu yapının bellekteki görünümünü çizer. Program yığınında (stack) yalnız h işaretçisi durur. Yapı ve dizi heap bellektedir; yapının a alanı dizinin başlangıç adresini tutar.

Bu sürüm sayaçlı bir malloc/free sarmalayıcısıyla sınanmıştır. Sarmalayıcı, her başarılı ayırmada ve her bırakmada bir sayaç artıran küçük iki fonksiyondur; makrolarla malloc ve free'nin yerine geçirilir. Deneme yigin_olustur(4) ile başlamış ve 20, 5, 30, 10, 40 değerlerini eklemeye çalışmıştır. İlk dört ekleme TRUE, beşincisi FALSE döndürmüştür, çünkü kapasite 4'tür. Ardından heap boşalana dek alınmış ve 30, 20, 10, 5 çıkmıştır. yigin_yok_et'ten sonra sayaçlar 2 ayırma ve 2 bırakma göstermiştir; sızıntı yoktur. yigin_yok_et(NULL) çağrısı da sorunsuz geçmiştir. Bu derleyici yapılandırmasında sizeof(Yigin) 16 bayttır: 8 baytlık işaretçi ve iki 4 baytlık int.

Dizinin kapasitesi, dolunca realloc ile iki katına çıkarılarak sınırsız da yapılabilir. O zaman ekleme hiç false döndürmez; büyütmeye denk gelen tek bir ekleme Θ(n) sürer, ama amortize maliyet değişmez. İki katına büyütmenin toplam kopyalama maliyeti n eklemede 2n'yi aşmaz.

13.5.2Minimum heap

Fotokopi ve havaalanı örnekleri minimum öncelikli kuyruk isterdi. Minimum heap'in yordamları maksimum heap'inkilerden yalnız iki noktada ayrılır: yordamın adı ve karşılaştırmaların yönü. Sunum ekleme yordamını verir:

void minimum_yigin_ekle(eleman item) {
  /* ... dolu denetimi aynı ... */
  int i = ++n;
  while (i != 1) {
    if (item.x >= yigin[i / 2].x) break; /* >= ! */
    yigin[i] = yigin[i / 2];
    i /= 2;
  }
  yigin[i] = item;
}

Tek değişiklik break koşulundadır: item.x <= … yerine item.x >= …. Yeni öğe ebeveyninden küçük olduğu sürece ebeveyn aşağı iner; yeni öğe ebeveyninden küçük değilse yeri bulunmuştur. Kodun ikinci satırındaki yorum, dolu denetiminin maksimum sürümdekiyle aynı olduğunu söyler; kısalık için yazılmamıştır. Test programında bu denetim eklenerek derlenmiştir.

Alma yordamında iki yer değişir: büyük çocuk yerine küçük çocuk seçilir ve durma koşulu tersine döner.

bool minimum_yigin_al(eleman *cikan) {
  if (YIGIN_BOSMU(n)) return false;
  *cikan = yigin[1];
  eleman deger = yigin[n--];
  int i = 1, j = 2;
  while (j <= n) {
    if (j < n && yigin[j].x > yigin[j + 1].x) j++;  /* küçük çocuk */
    if (deger.x <= yigin[j].x) break;               /* <= ! */
    yigin[i] = yigin[j];
    i = j; j *= 2;
  }
  yigin[i] = deger;
  return true;
}

Yordamın adı değiştirilip küçük ve büyük işaretleri de tersine çevrilirse, minimum heap başarıyla yazılmış olur. Tablo 13.9 değişen üç satırı toplar. Bu iki yordam 20, 5, 30, 10, 40 değerleriyle denenmiştir. Eklemelerden sonra dizi sırasıyla 20; 5, 20; 5, 20, 30; 5, 10, 30, 20; 5, 10, 30, 20, 40 olmuştur. Alma çağrıları 5, 10, 20, 30, 40'ı, yani artan sırayı vermiştir.

Karşılaştırmaları ters çevirmenin bir başka yolu, maksimum heap'i hiç değiştirmeden öncelikleri eksiyle çarpmaktır. −x'in en büyüğü x'in en küçüğüdür. Bu hile pratikte kullanılır, ama anahtarın sayı olduğu durumlarla sınırlıdır ve INT_MIN gibi sınır değerlerde taşma riski taşır. Karşılaştırmayı ayrı bir fonksiyona taşımak daha genel bir çözümdür: yordamlar o fonksiyonu çağırır ve hangi tür heap olduğu bu fonksiyonla belirlenir. Standart kütüphanedeki qsort da sıralama yönünü böyle bir karşılaştırma fonksiyonuyla alır.

13.5.3Önceliği değişen öğeler

Havaalanı örneğine geri dönelim. Uçakların yakıtı, kuleye ilk başvurdukları anda bir kez ölçülüp unutulmaz. Her uçağın saniyede harcadığı yakıt farklıdır. Bir uçak bir saniyede 10 galon (37,85 litre) yakıt harcarken, bir başkası 10 galonla belki bir saat uçabilir. Bu yüzden öncelikler zamanla değişir. Sistemde her saniye bir kesme (interrupt) gelir ve yakıtlar güncellenir. Problemi iyi yakalamak, bu değişimi de modele katmayı gerektirir.

Bir öğenin önceliği değişince heap özelliği yalnız o öğenin çevresinde bozulabilir. Maksimum heap'te önceliği artan öğe ebeveyninden büyük olabilir; yukarı kaydırılır. Önceliği azalan öğe çocuklarından küçük olabilir; aşağı kaydırılır. İki işlem de bir kök–yaprak yolu boyunca çalışır ve O(lg n) sürer. Sunum yukarı kaydırma sürümünü verir:

/* k konumundaki öğenin önceliği arttı: yukarı kaydır */
void oncelik_artir(int k, int yeni) {
  eleman e = yigin[k];
  e.x = yeni;
  while (k != 1 && e.x > yigin[k / 2].x) {
    yigin[k] = yigin[k / 2];
    k /= 2;
  }
  yigin[k] = e;
}

Yordam k. konumdaki öğeyi e'ye kopyalar ve önceliğini yeni değere çeker. Ardından ekleme yordamındaki döngünün aynısı çalışır, yalnız başlangıç konumu n + 1 değil k'dır. k != 1 koşulu kökte durur; e.x > yigin[k / 2].x koşulu ebeveyni daha küçük olduğu sürece devam eder. Döngünün sonunda öğe yeni yerine yazılır. Yordam yeni değerin eskisinden büyük olduğunu varsayar. Küçük bir değerle çağrılırsa döngü hiç dönmez ve öğe olduğu yerde küçülür; bu, heap özelliğini aşağı doğru bozabilir.

Öncelik azaldığında aşağı kaydırma gerekir. Bu sürüm sunumda yoktur; silme yordamının döngüsü k. konumdan başlatılarak elde edilir:

/* k konumundaki öğenin önceliği azaldı: aşağı kaydır */
void oncelik_azalt(int k, int yeni) {
  eleman e = yigin[k];
  e.x = yeni;
  int j = 2 * k;
  while (j <= n) {
    if (j < n && yigin[j].x < yigin[j + 1].x) j++;
    if (e.x >= yigin[j].x) break;
    yigin[k] = yigin[j];
    k = j; j *= 2;
  }
  yigin[k] = e;
}

Bu yordamların zor yanı kodları değil, k'yı bilmektir. Kule, yakıtı değişen uçağın adını bilir; heap'teki konumunu bilmez. Heap'te bir öğeyi aramak O(n) sürer, çünkü heap bir arama yapısı değildir. Her güncelleme için arama yapılırsa O(lg n)'lik kaydırmanın kazancı kaybolur. Çözüm, her öğenin heap'teki konumunu ayrı bir indeks tablosunda tutmaktır: örneğin konum[ucak_no]. Heap yordamları bir öğeyi her taşıdığında bu tabloyu da günceller. Öğe yigin[i] = yigin[j] ile taşınıyorsa ardından konum[yigin[i].no] = i yazılır. Böylece konum O(1)'de bulunur ve öncelik değiştirmek gerçekten O(lg n) sürer. Çizge algoritmalarındaki anahtar azaltma (decrease key) işlemi minimum heap'te aynı yolla yapılır.

13.6Diğer yapılarla karşılaştırma

Heap'in iki işlemi de O(lg n) sürer. Bu iyi bir sonuç mudur? Daha basit bir yapı, bir dizi ya da bir liste, aynı işi daha kolay yapamaz mı? Bu kesim beş gerçeklemeyi önce kuramsal maliyetleriyle, sonra sayılarla ve son olarak gerçek bir ölçümle karşılaştırır.

13.6.1Beş gerçeklemenin maliyeti

Tablo 13.10 sunumdaki karşılaştırmayı verir. Satırlar tek tek ele alınabilir.

Sırasız dizi. Yeni öğe dizinin sonuna yazılır: bir atama, Θ(1). En büyük öğeyi almak için önce onu bulmak gerekir. Dizi sırasız olduğu için bütün öğelere bakılır; bu her zaman n − 1 karşılaştırmadır ve Θ(n)'dir. Bulunan öğe çıkarılınca boşluğa sondaki öğe taşınır; kaydırma gerekmez. Alma işlemi bu yüzden tam olarak doğrusal sürer.

Sırasız liste. Bağlı listede yeni öğe başa eklenir: bir düğüm ayrılır ve iki işaretçi güncellenir, Θ(1). En büyüğü bulmak yine bütün düğümleri gezmeyi gerektirir: Θ(n).

Sıralı dizi. Dizi küçükten büyüğe sıralı tutulursa en büyük öğe sondadır ve almak Θ(1)'dir: n bir azaltılır. Ekleme ise pahalıdır. Yeni öğenin yeri ikili aramayla (binsearch) O(lg n)'de bulunur, ama ondan büyük bütün öğeler bir sağa kaydırılmalıdır. Yeni öğe en küçükse n kaydırma yapılır. Yeni öğe en büyükse hiç kaydırma yapılmaz; bu yüzden ekleme O(n)'dir, Θ(n) değil. İkili arama kullanılmayıp yer baştan doğrusal aramayla bulunursa durum değişir. Yeri bulmak için k öğeye bakılır, ardından n − k öğe kaydırılır; toplam her zaman yaklaşık n'dir. O zaman ekleme O(n) değil Θ(n) olur.

Sıralı bağlı liste. Liste büyükten küçüğe sıralı tutulursa en büyük öğe baştadır. Almak, baş düğümü çıkarıp başı güncellemektir: Θ(1). Eklemede yeni öğenin yeri baştan gezilerek bulunur; kaydırma gerekmez, ama bağlı listede ikili arama yapılamaz. Yeni öğe en büyükse başa hemen eklenir, en küçükse bütün liste gezilir. Ekleme bu yüzden O(n)'dir.

Maksimum heap. İki işlem de yalnız bir kök–yaprak yolu üzerinde çalışır: O(lg n).

Tablonun kalıbı açıktır. Basit yapıların her biri işlemlerden birini çok ucuz yapar, ama bunun bedelini öteki işlemde öder. Sırasız yapılar eklemeyi ucuz tutar, çünkü hiçbir düzen korumaz; bedeli, en büyüğü her seferinde yeniden aramaktır. Sıralı yapılar almayı ucuz tutar, çünkü tam bir düzen korur; bedeli, her eklemede bu düzeni yeniden kurmaktır. Heap ikisinin ortasında durur. Tam sıralama yapmaz, yalnız “her ebeveyn çocuklarından büyük” diye zayıf bir düzen korur. Bu düzen en büyüğü kökte tutmaya yeter ve onarılması yalnız bir yol boyunca iş ister.

Akla gelebilecek bir başka fikir, en büyük değeri ayrı bir max değişkeninde tutmaktır. Sırasız diziye ek olarak bu değişken her eklemede güncellenir ve en büyüğe bakmak O(1) olur. Ama en büyük öğe alındığında, yani o uçak indiğinde ne yapılacaktır? Yeni en büyüğü bulmak için yine bütün diziye bakmak gerekir. Bunu önlemek için ikinci en büyüğü, onun için üçüncüyü de tutmak gerekirdi; bu da sıralı bir dizi kullanmaktan farksızdır.

13.6.2Sayılarla: n = 2 000 000

Maliyet tablosu bir sayı üzerinde somutlaşır. n = 2 000 000 öğe olsun ve her temel işlem bir saniye sürsün. Bu varsayım abartılıdır, ama oranları görmeyi kolaylaştırır. lg 2 000 000 ≈ 20,9'dur; yuvarlanarak 21 alınır. 2 milyonun seçilmesinin nedeni de budur: logaritması kolay hesaplanır, çünkü 2²¹ = 2 097 152'dir.

Tablo 13.11 beş yaklaşımı hiç kod yazmadan, yalnız analizle karşılaştırır. İlk dört yapıda işlemlerden biri 2 milyon saniye, yani yaklaşık 23 gün sürer. Heap'te iki işlem de yaklaşık 21 saniyedir. Bir kuyrukta ekleme ve alma aşağı yukarı aynı sayıda yapıldığından, bir ekleme ile bir almanın toplamına bakmak doğru bir ölçüdür. Basit yapılarda bu toplam yaklaşık 2 milyon adım, heap'te 42 adımdır. Heap yaklaşık 48 000 kat hızlıdır. Bir benzetmeyle: heap ile gerçeklenen program yüz bin kez çalıştırıldığında, öteki yapılardan biriyle bir kez çalıştırmaktan daha kısa sürer.

Gerçek bir komut saniye değil, bir mikrosaniyenin küçük bir kesri kadar sürer. Bu yüzden şu itiraz yapılabilir: “Havaalanına yarım saatte bir uçak geliyor; bin uçaklık bir kuyrukta bile en kötü yapı göz açıp kapayıncaya kadar çalışır. Kim anlayacak algoritmanın kötü olduğunu?” Küçük bir problem için bu doğru olabilir. Ama aynı kod bir işletim sisteminin parçası olduğunda, saniyede binlerce kez çağrılır ve aradaki fark sistemin bütününe yayılır. Uzmanlık isteyen işlerde, iş yükü büyüyünce çöken bir çözümün akademik ve bilimsel bir değeri yoktur.

13.6.3Ölçüm

Kuramsal karşılaştırma bir ölçümle de sınanmıştır. Üç gerçekleme C ile yazılmış ve -O2 ile derlenmiştir: sırasız dizi, doğrusal kaydırmalı sıralı dizi ve maksimum heap. Her birine n rastgele değer eklenmiş, ardından n kez en büyük alınmıştır. Üç yapının verdiği değerlerin toplamları her çalıştırmada eşit çıkmıştır; yani üçü de aynı öğeleri vermiştir. Tablo 13.12 üç çalıştırmanın değer aralıklarını verir. Değerler makineye göre değişir; önemli olan büyüme biçimidir.

n on kat artınca sırasız ve sıralı dizinin süresi yaklaşık yüz kat artmıştır. Bu karesel büyümedir: n işlemin her biri Θ(n) sürdüğünde toplam Θ(n²) olur. Heap'in süresi ise kabaca n lg n ile büyür. Yüz bin öğede heap, sırasız diziden yaklaşık 700 kat, sıralı diziden yaklaşık 100 kat hızlıdır. Sıralı dizinin sırasız diziden hızlı çıkması da öğreticidir. İkisi de Θ(n²) toplam iş yapar. Ama kaydırma ardışık bellek hücreleri üzerinde çalışan çok basit bir döngüdür; aynı büyüme sınıfındaki iki yöntem arasında sabit çarpan bu kadar farklı olabilir. Asimptotik sınıf ise sabit çarpandan güçlüdür: n büyüdükçe heap'le aradaki fark açılmaya devam eder.

13.6.4İleri düzey heap'ler

Bu notta anlatılan yapı ikili heap'tir (binary heap). Daha ileri düzeyde başka heap türleri de vardır ve bazı işlemleri daha da hızlı yapar. Araştırmacılar lg n'nin yettiğini düşünmemiştir. Olimpiyat sloganındaki gibi: Citius! Altius! Fortius! (Daha hızlı! Daha yükseğe! Daha güçlü!) Tablo 13.13 üç yapıyı minimum heap işlemleri üzerinden karşılaştırır.

Binomial heap bir ağaç değil, belli boyutlarda ağaçlardan oluşan bir ormandır. Asıl kazancı birleştirmedir: iki binomial heap O(lg n)'de birleştirilebilir. İkili heap'te birleştirme için iki dizi birleştirilip yeniden heap kurulur; bu O(n) sürer. Fibonacci heap işi daha da erteler. Ekleme ve anahtar azaltma sırasında yapıyı düzenlemez; düzenlemeyi en küçüğün silindiği ana bırakır. Sürelerinin amortize olması bu yüzdendir: tek bir işlem pahalı olabilir, ama bir işlem dizisinin toplam maliyeti işlem sayısına bölündüğünde tablodaki değerler çıkar. Dijkstra ve Prim gibi çok sayıda anahtar azaltma yapan çizge algoritmalarında Fibonacci heap kuramsal bir kazanç sağlar. Uygulamada ise ikili heap'in sadeliği ve diziyle önbellek dostu yerleşimi çoğu zaman daha hızlı sonuç verir.

13.7Aşağıdan yukarı heap kurma

Bazen öğeler tek tek gelmez; hepsi baştan bir dizide hazırdır. Örneğin heap sort sıralanacak diziyi bir kerede alır. Böyle bir diziyi heap'e çevirmenin ilk akla gelen yolu, öğeleri boş bir heap'e tek tek eklemektir. Her ekleme O(lg n) sürdüğü için bu yol O(n lg n) sürer. Daha iyi bir yol vardır: diziyi yerinde, aşağıdan yukarı düzeltmek. Bu yönteme aşağıdan yukarı heap kurma (bottom-up heap construction, heapify) denir ve O(n) sürer.

13.7.1yigin_kur

Fikrin çıkış noktası yapraklardır. Tek bir düğümden oluşan ağaç zaten bir heap'tir; karşılaştırılacak çocuğu yoktur. n öğeli bir dizide k > ⌊n/2⌋ olan bütün düğümler yapraktır, çünkü sol çocukları 2k > n konumunda olurdu. Demek ki dizinin ikinci yarısı, daha hiçbir şey yapılmadan, tek öğelik heap'lerden oluşur.

Şimdi k = ⌊n/2⌋'den köke doğru geriye gidilir. Her k için düğümün iki alt ağacı zaten heap'tir, çünkü daha büyük indisli bütün düğümler önceden düzeltilmiştir. Bu durumda yalnız k'daki öğe yerinde olmayabilir. Bu tam olarak silmedeki durumdur: kökte yeri aranan bir öğe ve iki heap. k'daki öğe aşağı kaydırılır ve k köklü alt ağaç bir heap olur. Döngü köke ulaştığında bütün dizi heap'tir.

void yigin_kur(eleman a[], int n) {
  for (int k = n / 2; k >= 1; k--) {
    eleman deger = a[k];
    int i = k, j = 2 * k;
    while (j <= n) {
      if (j < n && a[j].x < a[j + 1].x) j++;
      if (deger.x >= a[j].x) break;
      a[i] = a[j];
      i = j; j *= 2;
    }
    a[i] = deger;
  }
}

Dış döngü k = n / 2'den 1'e kadar geriye sayar. İç kısım maksimum_yigin_al'daki döngünün aynısıdır; tek fark başlangıç konumunun 1 değil k olmasıdır. Horowitz'in kitabında bu iç döngü adjust adlı ayrı bir yordamdır. deger k'daki öğeyi tutar; i boşluğu, j çocukları gösterir. Büyük çocuk deger'den büyük olduğu sürece yukarı taşınır ve boşluk aşağı iner. Sonunda deger boşluğa yazılır.

Yordam ek dizi kullanmaz; heap girdi dizisinin içinde kurulur. Bu yüzden ek belleği O(1)'dir. Böyle algoritmalara yerinde (in-place) algoritma denir. Dizi 1 tabanlıdır: öğeler a[1]'den a[n]'ye kadardır ve a[0] kullanılmaz. Çağıranın en az n + 1 hücrelik bir dizi vermesi gerekir.

13.7.2Kod izleme: yigin_kur(a, 7)

Girdi 5, 3, 8, 9, 1, 12, 7'dir ve henüz heap değildir; kökteki 5, çocuklarından küçüktür. n = 7, ⌊n/2⌋ = 3'tür. 4, 5, 6 ve 7. konumlar yapraktır. Dış döngü 3, 2 ve 1 için çalışır. Tablo 13.14 her k için iç döngüyü özetler.

k = 3'te 8, 12 ile yer değiştirmiş gibi görünür; aslında 12 yukarı taşınmış ve 8 boşluğa yazılmıştır. 3 köklü alt ağaç artık 12, 8, 7'dir. k = 2'de benzer biçimde 9 yukarı çıkar ve 3 yaprağa iner. İki alt ağaç da heap olduktan sonra k = 1'de kök düzeltilir. 5'in yolu bu kez iki düzeydir: önce 12, sonra 8 yukarı taşınır ve 5, 6. konuma yerleşir. Dış döngü k = 0'da biter. Sonuç 12, 9, 8, 3, 1, 5, 7 geçerli bir maksimum heap'tir. Yordam bütünüyle 4 taşıma ve her k için bir son yazma, yani 3 son yazma yapmıştır.

Aynı yedi değer boş bir heap'e maksimum_yigin_ekle ile tek tek eklenseydi sonuç 12, 8, 9, 3, 1, 5, 7 olurdu. Bu da geçerli bir maksimum heap'tir, ama yigin_kur'un verdiğinden farklıdır. Aynı değer kümesi için birden çok heap vardır; iki yöntem farklı birine ulaşır. Hangisinin elde edildiği önemli değildir. İkisinde de kök en büyük öğedir ve sonraki almalar aynı sırayı verir.

13.7.3Neden O(n)?

İlk bakışta yigin_kur'un maliyeti şöyle hesaplanabilir: dış döngü n/2 kez döner, her seferinde iç döngü O(lg n) sürer; toplam O(n lg n). Bu sınır doğrudur ama gevşektir. Asıl gözlem, düğümlerin büyük çoğunluğunun ağacın alt kısmında olması ve oradaki düğümlerin çok az inebilmesidir.

Bir düğüm en çok, altındaki düzey sayısı kadar inebilir. Bu sayıya düğümün yüksekliği denir; yaprakların yüksekliği 0'dır. Düğümlerin yaklaşık yarısı yapraktır ve hiç inmez. Dörtte biri yaprakların hemen üstündedir ve en çok 1 düzey iner. Sekizde biri en çok 2 düzey iner. Yalnız tek bir düğüm, kök, ⌊lg n⌋ düzey inebilir. Şekil 13.14 15 düğümlü bir tam ağaç için bu hesabı yapar: 0 · 8 + 1 · 4 + 2 · 2 + 3 · 1 = 11. Toplam iniş en çok 11'dir ve bu sayı n = 15'ten küçüktür.

Kanıt. n öğeli bir heap'te yüksekliği h olan düğüm sayısı en çok ⌈n / 2^h+1⌉'dir. Yüksekliği h olan bir düğümün aşağı kaydırılması en çok h tur sürer ve her tur sabit iş yapar. Toplam iş şöyle sınırlanır:

Σ_{h ≥ 0} ⌈n / 2^h+1⌉ · O(h) = O(n · Σ_{h ≥ 0} h / 2^h) = O(2n) = O(n)

Burada Σ h / 2^h = 1/2 + 2/4 + 3/8 + … = 2'dir. Bu toplamın değeri şöyle görülür. S = Σ_{h ≥ 1} h / 2^h olsun. S / 2 = Σ_{h ≥ 1} h / 2^h+1 = Σ_{h ≥ 2} (h − 1) / 2^h'dir. Çıkarılınca S − S/2 = 1/2 + Σ_{h ≥ 2} 1/2^h = 1/2 + 1/2 = 1, yani S = 2 bulunur. Tam bir ağaçta daha kesin bir sayım da yapılabilir: 2^m − 1 düğümlü dolu ağaçta toplam iniş en çok n − m'dir, yani n'den azdır. 15 düğümlü örnekte bu 15 − 4 = 11'dir. ∎

Art arda ekleme neden aynı ucuzluğu sağlamaz? Eklemede hareket yukarı doğrudur ve bir düğümün çıkabileceği düzey sayısı onun derinliğidir, yani kökten uzaklığı. Düğümlerin yarısı en alt düzeydedir ve her biri köke kadar ⌊lg n⌋ düzey çıkabilir. Kalabalık olan alt düzeyler en uzun yolu yürüyebilir; toplam Θ(n lg n)'ye ulaşır. Aşağıdan yukarı kurmada durum tersinedir: uzun yolu yalnız az sayıdaki üst düğümler yürür.

İki yöntem bir ölçümle karşılaştırılmıştır. Rastgele dizilerde yigin_kur'un karşılaştırma ve taşıma sayıları sayılmış, aynı değerler bir de tek tek eklenmiştir. Tablo 13.15 sonuçları verir.

yigin_kur'un sayıları n ile tam orantılı büyür: karşılaştırma yaklaşık 1,88n, taşıma yaklaşık 0,74n'dir. Artan sırada eklemede kaydırma sayısı ise n on kat artınca on kattan fazla artar; bin öğede öğe başına 8, on milyonda öğe başına 21 kaydırma düşer. Bu n lg n büyümesidir. Rastgele sırada eklemenin ortalaması öğe başına yaklaşık 1,3 kaydırmada kalır; ama bu ortalama bir garanti değildir. yigin_kur ise her girdide n'den az taşıma yapar. On milyon öğede iki yöntemin süresi de bu makinede 0,1 saniye dolayında ölçülmüştür (yigin_kur 0,09–0,12 s, rastgele ekleme 0,13–0,15 s).

13.8d-ary heap

İkili heap'te her düğümün en çok iki çocuğu vardır. Bu sayı 2 olmak zorunda değildir. Her düğümün en çok d çocuğu olan tam ağaçla da heap kurulabilir.

d-ary heap de dizide saklanır. 0 tabanlı dizide i. düğümün çocukları d · i + 1'den d · i + d'ye kadardır, ebeveyni ⌊(i − 1)/d⌋'dir. d = 2 için bu formüller 0 tabanlı ikili heap'inkilerle aynıdır. Şekil 13.15 bir 3-ary heap'i gösterir. Kök 95'in çocukları 1, 2 ve 3. indislerdeki 60, 80 ve 70'tir. 2. indisteki 80'in çocukları 3 · 2 + 1 = 7'den 9'a kadardır: 75, 40 ve 10. 3. indisteki 70'in yalnız iki çocuğu vardır, 10 ve 11. indislerde: 65 ve 25. Ağaç tamdır; son düzey soldan sağa dolmuştur.

Çocuk sayısı artınca ağaç sığlaşır: yükseklik lg n'den log_d n = lg n / lg d'ye iner. Örneğin bir milyon öğede ikili heap'in yüksekliği 19, 4-ary heap'inki yaklaşık 10'dur. Yukarı kaydırma her düzeyde yalnız bir karşılaştırma yaptığı için ekleme hızlanır. Aşağı kaydırma ise her düzeyde d çocuğun en büyüğünü bulmak zorundadır; bu d − 1 karşılaştırma ister. Kökü silmek bu yüzden O(d · log_d n) sürer ve d büyüdükçe yavaşlar.

Sunumun tablosu maksimum heap'ten söz ettiği için yukarı kaydırma gerektiren işlemi “anahtar artırma” diye adlandırır. Minimum heap'te aynı işlem “anahtar azaltma”dır. Dijkstra'nın en kısa yol algoritması bir minimum heap kullanır ve çok sayıda anahtar azaltma, görece az sayıda silme yapar. Kenar sayısının düğüm sayısına göre çok olduğu yoğun çizgelerde bu oran belirgindir. Böyle durumlarda d > 2 seçmek kazançlıdır. Sığ ağacın bir yararı da önbelleğe dosttur: bir düğümün d çocuğu dizide yan yana durur ve çoğu kez aynı önbellek satırına düşer.

13.9Uygulamalar ve heap sort

Öncelikli kuyruk, “sıradaki en önemli iş hangisi?” sorusunun tekrar tekrar sorulduğu her yerde kullanılır. Sunum altı alan sayar.

• İşletim sistemi. İşlemlerin ve kesmelerin zamanlanması, zamanlayıcı olayları. En yakın zamanda dolacak zamanlayıcı bir minimum heap'in kökündedir.
• Çizge algoritmaları. Dijkstra'nın en kısa yol algoritması ve Prim'in minimum kapsayan ağaç algoritması, her adımda henüz işlenmemiş en yakın düğümü seçer. Bu seçim bir minimum heap'le yapılır.
• Heap sort. Heap kurulur, n kez kök alınır: O(n lg n), yerinde sıralama.
• Olay simülasyonu. Olaylar zaman damgalarına göre bir minimum heap'ten çekilir; her olay gelecekteki yeni olaylar ekleyebilir.
• En büyük ya da en küçük k öğe. Akan bir veride en büyük k öğe, boyutu k olan bir minimum heap'le izlenir. Yeni gelen değer kökten büyükse kök atılır, yeni değer eklenir. Her adım O(lg k), bütün akış O(n lg k) sürer. En küçük k öğe için aynı iş bir maksimum heap'le yapılır.
• Huffman kodlaması. Metin sıkıştırmada en küçük frekanslı iki ağaç art arda birleştirilir. Her adımda en küçük ikisini bulmak bir minimum heap işidir.

Bu uygulamalardan en kısası heap sort'tur ve notta incelenen bütün parçaları bir araya getirir. Art arda almanın azalan sırayı verdiği görülmüştü. Bu fikri ek dizi kullanmadan uygulamak için bir gözlem yeter: kök alındığında heap bir öğe küçülür ve dizinin sonunda bir hücre boşalır. Alınan en büyük öğe tam o hücreye konabilir. Böylece dizinin sonu, sıralanmış öğelerin biriktiği bölge olur. Aşağıdaki yordam bu fikri uygular:

/* a[1..n] küçükten büyüğe sıralanır; ek dizi kullanılmaz */
void heap_sort(eleman a[], int n) {
  yigin_kur(a, n);                 /* O(n) */
  for (int m = n; m > 1; m--) {
    eleman deger = a[m];           /* sondaki öğe */
    a[m] = a[1];                   /* en büyük sona */
    int i = 1, j = 2;              /* a[1..m-1] düzeltilir */
    while (j <= m - 1) {
      if (j < m - 1 && a[j].x < a[j + 1].x) j++;
      if (deger.x >= a[j].x) break;
      a[i] = a[j];
      i = j; j *= 2;
    }
    a[i] = deger;
  }
}

Yordam önce diziyi yigin_kur ile heap'e çevirir. Ardından m, heap'in o anki boyutu olarak n'den 2'ye iner. Her turda sondaki öğe deger'e alınır, kökteki en büyük öğe a[m]'ye yazılır ve deger'e a[1..m-1] içinde kökten başlayarak yer aranır. Bu son kısım maksimum_yigin_al'ın döngüsüdür; yalnız heap'in sonu m - 1'dir. Döngü bittiğinde a[2..n] sıralı ve en küçük öğe a[1]'dedir.

5, 3, 8, 9, 1, 12, 7 dizisi bu yordamla 1, 3, 5, 7, 8, 9, 12'ye sıralanmıştır. Yordam ayrıca 0–149 öğelik, yinelenen değerler içeren 3000 rastgele diziyle sınanmış ve her seferinde artan sıra vermiştir. Maliyet, yigin_kur için O(n) ile n − 1 aşağı kaydırma için O(n lg n)'nin toplamıdır: O(n lg n). Bu süre en kötü durumda da geçerlidir. Ek bellek yalnız birkaç değişkendir: O(1).

13.10Karmaşıklık özeti

Tablo 13.17 notta incelenen işlemleri toplar. Tablonun ortak bir gerekçesi vardır: heap'te iş bir kök–yaprak yolunun uzunluğuyla sınırlıdır ve bu uzunluk Teorem 13.2 gereği ⌊lg n⌋'dir. En büyüğe bakmak yol yürümeyi gerektirmez. Aşağıdan yukarı kurma, yolların çoğu kısa olduğu için doğrusaldır. Arama ise heap özelliğinden yararlanamaz: aranan değer kökten küçükse herhangi bir alt ağaçta olabilir. Ek bellek bütün satırlarda sabittir, çünkü heap dizinin kendisidir ve yordamlar yalnız birkaç indis değişkeni kullanır.

13.11Sık yapılan hatalar

1. 1 tabanlı ve 0 tabanlı formülleri karıştırmak. 1 tabanlı dizide ebeveyn i/2, çocuklar 2i ve 2i+1'dir; 0 tabanlı dizide ebeveyn (i−1)/2, çocuklar 2i+1 ve 2i+2'dir. Karıştırılınca yanlış düğümler karşılaştırılır ve heap sessizce bozulur.
2. Dizi boyutunu kapasiteden bir eksik tanımlamak. eleman yigin[ELEMAN_SAYISI - 1] ile 199. öğe yigin[199]'a, dizinin dışına yazılır.
3. eleman döndüren yordamda return 0; yazmak. Bir tamsayı bir yapıya dönüşmez; derleme hatasıdır. Başarı bool ile, öğe işaretçi parametreyle döndürülür.
4. j < n sınamasını unutup yigin[j+1]'i okumak. Okunan hücre heap'in dışındadır; yigin_kur'da dizinin de dışında olabilir.
5. Silmede büyük çocuk yerine ilk çocuğu seçmek. Küçük çocuk yukarı çıkınca büyük kardeşinin ebeveyni olur ve heap özelliği bozulur.
6. Heap'i sıralı dizi ya da ikili arama ağacı sanmak. Yalnız yigin[1]'in en büyük olduğu garantidir; kardeşler arasında sıra yoktur ve heap'te arama O(n) sürer.
7. Ekleme döngüsünü kökte durdurmamak. Koşul i != 1 yerine i >= 1 yazılırsa yigin[0] okunur ve yeni öğe heap'in dışına yazılabilir.
8. Öncelik değişince öğeyi yanlış yöne kaydırmak. Maksimum heap'te önceliği artan öğe yukarı, azalan öğe aşağı kaydırılır. oncelik_artir'ı küçük bir değerle çağırmak heap'i bozabilir.

13.12Sınav tarzı soru

(i) Beş ekleme Tablo 13.4'te adım adım izlendi. Son dizi 109, 107, 14, 15, 15, 6, 7, 10, 12, 3, 8, n = 11'dir. Sınavda her eklemenin yolunu yazmak yeterlidir: yeni konum n + 1, sonra ebeveyniyle karşılaştırma ve gerekirse ebeveyne çıkış.

(ii) Birinci alma kökteki 109'u verir. Sondaki öğe 11. konumdaki 8'dir; n 10'a iner. Kökün çocukları 107 ve 14'tür; 107 köke çıkar ve boşluk 2'ye iner. 2'nin çocukları 4. ve 5. konumdaki iki 15'tir. Sol çocuk sağdakinden küçük olmadığı için j 4'te kalır; 8 < 15 olduğundan 4. konumdaki 15 yukarı çıkar ve boşluk 4'e iner. 4'ün çocukları 10 ve 12'dir; 12 büyüktür ve 8 < 12'dir, 12 yukarı çıkar ve boşluk 9'a iner. 9'un sol çocuğu 18. konumda olurdu; 18 > 10'dur. 8, 9. konuma yazılır. Dizi 107, 15, 14, 12, 15, 6, 7, 10, 8, 3 olur.

İkinci alma 107'yi verir. Sondaki öğe 10. konumdaki 3'tür; n 9'a iner. Kökün çocukları 15 ve 14'tür; 15 köke çıkar, boşluk 2'ye iner. 2'nin çocukları 12 ve 15'tir; sağdaki büyüktür, 15 yukarı çıkar ve boşluk 5'e iner. 5'in sol çocuğu 10. konumda olurdu ve 10 > 9'dur; 3, 5. konuma yazılır. Alınanlar 109 ve 107'dir; son dizi 15, 15, 14, 12, 3, 6, 7, 10, 8, n = 9'dur.

(iii) 3'ün eklenmesi hiç kaydırma yapmadı: ebeveyni 8'den küçüktü. Bu en iyi durumdur, Ω(1). 109 ise köke kadar çıktı ve 3 kaydırma yaptı; 8 öğeli heap'te bu, yüksekliğe eşit olan en kötü durumdur, O(lg n). Bu çözümdeki bütün diziler, sunumdaki kodları birebir kullanan bir test programının çıktısıyla aynıdır.

13.13Alıştırmalar ve çözümleri

Sunumun altı alıştırması burada çözümleriyle verilir. Çözümlerdeki diziler test programlarıyla doğrulanmıştır.

13.13.1Boş heap'e beş ekleme

Soru. Boş bir maksimum heap'e 20, 5, 30, 10, 40 eklenirse her eklemeden sonra dizi ne olur?

Çözüm. 20 köke yazılır: 20. 5, 2. konuma gelir ve ebeveyni 20'den küçüktür: 20, 5. 30, 3. konuma gelir; ebeveyni 20'den büyük olduğu için 20 aşağı iner ve 30 köke çıkar: 30, 5, 20. 10, 4. konuma gelir; ebeveyni 2. konumdaki 5'ten büyüktür, 5 aşağı iner; yeni ebeveyni 30'dan küçüktür ve 10 2. konumda durur: 30, 10, 20, 5. 40, 5. konuma gelir; ebeveyni 10'dan, sonra 30'dan büyüktür ve köke çıkar: 40, 30, 20, 5, 10.

13.13.2Minimum heap için alma

Soru. maksimum_yigin_al minimum heap için yazılırsa hangi satırlar değişir?

Çözüm. Yordamın adı minimum_yigin_al olur. Çocuk seçiminde küçük çocuk aranır: if (j < n && yigin[j].x > yigin[j + 1].x) j++;. Durma koşulu if (deger.x <= yigin[j].x) break; olur. Geri kalan her şey aynıdır. Tam kod 13.5.2'de verilmiştir.

13.13.3Bin öğeli heap'te ekleme

Soru. n = 1000 öğeli bir heap'te ekleme en çok kaç kaydırma yapar?

Çözüm. 1000 öğeli tam ikili ağacın yüksekliği ⌈lg 1001⌉ = 10 düzeydir: 2⁹ = 512 ≤ 1000 < 1024. Bir yaprak ile kök arasında en çok 9 kenar vardır. Yaprak düzeyinden köke çıkan bir öğe her kenar için bir kaydırma yapar; en çok 9 kaydırma, yani ⌊lg 1000⌋ = 9. Yeni öğe 1001. konuma gelecekse yol 1001 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1'dir ve gerçekten 9 kenardır.

13.13.413. düğümün akrabaları

Soru. 1 tabanlı bir heap'te 13. düğümün ebeveyni ve çocukları hangi indislerdedir?

Çözüm. Ebeveyn ⌊13/2⌋ = 6'dır. Çocuklar 2 · 13 = 26 ve 27'dir; bunlar ancak heap'te yeterince öğe varsa bulunur (sol çocuk için n ≥ 26, sağ çocuk için n ≥ 27). Ayrıntılı hesap Örnek 13.1'dedir.

13.13.5Kurma ile art arda ekleme

Soru. 5, 3, 8, 9, 1, 12, 7 dizisine yigin_kur yerine art arda ekle uygulanırsa sonuç aynı olur mu?

Çözüm. Hayır. yigin_kur 12, 9, 8, 3, 1, 5, 7 verir. Art arda ekleme ise şöyle ilerler: 5; 5, 3; 8, 3, 5; 9, 8, 5, 3; 9, 8, 5, 3, 1; 12, 8, 9, 3, 1, 5; 12, 8, 9, 3, 1, 5, 7. İki sonuç da geçerli maksimum heap'tir, ama farklıdır. Aynı değer kümesinin birden çok heap düzeni vardır.

13.13.6En küçük öğe nerede?

Soru. Bir maksimum heap'te en küçük öğe nerelerde olabilir? Onu bulmanın maliyeti nedir?

Çözüm. Değerler farklıysa en küçük öğe yalnız bir yaprakta olabilir. Çocuğu olan bir düğüm, heap özelliği gereği en az bir değerden, çocuğundan büyüktür; en küçük olamaz. Yapraklar ⌊n/2⌋ + 1'den n'ye kadarki indislerdir. Yinelenen değerler varsa en küçük değer bir iç düğümde de bulunabilir, ama o değerin bir kopyası mutlaka bir yaprakta da vardır. Her iki durumda da yaprakları taramak yeter. Yaklaşık n/2 yaprak vardır ve hepsine bakmak gerekir, çünkü yapraklar arasında hiçbir sıra yoktur. Maliyet Θ(n)'dir. Heap en büyüğü bulmayı O(1) yapar, ama en küçüğü bulmayı hızlandırmaz.

13.14Özet

• Öncelikli kuyruk, ilk alınacak öğenin geliş sırasına göre değil önceliğe göre belirlendiği kuyruktur: maksimum sürümde en yüksek, minimum sürümde en düşük değerli öğe önce alınır.
• Bir soyut veri tipi olarak ekleme, alma ve bakma işlemleri vardır; sırasız ya da sıralı dizi, liste ya da heap ile gerçeklenebilir.
• Heap tam ikili ağaç ile “ebeveyn ≥ çocuk” kuralının birleşimidir. 1 tabanlı dizide ebeveyn i/2, çocuklar 2i ve 2i+1'dir; işaretçiye gerek yoktur.
• Heap ikili arama ağacı değildir; kardeşler arasında sıra yoktur. Yalnız kökün en büyük olduğu garantidir.
• Ekleme: ilk boş konum açılır, büyük atalar birer düzey aşağı kaydırılır, öğe en sonda bir kez yazılır. En iyi durum Ω(1), en kötü durum O(lg n).
• Silme: kök alınır, sondaki öğeye kökten başlayarak yer aranır, büyük çocuklar yukarı alınır: O(lg n). j < n sınaması sağ çocuğun varlığını denetler.
• Tam ikili ağacın yüksekliği ⌊lg n⌋'dir; heap işlemlerinin logaritmik olmasının gerekçesi budur.
• Global dizi yerine yapı kullanmak birden çok heap'e ve çalışma sırasında seçilen kapasiteye izin verir. Minimum heap için karşılaştırmalar ters çevrilir. Önceliği değişen öğe, konumu biliniyorsa O(lg n)'de yukarı ya da aşağı kaydırılır.
• Basit yapılar işlemlerden birini Θ(n)'e iter; heap ikisini de logaritmik tutar. Ölçümde yüz bin öğede heap, sırasız diziden yaklaşık 700 kat hızlı çıkmıştır.
• Aşağıdan yukarı kurma bir diziyi yerinde ve O(n) sürede heap'e çevirir; art arda ekleme en kötü durumda O(n lg n) sürer.
• d-ary heap ağacı sığlaştırır ve eklemeyi hızlandırır; binomial ve Fibonacci heap'leri birleştirme ve anahtar azaltmayı hızlandırır. Heap sort, öncelikli kuyruğun sıralamaya uygulanmasıdır: O(n lg n), yerinde.

13.15Kavram 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
• tam ikili ağaç complete binary tree
• ebeveyn parent
• düzey level
• yükseklik height
• heap heap
• max-heap max-heap
• min-heap min-heap
• ikili arama ağacı binary search tree
• up-heap (yukarı süzme) up-heap
• down-heap (aşağı süzme) down-heap
• aşağıdan yukarıya heap oluşturma bottom-up heap construction (heapify)
• anahtar azaltma decrease key
• Fibonacci heap Fibonacci heap
• heap sort heap sort
• yerinde sıralama in-place sort
• amortize analiz amortized analysis
• önbellek cache
• heap bellek heap memory

13.16Kendini Dene

1. Boş bir maksimum heap'e sırasıyla 4, 9, 2, 7, 11 ekleniyor. Son dizi nedir? Kaç kaydırma yapılır?

   Cevap

   Diziler: 4; 9, 4; 9, 4, 2; 9, 7, 2, 4; 11, 9, 2, 4, 7. Kaydırmalar: 9 için 1 (4 aşağı), 2 için 0, 7 için 1 (4 aşağı), 11 için 2 (7 ve 9 aşağı); toplam 4.

2. 50, 30, 40, 10, 20, 35 heap'inden maksimum_yigin_al bir kez çağrılıyor. Alınan öğe ve yeni dizi nedir?

   Cevap

   50 alınır. Sondaki 35 çıkarılır, n = 5. Kökün çocukları 30 ve 40'tır; 40 köke çıkar ve boşluk 3'e iner. 3'ün sol çocuğu 6. konumda olurdu, ama 6 > 5'tir. 35, 3. konuma yazılır: 40, 30, 35, 10, 20.

3. 100 öğeli 1 tabanlı bir heap'te 37. düğümün ebeveyni, çocukları ve düzeyi nedir?

   Cevap

   Ebeveyn ⌊37/2⌋ = 18, çocuklar 74 ve 75'tir (ikisi de ≤ 100, yani vardır). Düzey ⌊lg 37⌋ = 5'tir, çünkü 32 ≤ 37 < 64'tür.

4. yigin_kur 1, 2, 3, 4, 5, 6, 7 dizisini neye çevirir? Kaç taşıma yapılır?

   Cevap

   k = 3: 3'ün çocukları 6 ve 7; 7 yukarı, 3 aşağı. k = 2: 2'nin çocukları 4 ve 5; 5 yukarı, 2 aşağı. k = 1: kökün çocukları 5 ve 7; 7 yukarı; ardından 6 ve 3 arasından 6 yukarı; 1, 6. konuma iner. Sonuç 7, 5, 6, 4, 2, 1, 3; 4 taşıma.

5. Minimum heap 3, 6, 7, 14, 8, 12, 15'e 2 ekleniyor. Yol ve son dizi nedir?

   Cevap

   Yeni konum 8'dir. Atalar sırasıyla 14 (4. konum), 6 (2. konum) ve 3 (kök); 2 hepsinden küçük olduğu için üçü de aşağı iner. Yol 8 → 4 → 2 → 1, 3 kaydırma. Son dizi 2, 3, 7, 6, 8, 12, 15, 14.

6. Değerleri farklı bir maksimum heap'te ikinci ve üçüncü büyük öğeler hangi indislerde olabilir?

   Cevap

   İkinci büyük öğenin ebeveyni yalnız kök olabilir, çünkü ebeveyni ondan büyük olmalıdır ve ondan büyük tek öğe köktür: indis 2 ya da 3. Üçüncü büyük öğenin ebeveyni kök ya da ikinci büyük öğedir: indis 2, 3 ya da ikinci büyüğün çocukları, yani 4, 5, 6, 7'den biri.

7. 31 öğeli bir maksimum heap'e yeni bir öğe ekleniyor. En çok kaç kaydırma yapılabilir? En az kaç?

   Cevap

   Yeni öğe 32. konuma gelir; bu yeni bir düzeyin ilk konumudur. Yol 32 → 16 → 8 → 4 → 2 → 1, yani en çok ⌊lg 32⌋ = 5 kaydırma. Yeni öğe 16. konumdaki ebeveyninden küçük ya da ona eşitse hiç kaydırma yapılmaz: en az 0.

8. 0 tabanlı bir 3-ary heap'te 5. düğümün ebeveyni ve çocukları hangi indislerdedir?

   Cevap

   Ebeveyn ⌊(5 − 1)/3⌋ = 1'dir. Çocuklar 3 · 5 + 1 = 16, 17 ve 18'dir.

9. Bir öncelikli kuyruğa önce bir milyon öğe eklenecek, sonra yalnız en büyük on öğe alınacaktır. Sırasız dizi mi, heap mi daha uygundur?

   Cevap

   Sırasız dizide bir milyon ekleme ucuzdur (her biri Θ(1)), ama on alma her biri yaklaşık bir milyon karşılaştırma ister: toplam yaklaşık on milyon. Heap'te öğeler önce diziye konup yigin_kur ile n'den az taşımayla heap yapılabilir; on alma yaklaşık 10 · 2 · 19 = 380 karşılaştırma ister. Sırasız dizi toplam yaklaşık 11 milyon, heap yaklaşık 2 milyon adım yapar (kurmada yaklaşık 1,9n karşılaştırma). Heap yine üstündür; ama fark beş kat kadardır, çünkü işin çoğu girişte yapılır. Alma sayısı arttıkça heap'in üstünlüğü büyür.

13.17İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C: heap'lerin, adjust yordamının ve heap sort'un bu notta izlenen kaynağıdır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms, Bölüm 6: heap kurmanın O(n) analizini, heap sort'u ve öncelikli kuyruk işlemlerini kanıtlarıyla verir; Fibonacci heap'lerine ayrılan bölüm amortize sürelerin kaynağıdır.
• R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 9: öncelikli kuyruğun dizi, liste ve heap gerçeklemelerini ve öğeleri indeksle izleyen dolaylı heap'i anlatır.
• J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM 7(6), 1964 ve R. W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM 7(12), 1964: ikili heap'i ve heap sort'u tanıtan, aşağıdan yukarı kurmayı ekleyen iki kısa özgün yayındır.

13.18Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Bölüm 5.6 (Heaps), Bölüm 7 (Heap Sort).
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (CLRS), MIT Press, Bölüm 6 (Heapsort, öncelikli kuyruklar) ve Fibonacci heap'leri bölümü.
3. R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 9 (Priority Queues and Heapsort).
4. J. W. J. Williams, “Algorithm 232: Heapsort”, Communications of the ACM, 7(6), 347–348, 1964.
5. R. W. Floyd, “Algorithm 245: Treesort 3”, Communications of the ACM, 7(12), 701, 1964.

İlgili sayfalar: Bölüm 13 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.