Heap (Öncelik Kuyruğu)

#Nasıl çalışır?

Heap (yığın ağacı), en küçük (min-heap) ya da en büyük (max-heap) elemana her zaman anında erişim sağlayan bir ağaçtır. Min-heap kuralı: her ebeveyn çocuklarından küçük ya da eşittir; bu yüzden en küçük eleman köktedir.

Heap tam ikili ağaçtır: seviyeler soldan sağa boşluksuz dolar. Bu sayede işaretçiye gerek kalmadan bir dizide saklanır: i'inci elemanın çocukları 2i + 1 ve 2i + 2, ebeveyni (i - 1) / 2 indeksindedir.

Ekleme yeni elemanı sona koyup ebeveyninden küçük olduğu sürece yukarı taşır (sift up). En küçüğü çıkarma ise son elemanı köke taşıyıp çocuklarından büyük olduğu sürece aşağı indirir (sift down). Heap, sıralama değil, yalnızca "en küçük kim?" sorusuna hızlı cevap verir.

#Kendin dene

#Temel işlemler

insert(x)

x'i dizinin sonuna ekler, sonra ebeveyniyle yer değiştirerek yukarı taşır.

extractMin()

Kökü çıkarır, son elemanı köke koyar ve küçük çocuğuyla yer değiştirerek aşağı indirir.

peek()

Kökteki en küçük elemanı çıkarmadan okur.

heapify

Rastgele bir diziyi O(n) sürede heap'e dönüştürür.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

class MinHeap:
    """Min-heap in a list: the children of i are 2i + 1 and 2i + 2, its parent is (i - 1) // 2."""

    def __init__(self) -> None:
        self.items: list[int] = []

    def push(self, value: int) -> None:
        a = self.items
        a.append(value)
        i = len(a) - 1
        # Sift up: swap with the parent while smaller.
        while i > 0 and a[(i - 1) // 2] > a[i]:
            a[i], a[(i - 1) // 2] = a[(i - 1) // 2], a[i]
            i = (i - 1) // 2

    def pop(self) -> int:
        a = self.items
        if not a:
            raise IndexError("heap is empty")
        smallest_value = a[0]
        last = a.pop()
        if a:
            a[0] = last  # move the last element to the root
            # Sift down: swap with the smaller child while a child is smaller.
            i = 0
            while True:
                left, right, smallest = 2 * i + 1, 2 * i + 2, i
                if left < len(a) and a[left] < a[smallest]:
                    smallest = left
                if right < len(a) and a[right] < a[smallest]:
                    smallest = right
                if smallest == i:
                    break
                a[i], a[smallest] = a[smallest], a[i]
                i = smallest
        return smallest_value

    def __len__(self) -> int:
        return len(self.items)


heap = MinHeap()
for v in (5, 3, 8, 1, 9, 2):
    heap.push(v)
# Popping repeatedly yields the values in ascending order.
print(*[heap.pop() for _ in range(len(heap))])

#Karmaşıklık

Heap her zaman tam ağaç olduğu için yüksekliği log₂ n'dir; sift up ve sift down en fazla bu kadar adım sürer. Heap kardeşler arasında sıra tutmaz, bu yüzden rastgele bir değeri aramak O(n)'dir. n elemanı tek tek extractMin ile çıkarmak O(n log n) süren heap sort algoritmasını verir.

#Ne zaman kullanılır?

Öncelik kuyruklarının (priority queue) standart gerçeklemesidir: işletim sistemi görev zamanlama, Dijkstra ve Prim algoritmaları, olay simülasyonları, "en büyük k eleman" ve akan veride ortanca bulma problemleri. Python'da heapq, Java'da PriorityQueue heap kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Dijkstra Algoritması
• Yığın Sıralaması (Heap Sort)
• Huffman Kodlaması