Heap ve Priority Queue: C# ile Binary Heap, Heapify, Heap Sort ve Top-K

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Kargo servisi siparişleri önceliğe göre işliyor. Sabah sekiz sipariş geliyor, hepsi aynı öncelikte (1), sırayla A1'den A8'e. .NET'in PriorityQueue'suna atıp sırayla çekiyoruz:

PriorityQueue<string, int> orders = new();
string[] ids = ["A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8"];
foreach (string id in ids) orders.Enqueue(id, 1);
List<string> plain = [];
while (orders.TryDequeue(out string? id, out _)) plain.Add(id);
Console.WriteLine($"same priority:      {string.Join(" ", plain)}");

Adı "queue" olduğuna göre geliş sırası korunur, değil mi? A1 A2 A3 ... A8 mi çıkar, yoksa başka bir sıra mı? Cevabı yazının ortasında, heap'in nasıl çalıştığını gördükten sonra veriyorum.

Heap Nedir: Tek Kuralı Olan Bir Tree

Binary heap, her node'un iki child'ından küçük ya da eşit olduğu (min-heap) ve her seviyesi soldan sağa dolu olan bir binary tree'dir. Kuralın tek garantisi şu: en küçük eleman köktedir. Kardeşler arasında, ya da sol subtree ile sağ subtree arasında hiçbir sıra yoktur. Bir önceki yazıdaki balanced tree bütün sıralamayı korurken heap yalnız "tepedekini" korur ve bu gevşeklik onu hem daha basit hem daha hızlı yapar.

"Her seviye soldan sağa dolu" şartı (complete tree) sayesinde heap'i pointer'larla değil düz bir array'le tutabiliriz. Kök index 0'da durur; index i'deki node'un child'ları 2i + 1 ve 2i + 2'de, parent'ı (i - 1) / 2'dedir. Node object'i yok, child referansı yok, sadece aritmetik:

Bu yüzden heap bellek açısından çok verimlidir: n eleman için n slot'luk bir array. Elemanlar ardışık durduğu için CPU (Central Processing Unit) cache'i de mutludur; serinin 3. yazısında linked list'in neden kaybettiğini görmüştük, heap tam tersi tarafta.

Sift Up ve Sift Down

Heap'in iki temel hareketi var. Insert'te yeni eleman array'in sonuna eklenir ve parent'ından küçük olduğu sürece yukarı kayar (sift up). En küçüğü çıkarırken kökü alırız, son elemanı köke taşırız ve child'larından büyük olduğu sürece küçük olan child'la yer değiştirerek aşağı iner (sift down). Her ikisi de en fazla tree yüksekliği kadar adım atar: O(log n).

public sealed class BinaryHeap<T>
{
    private T[] _items;
    private readonly IComparer<T> _comparer;

    public BinaryHeap(IComparer<T>? comparer = null)
    {
        _items = new T[4];
        _comparer = comparer ?? Comparer<T>.Default;
    }

    public int Count { get; private set; }

    public T Peek() => Count > 0 ? _items[0] : throw new InvalidOperationException("Heap is empty.");

    public void Push(T item)
    {
        if (Count == _items.Length)
        {
            Array.Resize(ref _items, _items.Length * 2);
        }

        _items[Count] = item;
        SiftUp(Count);
        Count++;
    }

    public T Pop()
    {
        T top = Peek();
        Count--;
        _items[0] = _items[Count];
        _items[Count] = default!; // referans tipte GC'nin object'i toplayabilmesi için
        if (Count > 0)
        {
            SiftDown(0);
        }

        return top;
    }

    private void SiftUp(int index)
    {
        T item = _items[index];
        while (index > 0)
        {
            int parent = (index - 1) / 2;
            if (_comparer.Compare(item, _items[parent]) >= 0)
            {
                break;
            }

            _items[index] = _items[parent]; // parent'ı aşağı kaydır, swap yok
            index = parent;
        }

        _items[index] = item;
    }

    private void SiftDown(int index)
    {
        T item = _items[index];
        while (true)
        {
            int child = 2 * index + 1;
            if (child >= Count)
            {
                break;
            }

            if (child + 1 < Count && _comparer.Compare(_items[child + 1], _items[child]) < 0)
            {
                child++; // küçük olan child
            }

            if (_comparer.Compare(_items[child], item) >= 0)
            {
                break;
            }

            _items[index] = _items[child];
            index = child;
        }

        _items[index] = item;
    }
}

İki küçük detay performansı etkiler. Birincisi, her adımda swap yapmak yerine taşınan elemanı bir değişkende tutup "boşluğu" kaydırıyoruz; her seviyede üç yerine bir atama. İkincisi, Pop'ta boşalan slot'u default'a çekiyoruz; serinin 2. yazısındaki dynamic array'de gördüğümüz gibi, aksi halde referans tipli elemanlar GC (Garbage Collector) tarafından toplanamaz. Max-heap için ayrı bir class yazmaya gerek yok, ters comparer yeterli: Comparer<int>.Create((a, b) => b.CompareTo(a)).

Build-Heap Neden O(n)

Elinde zaten bir array varsa, elemanları tek tek Push etmek n log n'lik iş gibi görünür. Daha iyisi var: array'i olduğu gibi heap kabul edip son iç node'dan köke doğru her node'a sift down uygulamak (bottom-up build-heap, Floyd'un yöntemi):

public BinaryHeap(IEnumerable<T> items, IComparer<T>? comparer = null)
{
    _items = [.. items];
    _comparer = comparer ?? Comparer<T>.Default;
    Count = _items.Length;
    for (int i = (Count - 2) / 2; i >= 0; i--)
    {
        SiftDown(i);
    }

    if (_items.Length == 0)
    {
        _items = new T[4];
    }
}

Sezgisi şöyle: node'ların yarısı yaprak ve hiç iş yapmaz. Dörtte biri en fazla bir seviye iner, sekizde biri en fazla iki seviye. Pahalı olan, uzun yol yürüyen node'lar azınlıkta; toplam iş n/4·1 + n/8·2 + n/16·3 + ... ≤ n civarında kalır. Push ile kurmada ise durum tam tersi: elemanların yarısı en alt seviyeye eklenir ve en uzun yolu yürüme ihtimali olan onlardır. Bunu sayarak gördüm; karşılaştırma sayan bir comparer ile bir milyon elemanlık heap kurdum:

private sealed class CountingComparer : IComparer<int>
{
    public long Comparisons;
    public int Compare(int x, int y)
    {
        Comparisons++;
        return x.CompareTo(y);
    }
}

n=1,000,000: Push one by one = 2,280,005 comparisons, bottom-up build = 1,880,456 comparisons
descending input: Push = 17,951,445, build = 1,999,974

Rastgele veride fark küçük, çünkü rastgele bir elemanın sift up'ı ortalamada birkaç adımda durur. Ama ters sıralı veride (min-heap için en kötü durum, her yeni eleman köke kadar çıkar) Push ile kurma 18 milyon karşılaştırma yaparken build-heap 2 milyonda kalıyor. Bottom-up kurmanın maliyeti input'tan bağımsız olarak O(n). Analizin ayrıntısını Big-O ve Complexity serisinin "Koddan Time Complexity Çıkarmak" yazısındaki toplam sembolü tekniğiyle yapabilirsin.

Heap Sort

Build-heap ve tekrarlanan "en büyüğü sona koy" adımı bir sıralama algoritması verir. Max-heap kurarız, kökü (en büyüğü) array'in sonuna swap ederiz, heap'i bir küçültüp kökü sift down ederiz:

public static void Sort<T>(Span<T> items, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int n = items.Length;
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        SiftDown(items, i, n, comparer);
    }

    for (int end = n - 1; end > 0; end--)
    {
        (items[0], items[end]) = (items[end], items[0]);
        SiftDown(items, 0, end, comparer);
    }
}

Heap sort'un iki güzel özelliği var: worst case'de bile O(n log n) ve ek bellek O(1), sıralamayı yerinde yapar. İki eksiği de var: stable değil (serinin 8. yazısında stability'nin neden önemli olduğunu görmüştük) ve array'in uzak bölgeleri arasında zıpladığı için cache dostu değil. Bu yüzden .NET'in Array.Sort'u heap sort'u ana algoritma olarak değil, introsort'un emniyet supabı olarak kullanır: quicksort'un recursion derinliği 2·log n'i aşınca heap sort'a geçer. Ayrıntısı serinin 9. yazısında.

.NET PriorityQueue: 4-ary Heap ve FIFO Tuzağı

Şimdi açılıştaki sorunun cevabı:

same priority:      A1 A8 A7 A6 A5 A4 A3 A2

Geliş sırası korunmadı. Bu bir bug değil; Microsoft Learn dokümanı PriorityQueue<TElement, TPriority>'yu array tabanlı bir quaternary (4-ary) min-heap olarak tanımlar ve eşit priority'deki elemanlar için FIFO (First-In-First-Out) garantisi vermediğini açıkça yazar. 4-ary heap'te her node'un dört child'ı vardır; tree daha basık olduğu için sift up daha az seviye yürür, sift down ise her seviyede dört child'ı karşılaştırır. Eşitlik durumunda hangi elemanın yukarı çıkacağı heap'in iç şekline bağlıdır, geliş sırasına değil.

Sıra önemliyse (aynı öncelikteki siparişler geliş sırasıyla işlenmeli) priority'ye bir sıra numarası ekle. Tuple'lar önce ilk alana, eşitse ikinci alana göre karşılaştırılır:

PriorityQueue<string, (int Priority, long Sequence)> fifo = new();
long sequence = 0;
foreach (string id in ids) fifo.Enqueue(id, (1, sequence++));
List<string> stable = [];
while (fifo.TryDequeue(out string? id, out _)) stable.Add(id);
Console.WriteLine($"(priority, seq):    {string.Join(" ", stable)}");

(priority, seq):    A1 A2 A3 A4 A5 A6 A7 A8

İkinci önemli eksik decrease-key: kuyruktaki bir elemanın önceliğini değiştiremezsin. .NET 9 ile gelen Remove(element, out removed, out priority, comparer) var, ama dokümanın dediği gibi bütün heap'i doğrusal tarar, yani O(n). Pratik çözüm lazy deletion: yeni öncelikle elemanı bir kez daha ekle, eskisi kuyruktan çıktığında "bu artık geçersiz" deyip atla. Serinin 17. yazısında Dijkstra'yı tam olarak böyle yazacağız. API'nin (Application Programming Interface) geri kalanını C# Koleksiyonlar serisinin "C# Queue, Stack, LinkedList ve PriorityQueue" yazısında anlattık.

Kullanımlar: Top-K, K-Way Merge ve Running Median

En çok satan 10 kitap. İki milyon satış kaydından kitap başına toplamı çıkardık ve elimizde on binlerce farklı ISBN (International Standard Book Number) var. Hepsini sıralamak O(n log n) iş ve n elemanlık bir buffer ister. Oysa sadece ilk K'yı istiyoruz. Boyutu K ile sınırlı bir min-heap tutarsak, tepedeki eleman "şu ana kadarki en iyi K'nın en zayıfı" olur; yeni gelen ondan iyiyse yer değiştirir:

public static List<(TItem Item, int Score)> TopK<TItem>(IEnumerable<(TItem Item, int Score)> source, int k)
{
    PriorityQueue<TItem, int> heap = new(k);
    foreach ((TItem item, int score) in source)
    {
        if (heap.Count < k)
        {
            heap.Enqueue(item, score);
        }
        else if (heap.TryPeek(out _, out int smallest) && score > smallest)
        {
            heap.DequeueEnqueue(item, score); // en zayıfı at, yenisini ekle: tek sift down
        }
    }

    List<(TItem, int)> result = new(heap.Count);
    while (heap.TryDequeue(out TItem? item, out int score))
    {
        result.Add((item, score));
    }

    result.Reverse();
    return result;
}

978-000000011  568
978-000000019  555
978-000000017  553
978-000000004  535
978-000000065  534

Maliyet O(n log k) ve bellek O(k). K = 5 iken log k neredeyse sabit; bu algoritma stream üzerinde de çalışır, veriyi hiç bellekte toplamadan. DequeueEnqueue "çıkar, sonra ekle" işini tek sift down ile yapar.

K sıralı listeyi birleştirmek. Her depo kendi sipariş listesini tarihe göre sıralı gönderiyor ve hepsini tek sıralı akışta birleştirmek istiyoruz. Heap'te her listenin sıradaki elemanı durur; en küçüğü çıkarır, o listenin bir sonrakini ekleriz:

public static IEnumerable<T> MergeSorted<T>(IReadOnlyList<IEnumerable<T>> sources, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    List<IEnumerator<T>> enumerators = [.. sources.Select(s => s.GetEnumerator())];
    try
    {
        PriorityQueue<int, T> heap = new(comparer); // element: hangi listeden geldiği
        for (int i = 0; i < enumerators.Count; i++)
        {
            if (enumerators[i].MoveNext())
            {
                heap.Enqueue(i, enumerators[i].Current);
            }
        }

        while (heap.TryDequeue(out int index, out T? value))
        {
            yield return value;
            if (enumerators[index].MoveNext())
            {
                heap.Enqueue(index, enumerators[index].Current);
            }
        }
    }
    finally
    {
        foreach (IEnumerator<T> e in enumerators) e.Dispose();
    }
}

Toplam n eleman ve k liste için O(n log k). Serinin 8. yazısında bahsettiğimiz external merge sort'un birleştirme adımı da budur: diske yazılmış sıralı parçalar heap ile tek geçişte birleştirilir.

Running median. Kargo teslim sürelerinin medyanını her yeni kayıtta güncel tutmak istiyoruz. Sıralı bir liste tutmak her insert'te O(n) kaydırma demek. İki heap ile O(log n): alt yarı bir max-heap'te, üst yarı bir min-heap'te; iki heap'in boyu en fazla bir farklı olacak şekilde dengelenir ve medyan tepelerden okunur:

public sealed class RunningMedian
{
    private readonly PriorityQueue<int, int> _lower = new(Comparer<int>.Create((a, b) => b.CompareTo(a)));
    private readonly PriorityQueue<int, int> _upper = new();

    public void Add(int value)
    {
        if (_lower.Count == 0 || value <= _lower.Peek())
        {
            _lower.Enqueue(value, value);
        }
        else
        {
            _upper.Enqueue(value, value);
        }

        if (_lower.Count > _upper.Count + 1)
        {
            int moved = _lower.Dequeue();
            _upper.Enqueue(moved, moved);
        }
        else if (_upper.Count > _lower.Count)
        {
            int moved = _upper.Dequeue();
            _lower.Enqueue(moved, moved);
        }
    }

    public double Median => _lower.Count == 0
        ? throw new InvalidOperationException("No values.")
        : _lower.Count > _upper.Count ? _lower.Peek() : (_lower.Peek() + (double)_upper.Peek()) / 2;
}

26->26 30->28 22->26 90->28 24->26 28->27 25->26

90 saatlik gecikmiş kargo ortalamayı bozardı, medyanı ise neredeyse hiç oynatmıyor. Testte her adımda sonucu sıralı listenin ortasıyla karşılaştırıyoruz; heap testlerinin tamamı:

Test run summary: Passed!
  total: 10
  failed: 0
  succeeded: 10
  skipped: 0
  duration: 330ms

Ölçüm: Kendi Heap'imiz, PriorityQueue ve Array.Sort

100.000 rastgele int'i önce ekleyip sonra hepsini çıkardım; ayrıca heap sort'u Array.Sort ile karşılaştırdım (iki sıralama da önce array'in kopyasını alıyor):

[Benchmark(Baseline = true)]
public long PriorityQueue_EnqueueDequeue()
{
    PriorityQueue<int, int> queue = new();
    foreach (int v in _data) queue.Enqueue(v, v);
    long sum = 0;
    while (queue.TryDequeue(out int v, out _)) sum += v;
    return sum;
}

[Benchmark]
public long BinaryHeap_PushPop()
{
    BinaryHeap<int> heap = new();
    foreach (int v in _data) heap.Push(v);
    long sum = 0;
    while (heap.TryPop(out int v)) sum += v;
    return sum;
}

[Benchmark]
public int[] HeapSort_Copy()
{
    int[] copy = [.. _data];
    HeapSort.Sort<int>(copy);
    return copy;
}

[Benchmark]
public int[] ArraySort_Copy()
{
    int[] copy = [.. _data];
    Array.Sort(copy);
    return copy;
}

Ölçümler Apple M5 (10 çekirdek), macOS 27.0.1, .NET 10.0.13, BenchmarkDotNet 0.15.8 ile alındı. Benchmark'ları tek tek çalıştırdım ama makinede paralel işler vardı; mutlak sayılara değil oranlara bak. Ratio sütunu tek baseline'a göre hesaplanıyor, o yüzden ilk iki satırı kendi arasında, son iki satırı kendi arasında oku.

| Method                       | N      | Mean     | Ratio | Allocated  |
|----------------------------- |------- |---------:|------:|-----------:|
| PriorityQueue_EnqueueDequeue | 100000 | 8.211 ms |  1.00 | 2048.69 KB |
| BinaryHeap_PushPop           | 100000 | 6.767 ms |  0.83 | 1024.54 KB |
| HeapSort_Copy                | 100000 | 8.064 ms |  0.98 |  390.72 KB |
| ArraySort_Copy               | 100000 | 3.953 ms |  0.48 |  390.73 KB |

Kendi binary heap'imiz bu senaryoda PriorityQueue'dan yaklaşık %17 hızlı ve yarı bellek kullanıyor. Allocated sütunu farkın bir nedenini gösteriyor: PriorityQueue her slot'ta (element, priority) çiftini tutuyor, biz yalnız değeri. Element ile priority'nin aynı şey olduğu bu özel durumda iki kat veri taşıyor ve iki kat büyüyor (2 MB ile 1 MB). Farkın ne kadarının bundan, ne kadarının 4-ary yapıdan geldiğini ayırmak için d-ary denemesini yazının sonuna bıraktım. Element ve priority farklı olduğunda (sipariş ve tarihi) bu avantaj kaybolur; PriorityQueue ayrıca test edilmiş, EnqueueDequeue gibi optimize işlemleri olan hazır bir yapı. Sıralamada tablo net: heap sort, aynı O(n log n)'e rağmen Array.Sort'un iki katı sürüyor. Introsort'un quicksort'u ardışık bölgelerde çalışırken heap sort index i'den 2i + 1'e zıplıyor ve cache'i sürekli ıskalıyor.

Üretimde Dikkat

PriorityQueue thread-safe değil. Birden çok worker aynı kuyruğa yazıyorsa ya lock kullan ya da önceliği farklı kanallara bölüp Channels ile çalış; C# Asenkron serisinin "C# Senkronizasyon" ve "C# Channels ile Producer/Consumer" yazılarına bak.

Sınırsız büyüme. Bir job scheduler'ın kuyruğu tüketiciden hızlı doluyorsa heap sessizce büyür ve her işlem log n yavaşlar. Kuyruk boyunu metric olarak izle ve bir üst sınır koy; sınır aşılınca yeni işi reddetmek, en düşük öncelikliyi düşürmek ya da üreticiyi yavaşlatmak bir iş kararıdır, kodun içinde gizli kalmamalı.

Priority değeri kuyruktayken değişmemeli. Priority olarak mutable bir object'in property'sini (örneğin siparişin DueDate'i) kullanıyorsan ve bu değer kuyruktayken değişirse heap kuralı bozulur ve çıkış sırası yanlış olur. Priority'yi enqueue anında kopyala (value type kullan) ya da değiştiğinde lazy deletion uygula.

Top-K için tüm listeyi sıralamak. OrderByDescending(x => x.Sales).Take(10) okunaklı ama kaynağın tamamını buffer'a alır. Birkaç bin kayıtta önemi yok; milyonlarca satırlık bir stream'de ya da bellek limiti olan bir container'da size-K heap'i tercih et. Veri veritabanındaysa en iyisi sıralamayı ORDER BY ... LIMIT ile oraya bırakmak.

Sık Düşülen Tuzaklar

Eşit önceliklerde FIFO beklemek. Açılıştaki çıktı bunu gösterdi; aynı önceliğe sahip işler arasında sıra önemliyse sıra numarasını priority'ye ekle ve bunu bir testle sabitle.

Top-K'da yanlış heap. En büyük K'yı bulmak için min-heap gerekir (tepede en zayıf aday dursun), en küçük K için max-heap. Ters seçersen her yeni eleman tepedekiyle karşılaştırılır ama yanlış eleman atılır ve sonuç sessizce bozulur.

Off-by-one index formülleri. 0 tabanlı array'de child'lar 2i + 1 ve 2i + 2, parent (i - 1) / 2. 1 tabanlı kitap formüllerini (2i, 2i + 1, i / 2) 0 tabanlı array'e taşımak kökün ilk child'ını kendisi yapar. Rastgele veriyle "çıkan sıra artan mı" testi bu hatayı hemen yakalar.

Heap'i sıralı sanmak. UnorderedItems'ı ya da kendi array'ini foreach ile gezmek sıralı sonuç vermez; sıralı istiyorsan elemanları tek tek dequeue etmen gerekir.

Küçük Bir Deneme

★☆☆ BinaryHeap<T>'yi max-heap olarak kullanıp bir sipariş listesinden en pahalı üç siparişi bul. Sonra aynı işi PriorityQueue ve ters comparer ile yap.

★★☆ BinaryHeap<T>'yi d-ary yap: child'lar d·i + 1 ile d·i + d arasında, parent (i - 1) / d. d = 2, 4 ve 8 için benchmark'ı tekrar çalıştır. Push ve Pop ayrı ayrı ölçüldüğünde hangisi d büyüdükçe hızlanıyor, hangisi yavaşlıyor?

★★★ Kargo depolarından gelen, her biri tarihe göre sıralı 20 dosyayı (her biri 100.000 satır) MergeSorted ile tek dosyada birleştir; belleği GC.GetGCMemoryInfo() ile izle ve bütün satırları okuyup OrderBy ile sıralayan versiyonla karşılaştır.

Heap ile "en küçük hep tepede" kuralını öğrendik. Bir sonraki yazıda farklı bir soruya geçiyoruz: kullanıcı arama kutusuna "dun" yazdığında, "Dune" ve "Dune Messiah" gibi bu prefix'le başlayan kitapları milisaniyeler içinde nasıl buluruz? Cevap, key'leri karakter karakter saklayan bir tree: trie.