Heap
- Türkçe karşılığı
- öbek
- Okunuşu
- hip
Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.
Kısaca
Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
Heap veri yapısı nedir?
Heap, heap özelliğini sağlayan özel bir ağaç türüdür. Min-heap'te her ebeveyn çocuklarından küçük ya da onlara eşittir, dolayısıyla en küçük öğe her zaman kökte olur; max-heap'te her ebeveyn çocuklarından büyük ya da onlara eşittir, dolayısıyla en büyük öğe kökte olur. En yaygın tür olan ikili heap, tam bir ikili ağaçtır: son seviye hariç her seviye doludur ve son seviye soldan sağa doldurulur.
Ağaç tam olduğu için ikili heap genellikle işaretçi olmadan düz bir dizide saklanır: i indeksindeki öğenin çocukları 2i + 1 ve 2i + 2 konumundadır, ebeveyni ise (i - 1) / 2 konumundadır (aşağı yuvarlanır). Tepedeki öğeyi okumak O(1) sürer. Bir öğe eklemek ya da tepeyi çıkarmak O(log n) sürer; çünkü heap yalnızca kök ile bir yaprak arasındaki tek bir yol boyunca öğeleri takas eder ve bu yol yaklaşık log n seviye uzunluğundadır. Var olan n öğeden bir heap oluşturmak, heapify adlı bir işlemle yalnızca O(n) sürer.
Hastane acil servisini düşünün: hastalar geliş sırasına göre değil aciliyete göre tedavi edilir ve en acil vaka her zaman sıradaki olur. Bir öncelik kuyruğunun yaptığı tam olarak budur ve heap'ler bir tanesini kurmanın standart yoludur. Heap'ler görev zamanlayıcılarda, Dijkstra'nın en kısa yol algoritmasında, büyük bir veri kümesindeki en büyük k öğeyi bulmada, sıralı dosyaları birleştirmede ve O(n log n) sürede sıralayan heap sort'ta kullanılır.
Heap veri yapısının, programların çalışma zamanında nesne ayırdığı ve çöp toplayıcının temizlediği alan olan heap belleğiyle bir ilgisi yoktur; yalnızca adları aynıdır. Heap ayrıca yalnızca kısmen sıralıdır: tepedeki öğeyi garanti eder, ancak gerisi sıralı değildir ve rastgele bir değeri aramak O(n) sürer. Tüm öğelere sıralı biçimde ya da değere göre hızlı aramaya ihtiyacınız varsa dengeli bir ikili arama ağacı daha uygun bir seçimdir.
Önemli noktalar
- Min-heap en küçük öğeyi, max-heap en büyük öğeyi kökte tutar.
- Tepeye bakmak O(1), ekleme ve tepeyi çıkarma O(log n)'dir.
- n öğeden heap oluşturmak O(n) sürer.
- İkili heap genellikle işaretçi olmadan bir dizide saklanır.
- Heap'ler öncelik kuyruklarının standart uygulamasıdır.
Örnek
import heapq
# heapq turns a plain list into a min-heap: the smallest item is at index 0
tasks = []
heapq.heappush(tasks, (3, "write docs")) # push: O(log n)
heapq.heappush(tasks, (1, "fix production bug"))
heapq.heappush(tasks, (2, "review pull request"))
print(tasks[0]) # peek in O(1): (1, 'fix production bug')
# Pop always returns the lowest priority number first: O(log n) each
while tasks:
priority, task = heapq.heappop(tasks)
print(priority, task) # 1, then 2, then 3Sık sorulan sorular
Heap ile ikili arama ağacı arasındaki fark nedir?
İkili arama ağacı tüm değerleri sıralı tutar; bu yüzden herhangi bir değeri hızla bulabilir. Heap yalnızca en küçük ya da en büyük değerin tepede olmasını garanti eder; bu onu öncelik kuyruğu işleri için daha basit ve hızlı yapar ama rastgele değerleri bulmak için yavaştır (O(n)).
Heap veri yapısı heap belleğiyle ilişkili midir?
Hayır. Heap belleği bir programın çalışma zamanında nesne ayırdığı alandır ve bir heap veri yapısı olarak düzenlenmemiştir. İki kavram yalnızca adı paylaşır.
Python'da yerleşik bir heap var mı?
Evet. heapq modülü, heappush() ve heappop() gibi fonksiyonlarla sıradan bir listeyi min-heap'e dönüştürür. Max-heap için sayıların negatiflerini saklayabilirsiniz; Python 3.14 ve sonrası ayrıca heappush_max() gibi fonksiyonlar da sağlar.
İlgili sayfalar
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- Çöp toplamaProgramlamanın Temelleri, s. 9Çöp toplama, dil çalışma zamanının programın artık kullanamadığı verileri bulup bu belleği yeniden kullanıma açtığı otomatik bellek yönetimidir.
- Heap Belleğiİşletim Sistemleri, s. 13Heap belleği, boyutu ya da ömrü önceden bilinmeyen, çalışma zamanında ayrılan ve onu oluşturan fonksiyondan uzun yaşayabilen verilerin tutulduğu bölgedir.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin