Heap ve Priority Queue Nedir? Heap Lab ile Görselleştirin

Heap, en yüksek veya en düşük öncelikli öğeye hızlı erişmek için kullanılan complete binary tree tabanlı bir veri yapısıdır. Priority Queue ise öğeleri geliş sırasına göre değil, önceliklerine göre çıkaran abstract data type’tır. Bu iki kavram sıkça aynı şey gibi anlatılsa da biri representation, diğeri davranış sözleşmesidir.

Websoftik Academy Heap & Priority Queue Lab, aynı heap’i array ve tree görünümünde senkronize eder. Insert, extract, change-key, bottom-up build ve Heap Sort işlemlerinde aktif index’leri, karşılaştırmaları ve invariant’ın nasıl geri kurulduğunu micro-step düzeyinde gösterir.

Binary heap iki koşulu birlikte sağlar. Shape property, ağacın complete binary tree olmasını; heap-order property ise parent ile child arasındaki öncelik ilişkisini tanımlar. Max heap’te her parent child’larından büyük veya eşit, min heap’te küçük veya eşittir.

Heap bir Binary Search Tree değildir. Sol subtree’deki bütün değerlerin root’tan küçük olması gerekmez. Garanti yalnızca parent-child edge’leri için geçerlidir; bu nedenle root optimum öğeyi verirken rastgele bir değeri aramak yine O(n) sürebilir.

Heap & Priority Queue Lab, foundations, array-tree mapping, construction, mutation, priority queue ve Heap Sort modüllerini tek bir öğrenme rotasında birleştirir. Bir array hücresi seçildiğinde karşılık gelen tree node da vurgulanır.

Her trace adımı operation phase, aktif index, karşılaştırılan değerler, swap kararı ve heap invariant sonucunu içerir. Böylece yalnızca son diziyi değil, yapının neden geçici olarak bozulduğunu ve hangi hareketle düzeldiğini açıklayabilirsiniz.

Complete binary tree’nin bütün seviyeleri, son seviye hariç, doludur; son seviye soldan sağa yerleşir. Bu düzen heap yüksekliğini Θ(log n) ile sınırlar. Insert için yeni konum ve extract sonrası root’a taşınacak son öğe belirsiz değildir.

Shape property sayesinde pointer tabanlı node nesnelerine ihtiyaç duyulmaz. Tree, boşluk bırakmayan bir array içinde saklanır. Bu hem bellek locality’sini iyileştirir hem parent ve child ilişkilerini aritmetik formüllere dönüştürür.

Sıfır tabanlı array’de i index’indeki node için parent ⌊(i-1)/2⌋, left child 2i+1, right child 2i+2 olur. Bir tabanlı gösterimde formüller değişir; sınavda kullanılan index modelini baştan kontrol etmek gerekir.

Lab, cursor’ı array üzerinde hareket ettirdiğinizde tree edge’lerini eşzamanlı aydınlatır. Bu eşleme özellikle sift-up ve sift-down sırasında “hangi node nereye gitti?” sorusunu görsel olarak çözer.

Kullanılacak model problem sözleşmesine bağlıdır. Dijkstra’da en küçük tentative distance için min-priority queue; top-k smallest gibi bazı problemlerde sınırı tutmak için max heap kullanılabilir.

Yeni öğe shape property’yi korumak için array’in sonuna eklenir. Max heap’te parent’tan büyükse, min heap’te parent’tan küçükse swap edilir. Bu süreç root’a ulaşana veya parent-child ilişkisi düzelene kadar sürer.

Her swap bir seviye yukarı çıktığından insert maliyeti O(log n)’dir. Best case’te yeni öğe ilk parent ile uyumluysa yalnızca bir kontrol gerekir. Lab, candidate path’i tree üzerinde ayrı renkle göstererek worst-case yüksekliğini somutlaştırır.

Extract-min veya extract-max root’u çıkarır. Son array öğesi root’a taşınır, heap size bir azaltılır ve doğru child ile swap edilerek aşağı indirilir. Max heap’te iki child arasından daha büyük, min heap’te daha küçük olan seçilmelidir.

Yanlış child ile swap yapmak local ilişkiyi düzeltse bile diğer edge’de invariant’ı bozabilir. Lab iki child karşılaştırmasını, winner child’ı ve durma koşulunu ayrı micro-step’ler olarak gösterir. Toplam maliyet O(log n)’dir.

Bir array’i heap’e dönüştürmek için her öğeyi tek tek insert etmek O(n log n) üst sınırı verir. Bottom-up yöntem son internal node’dan root’a doğru sift-down uygular ve O(n) zamanda heap kurar.

Bunun nedeni bütün node’ların tam yükseklik kadar hareket etmemesidir. Node’ların yaklaşık yarısı leaf’tir ve hiç sift-down yapmaz; çeyreği yalnızca bir, sekizde biri iki seviye hareket edebilir. Ağırlıklı toplam lineer kalır. Lab, her seviyenin gerçek karşılaştırma katkısını ayrı sayaçta toplar.

Priority Queue; insert, peek ve extract-highest-priority işlemlerini sunar. FIFO queue’dan farklı olarak önce gelen öğe değil, priority değeri belirleyici olur. Heap bu sözleşmenin yaygın ve verimli implementation’ıdır.

CPU scheduling, event simulation, network routing, Dijkstra ve Prim gibi algoritmalar priority queue kullanır. Eşit priority durumunda stable ordering gerekiyorsa öğeye monoton artan arrival index eklemek gibi bir tie-break politikası tanımlanmalıdır.

Bir key’in priority’si değiştiğinde hareket yönü yeni değere bağlıdır. Max heap’te değer büyüdüyse sift-up, küçüldüyse sift-down gerekir. Dijkstra’daki decrease-key işlemi min heap üzerinde node’u yukarı taşır.

Rastgele index silmede öğe son değerle değiştirilir, heap size azaltılır ve local ilişkiye göre doğru yönde repair yapılır. Node’un array index’ini hızlı bulmak gerekiyorsa ayrıca id-to-index map tutulması gerekir; aksi hâlde arama O(n) olur.

Artan sıralama için önce max heap kurulur. Root’taki maksimum değer array’in son aktif konumuyla swap edilir, heap size küçültülür ve yeni root sift-down ile düzeltilir. Her turda sorted suffix bir öğe büyür.

Heap Sort worst-case O(n log n), in-place ve comparison-based’dir; ancak stable değildir. Sorting ailelerini karşılaştırmak için Sorting Algorithms Lab rehberine geçebilirsiniz.

“Hangisi daha iyi?” sorusunun tek cevabı yoktur. Operasyon dağılımı ve gereken ordering garantisi seçimi belirler. BST invariant’larını Trees & BST rehberinde karşılaştırabilirsiniz.

Complexity’yi yalnızca tabloda ezberlemek yerine hareket edilen tree yüksekliği ve yapılan karşılaştırma sayısıyla ilişkilendirin. Büyüme analizlerini ayrıca Complexity Lab’de deneyebilirsiniz.

Heap & Priority Queue Lab’i açın ve array ile tree’yi aynı trace üzerinde okuyun. Ardından heap’in Huffman ve greedy tasarımındaki rolünü görmek için Greedy Optimization rehberine geçin.