İkili Yığın

Ağaçlar O(log n) O(n)

Dizide saklanan tam ikili ağaç; ekleme bir değeri yukarı süzer, çıkarma son elemanı aşağı indirerek maksimum yığın düzenini korur.

heap array

150

EkleÇıkar

1/33

15 sona ekleniyor (0. indeks).

DeğişmezHer ebeveyn iki çocuğundan da ≥ olduğu için maksimum her zaman köktedir.

mevcutkarşılaştıreklesildöndür

heap.c

void siftUp(int h[], int i) {
    while (i > 0 && h[i] > h[(i - 1) / 2]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}
 
void push(int h[], int *n, int val) {
    h[*n] = val;
    siftUp(h, (*n)++);
}
 
void siftDown(int h[], int n, int i) {
    for (;;) {
        int l = 2*i+1, r = 2*i+2, big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) break;
        swap(&h[i], &h[big]);
        i = big;
    }
}
 
int pop(int h[], int *n) {
    int top = h[0];
    h[0] = h[--(*n)];
    siftDown(h, *n, 0);
    return top;
}

İkili Yığın nasıl çalışır?

Diziye paketlenmiş tam ikili ağaç (i'nin çocukları 2i+1, 2i+2). Push değeri ebeveyni büyük olana dek yukarı süzer; pop son elemanı köke taşıyıp aşağı indirir.

Ne zaman kullanılır?

Öncelik kuyrukları: zamanlayıcılar, Dijkstra/Prim, top-k takibi, heapsort.