İkili heap: dizi gösterimi, percolate, buildHeap, heapsort

Heap, öncelik kuyruğunun (priority queue) arkasındaki yapıdır: en küçük (ya da en büyük) elemana her an O(1)‘de ulaşırsın, ekleme ve silme O(log n). Ağaç gibi düşünülür ama dizi içinde tutulur, işaretçi yoktur. Sınavda neredeyse hep aynı soru gelir: “Şu sırayla ekle / şu kadar deleteMin yap / buildHeap uygula, son diziyi yaz.” Bu sayfadaki iki kaydırma işlemini (percolate up ve percolate down) doğru yapan biri bu soruları kaçırmaz.

Altın kurallar:

1. Yapı kuralı: heap tam (complete) ikili ağaçtır. Seviyeler soldan sağa doldurulur, boşluk yok.
2. Sıra kuralı (min-heap): her düğüm çocuklarından küçük ya da eşittir. En küçük eleman kökte.
3. Ekleme yukarı, silme aşağı. insert sona koyar ve yukarı kaydırır. deleteMin son elemanı köke koyar ve aşağı kaydırır.
4. Aşağı inerken küçük çocukla yer değiştir. Büyük çocukla değiştirirsen sıra kuralı bozulur.

Dizi gösterimi

Ağaç tam olduğu için düğümleri seviye sırasıyla diziye yazmak yeterli. Bu derste (ve Weiss’te) öncelik kuyruğu heap’i 1. indisten başlar, a[0] boş kalır. O zaman formüller çok temiz olur:

index:  1   2   3   4   5   6   7   8
array: [6, 14,  9, 20, 17, 11, 30, 25]

              6
           /     \
         14       9
        /  \     /  \
      20    17  11   30
     /
   25

25’in indisi 8, ebeveyni 8 / 2 = 4, yani 20. Her ebeveyn çocuklarından küçük: bu bir min-heap. Ama kardeşler arasında (14 ile 9 gibi) bir sıra yok. Heap, BST değildir.

n elemanlı heap’in yüksekliği $\lfloor \log_2 n \rfloor$. 8 eleman için 3.

insert: percolate up

1. Yeni elemanı ilk boş yere (dizinin sonuna, index size + 1) koy.
2. Ebeveyninden küçük olduğu sürece ebeveyniyle yer değiştir.

Yukarıdaki heap’e 8 ekleyelim:

8 index 9'a: ebeveyn a[4]=20 > 8  → yukari
8 index 4'te: ebeveyn a[2]=14 > 8 → yukari
8 index 2'de: ebeveyn a[1]=6 < 8  → dur

[6, 8, 9, 14, 17, 11, 30, 25, 20]

              6
           /     \
          8       9
        /  \     /  \
      14    17  11   30
     /  \
   25    20

En kötü durumda yeni eleman köke kadar çıkar: O(log n).

deleteMin: percolate down

1. Kökteki elemanı (minimum) sakla, döndüreceğiz.
2. Son elemanı köke taşı, boyutu 1 azalt.
3. Kökten başlayarak: iki çocuktan küçük olanı seç. Çocuk taşıdığın değerden küçükse yer değiştir, aşağı in. Değilse dur.

Az önceki 9 elemanlı heap’te deleteMin:

6 cikar, son eleman 20 koke:
[20, 8, 9, 14, 17, 11, 30, 25]
i=1: cocuklar 8, 9   → 8 < 20, degistir
i=2: cocuklar 14, 17 → 14 < 20, degistir
i=4: cocuk 25 (index 8) > 20 → dur

[8, 14, 9, 20, 17, 11, 30, 25]

TUZAK · Silinen elemanın yerine son eleman gelir. Köke “küçük çocuğu çıkarmak” diye bir şey yapılmaz. Önce son eleman köke konur, sonra aşağı kaydırılır. Böylece ağaç tam kalır, boşluk oluşmaz.

buildHeap: O(n) kurulum

Elinde sırasız n eleman varsa iki yol var: n kez insert (O(n log n)) ya da Floyd yöntemi. Floyd: elemanları olduğu gibi diziye koy, sonra son iç düğümden (n/2) köke doğru her düğümde percolateDown çağır. Yapraklar (n/2’den sonrakiler) zaten tek başına heap’tir, onlara dokunulmaz.

[15, 12, 10, 8, 4, 6, 2, 9, 1, 3] için (n = 10, i = 5, 4, 3, 2, 1):

    percDown(5) -> [15, 12, 10, 8, 3, 6, 2, 9, 1, 4]
    percDown(4) -> [15, 12, 10, 1, 3, 6, 2, 9, 8, 4]
    percDown(3) -> [15, 12, 2, 1, 3, 6, 10, 9, 8, 4]
    percDown(2) -> [15, 1, 2, 8, 3, 6, 10, 9, 12, 4]
    percDown(1) -> [1, 3, 2, 8, 4, 6, 10, 9, 12, 15]
  result: [1, 3, 2, 8, 4, 6, 10, 9, 12, 15]  moves=8

Son adımda 15 kökten en alta (index 10) kadar iner: 1, 3 ve 4 birer seviye yukarı çıkar.

Neden O(n)? percolateDown bir düğümde en fazla o düğümün yüksekliği kadar iş yapar. Düğümlerin yarısı yaprak (iş 0), çeyreği yükseklik 1, sekizde biri yükseklik 2, … Toplam:

$\sum_{h} \frac{n}{2^{h+1}} \cdot h \;\le\; n \sum_{h \ge 1} \frac{h}{2^{h+1}} = n$

Yani iş düğümlerin çoğunun bulunduğu altta az, düğümlerin az olduğu üstte çok. Ortalama sabit, toplam O(n). insert ile kurarken tersi olur: elemanların çoğu altta ve her biri köke kadar çıkabilir.

Java’da MinHeap

public class MinHeap {
    private int[] array = new int[11];   // array[0] kullanilmaz
    private int size = 0;

    public void insert(int x) {
        if (size + 1 == array.length)
            array = java.util.Arrays.copyOf(array, array.length * 2);
        int hole = ++size;
        while (hole > 1 && x < array[hole / 2]) {
            array[hole] = array[hole / 2];   // ebeveyni asagi al
            hole /= 2;
        }
        array[hole] = x;
    }

    public int findMin() { return array[1]; }

    public int deleteMin() {
        if (size == 0) throw new RuntimeException("empty heap");
        int min = array[1];
        array[1] = array[size--];            // son eleman koke
        percolateDown(1);
        return min;
    }

    private void percolateDown(int hole) {
        int tmp = array[hole];
        while (hole * 2 <= size) {
            int child = hole * 2;
            if (child != size && array[child + 1] < array[child]) child++;
            if (array[child] < tmp) array[hole] = array[child];
            else break;
            hole = child;
        }
        array[hole] = tmp;
    }

    public void buildHeap(int[] items) {
        array = new int[items.length + 1];
        size = items.length;
        for (int i = 0; i < items.length; i++) array[i + 1] = items[i];
        for (int i = size / 2; i > 0; i--) percolateDown(i);
    }

    public String toString() {           // array[1..size]
        return java.util.Arrays.toString(
            java.util.Arrays.copyOfRange(array, 1, size + 1));
    }
}

Kod değerleri her adımda takas etmez. Bir “delik” (hole) gezdirir ve elemanı en sonda bir kez yerine yazar. Takas 3 atama, delik kaydırma 1 atama yapar.

MinHeap h = new MinHeap();
for (int x : new int[]{6, 14, 9, 20, 17, 11, 30, 25}) h.insert(x);
h.insert(8);
System.out.println("+8 -> " + h);
System.out.println("deleteMin = " + h.deleteMin() + " -> " + h);

+8 -> [6, 8, 9, 14, 17, 11, 30, 25, 20]
deleteMin = 6 -> [8, 14, 9, 20, 17, 11, 30, 25]

Heapsort

Heap ile sıralama: diziyi max-heap yap, sonra en büyüğü (kök) sona taşı ve heap’i bir küçült. Ek dizi gerekmez. Heapsort’ta dizi 0. indisten başlar (sıralanacak dizi zaten böyle), çocuklar 2i + 1 ve 2i + 2.

1. buildMaxHeap: i = n/2 - 1’den 0’a, her birinde (max için) percolateDown.
2. n - 1 kez: a[0] ile heap’in son elemanını takasla, heap boyunu 1 azalt, a[0]‘ı aşağı kaydır.

[4, 10, 3, 5, 1] için:

== heapsort [4, 10, 3, 5, 1]
  after buildMaxHeap: [10, 5, 3, 4, 1]
  after deleteMax #1: [5, 4, 3, 1, 10]  (heap part size 4)
  after deleteMax #2: [4, 1, 3, 5, 10]  (heap part size 3)
  after deleteMax #3: [3, 1, 4, 5, 10]  (heap part size 2)
  after deleteMax #4: [1, 3, 4, 5, 10]  (heap part size 1)

Her adımda dizinin sağında sıralı kısım bir büyür. buildMaxHeap: i=1 (10) çocukları 5, 1’den büyük, değişmez; i=0 (4) çocukları 10, 3, büyüğü 10 yukarı, 4 index 1’de çocukları 5, 1, büyüğü 5 yukarı. Sonuç [10, 5, 3, 4, 1].

Sık yapılan hatalar

private void percolateDown(int hole) {
    int tmp = array[hole];
    while (hole * 2 <= size) {            // en az sol cocuk var
        int child = hole * 2;
        if (child != size && array[child + 1] < array[child])
            child++;                       // kucuk cocugu sec
        if (array[child] < tmp)
            array[hole] = array[child];    // cocuk yukari
        else
            break;
        hole = child;
    }
    array[hole] = tmp;
}