Heap ve Öncelik Kuyruğu

Bir hastanenin acil servisini düşün. Hastalar kapıdan geliş sırasına göre değil, durumlarının ciddiyetine göre muayeneye alınır: göğüs ağrısıyla gelen biri, parmağını kesmiş birinden önce içeri girer. Bekleme salonuna sürekli yeni hastalar gelir ve her doktor boşaldığında aynı soru sorulur: "Şu an en acil kim?" Bu soruyu her seferinde salondaki herkese tek tek bakarak yanıtlamak, kalabalık bir günde işleri kilitler.

Yazılımda bu problemin adı öncelik kuyruğudur (priority queue) ve sandığından çok daha sık karşına çıkar: işletim sistemi bir sonraki işi seçerken, Dijkstra algoritması en yakın düğümü ararken, bir zamanlayıcı sıradaki alarmı bulurken ya da milyonlarca kayıt arasından en popüler on ürün seçilirken. Hepsinde ihtiyaç aynıdır: elemanları hızlıca eklemek ve her an en küçük (ya da en büyük) elemanı hızlıca çekip almak.

Bu ihtiyacı en zarif biçimde karşılayan yapı ikili heaptir (binary heap, öbek). Heap, bir ağacı hiç işaretçi kullanmadan düz bir dilime yerleştirir; eklemeyi ve en küçüğü çıkarmayı O(log n), en küçüğe bakmayı O(1) sürede yapar. Bu dersin sonunda heap'in neden çalıştığını diyagramlarla adım adım anlamış, jenerik bir Heap[T] tipini sıfırdan yazmış, Go'nun container/heap paketini doğru kullanmayı öğrenmiş ve top-k ile k sıralı listeyi birleştirme gibi mülakatların gözde problemlerini çözmüş olacaksın.

Öncelik kuyruğu: neye ihtiyacımız var?

Öncelik kuyruğu bir soyut veri tipidir (abstract data type): nasıl gerçekleştirildiğini değil, hangi işlemleri sunduğunu tanımlar.

• Push(x): yeni bir eleman ekler.
• Pop(): en yüksek öncelikli elemanı çıkarır ve döndürür.
• Peek(): en yüksek öncelikli elemana çıkarmadan bakar.
• Len(): eleman sayısını verir.

"En yüksek öncelik", bir min-öncelik kuyruğunda en küçük değer, max-öncelik kuyruğunda en büyük değer demektir. Bu işlemleri daha önce gördüğün yapılarla da gerçekleştirebilirsin, ama her birinin zayıf bir noktası var:

Sırasız dilime eklemek kolaydır ama en küçüğü bulmak için her seferinde bütün dilimi taraman gerekir. Sıralı dilimde (en küçüğü sonda tutarsan) çıkarmak kolaydır ama her eklemede elemanları kaydırmak zorundasın. Dengeli bir ikili arama ağacı (AVL gibi) her işlemi O(log n) yapar; fakat düğüm başına işaretçiler, dönüşler ve epey karmaşık kod ister. Heap ise yalnızca gerçekten istediğimizi yapar: tam sıralama yerine "en küçük her zaman tepede" garantisi verir. Daha az şey vaat ettiği için hem daha basit hem de pratikte daha hızlıdır.

Tam ikili ağaç ve heap özelliği

İkili heap, iki kurala aynı anda uyan bir ikili ağaçtır. Kurallardan biri ağacın şekliyle, diğeri düğümlerdeki değerlerle ilgilidir.

Şekil kuralı: tam ikili ağaç

Tam ikili ağaçta (complete binary tree) son seviye hariç bütün seviyeler doludur; son seviyedeki düğümler de soldan sağa, arada boşluk bırakmadan dizilir. Bu kural sayesinde n düğümlü bir heap'in yüksekliği her zaman ⌊log₂ n⌋ olur: bir milyon elemanlı bir heap'te kökten en derin yaprağa yalnızca 19 adım vardır.

Değer kuralı: heap özelliği

• Min-heap: Her düğümün değeri, çocuklarının değerlerinden küçük veya onlara eşittir. Dolayısıyla en küçük eleman her zaman köktedir.
• Max-heap: Her düğüm çocuklarından büyük veya onlara eşittir; en büyük eleman köktedir.

Tam ikili ağaç                          Tam değil: son seviyede boşluk var

         A                                       A
       /   \                                   /   \
      B     C                                 B     C
     / \   /                                 /     /
    D   E F                                 D     F

Min-heap: ebeveyn ≤ çocuklar            Max-heap: ebeveyn ≥ çocuklar

         2                                       9
       /   \                                   /   \
      5     3                                 6     8
     / \   / \                               / \   /
    9   6 8   4                             5   2 3

Dikkat et: heap özelliği yalnızca ebeveyn ile çocuk arasındaki ilişkiyi tanımlar. Kardeşler arasında ya da farklı dallar arasında hiçbir sıra yoktur. Soldaki min-heap'te 9 sol dalda, 4 sağ dalda aynı seviyede duruyor ve bu tamamen geçerli. Kökten herhangi bir yaprağa giden her yol sıralıdır, ama heap'in bütünü sıralı değildir.

Dizi temsili: ebeveyn ve çocuk indeksleri

Tam ikili ağacın asıl sihri şudur: düğümleri seviye seviye ve soldan sağa numaralandırırsan numaralar arasında hiç boşluk kalmaz. Bu yüzden ağacı işaretçiler olmadan düz bir dilimde saklayabilirsin; ağacın şekli indekslerin aritmetiğinde gizlidir.

                [0]
                 2
              /     \
          [1]         [2]
           5           3
         /   \       /   \
       [3]   [4]   [5]   [6]
        9     6     8     4

 indeks:   0   1   2   3   4   5   6
 dilim:  [ 2 | 5 | 3 | 9 | 6 | 8 | 4 ]
           ^   ^---^   ^---^   ^---^
          kök  0'ın    1'in    2'nin
             çocukları çocukları çocukları

0 tabanlı indekslerde bir düğümün akrabalarını üç basit formülle bulursun:

Formüllerin nereden geldiğini görmek zor değil. Kök 0. seviye olmak üzere, k. seviye 2ᵏ − 1 indeksinden başlar ve 2ᵏ düğüm içerir. Bu seviyede j. sırada duran düğümün indeksi i = 2ᵏ − 1 + j olur. Bir alt seviyede, ondan önceki j düğümün her birinin iki çocuğu vardır; bu yüzden onun sol çocuğu 2ᵏ⁺¹ − 1 + 2j = 2i + 1 indeksine düşer.

Bu temsilin üç büyük avantajı var:

• Düğüm başına işaretçi yoktur; bellek yalnızca değerlerin kendisi kadardır.
• Elemanlar bellekte bitişik durduğu için işlemci önbelleğiyle çok iyi anlaşır (Diziler ve Dinamik Diziler dersini hatırla).
• Sona append yapmak şekil kuralını kendiliğinden korur: yeni eleman her zaman son seviyedeki ilk boş yere düşer.

Yukarı ve aşağı kaydırma

Heap'in bütün işlemleri iki yardımcı hareket üzerine kuruludur. Birinde bir eleman olması gerekenden küçük olduğu için yukarı tırmanır, diğerinde olması gerekenden büyük olduğu için aşağı iner.

Push: sona ekle, yukarı kaydır

Yeni bir eleman eklerken şekil kuralını korumanın tek yolu onu dilimin sonuna koymaktır. Ama bu, değer kuralını bozabilir: yeni eleman ebeveyninden küçük olabilir. Çözüm yukarı kaydırmadır (sift up): eleman ebeveyninden küçük olduğu sürece ikisinin yerini değiştir.

Aşağıda [2 5 3 9 6 8 4] heap'ine 1 ekleniyor:

1) 1'i sona ekle (indeks 7)             2) 1 < 9: yer değiştir (7 ile 3)

         2                                       2
       /   \                                   /   \
      5     3                                 5     3
     / \   / \                               / \   / \
    9   6 8   4                            (1)  6 8   4
   /                                       /
 (1)                                      9

   [2 5 3 9 6 8 4 1]                       [2 5 3 1 6 8 4 9]


3) 1 < 5: yer değiştir (3 ile 1)        4) 1 < 2: yer değiştir, köke ulaştı

         2                                      (1)
       /   \                                   /   \
     (1)    3                                 2     3
     / \   / \                               / \   / \
    5   6 8   4                             5   6 8   4
   /                                       /
  9                                       9

   [2 1 3 5 6 8 4 9]                       [1 2 3 5 6 8 4 9]

Neden doğru çalışıyor? Her yer değiştirmede aşağı inen ebeveyn, zaten altındaki bütün elemanlardan küçük veya onlara eşitti; yeni yerinde de kuralı bozmaz. Yukarı çıkan eleman ise eski ebeveyninden küçük olduğu için onun diğer çocuğundan da küçüktür. Yani kural ihlali her adımda bir seviye yukarı taşınır ve en geç kökte biter. Döngü en fazla ağacın yüksekliği kadar döner.

Pop: kökü al, sonuncuyu başa taşı, aşağı kaydır

En küçük eleman köktedir; onu okumak kolay. Zor olan, kökü çıkardıktan sonra ağacı onarmaktır. Kökü doğrudan silersek ağaç ikiye bölünür. Bunun yerine şu hileyi kullanırız: dilimin son elemanını köke taşı ve dilimi bir kısalt. Şekil kuralı korunur, ama köke gelen eleman büyük ihtimalle çok büyüktür. Onu aşağı kaydırırız (sift down): çocuklarından biri kendisinden küçük olduğu sürece küçük olan çocukla yer değiştir.

Az önceki [1 2 3 5 6 8 4 9] heap'inden Pop yapalım:

1) 1'i al, son eleman 9'u köke taşı     2) çocuklar 2 ve 3, küçüğü 2: yer değiştir

        (9)                                      2
       /   \                                   /   \
      2     3                                (9)    3
     / \   / \                               / \   / \
    5   6 8   4                             5   6 8   4

   [9 2 3 5 6 8 4]                         [2 9 3 5 6 8 4]


3) çocuklar 5 ve 6, küçüğü 5: yer değiştir
   9'un artık çocuğu yok: dur. Pop 1 döndürür.

         2
       /   \
      5     3
     / \   / \
   (9)  6 8   4

   [2 5 3 9 6 8 4]

Peek

En küçük eleman her zaman data[0] konumundadır; ona bakmak için hiçbir şeyi kaydırmak gerekmez.

Şimdi bu hareketleri kendin dene. Aşağıdaki görselleştirmede min-heap'e birkaç sayı ekle, sonra en küçüğü çıkar. Yeni elemanın yukarı tırmanışını ve köke taşınan son elemanın aşağı inişini adım adım izle; özellikle aşağı kaydırmada hangi çocuğun seçildiğine dikkat et.

Sıfırdan jenerik Heap[T]

Artık kodu yazabiliriz. Hedefimiz her tiple çalışan, hem min-heap hem max-heap olabilen, küçük ve anlaşılır bir tip. Jenerikler dersinde gördüğün tip parametreleri burada tam yerinde.

Tip, yapıcı ve Push

Karşılaştırma kuralını bir less fonksiyonuyla dışarıdan alıyoruz. cmp.Ordered kısıtı yerine fonksiyon almak iki kazanç sağlar: aynı int tipinden hem min-heap hem max-heap üretebilirsin ve struct'ları istediğin alana göre sıralayabilirsin.

// Heap, less fonksiyonuna göre en "küçük" elemanı kökte tutan ikili heap'tir.
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}

// New, boş bir heap oluşturur.
func New[T any](less func(a, b T) bool) *Heap[T] {
	return &Heap[T]{less: less}
}

func (h *Heap[T]) Len() int { return len(h.data) }

// Push, x'i sona ekler ve yukarı kaydırır: O(log n).
func (h *Heap[T]) Push(x T) {
	h.data = append(h.data, x)
	h.up(len(h.data) - 1)
}

func (h *Heap[T]) up(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if !h.less(h.data[i], h.data[parent]) {
			break // ebeveyn zaten küçük veya eşit
		}
		h.data[i], h.data[parent] = h.data[parent], h.data[i]
		i = parent
	}
}

up içindeki koşula dikkat: çocuk ebeveyninden kesin olarak küçük değilse duruyoruz. Eşit elemanların yerini gereksiz yere değiştirmemek işi azaltır.

Peek, Pop ve down

// Peek, en küçük elemanı çıkarmadan döndürür: O(1).
func (h *Heap[T]) Peek() (T, bool) {
	if len(h.data) == 0 {
		var zero T
		return zero, false
	}
	return h.data[0], true
}

// Pop, en küçük elemanı çıkarır ve döndürür: O(log n).
func (h *Heap[T]) Pop() (T, bool) {
	var zero T
	if len(h.data) == 0 {
		return zero, false
	}
	top := h.data[0]
	last := len(h.data) - 1
	h.data[0] = h.data[last]
	h.data[last] = zero // çöp toplayıcı eski değeri serbest bırakabilsin
	h.data = h.data[:last]
	h.down(0)
	return top, true
}

func (h *Heap[T]) down(i int) {
	n := len(h.data)
	for {
		smallest := i
		if l := 2*i + 1; l < n && h.less(h.data[l], h.data[smallest]) {
			smallest = l
		}
		if r := 2*i + 2; r < n && h.less(h.data[r], h.data[smallest]) {
			smallest = r
		}
		if smallest == i {
			return // iki çocuk da küçük değil: yerine oturdu
		}
		h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
		i = smallest
	}
}

İki ayrıntı önemli. Birincisi, boş heap'te panik oluşturmak yerine Go'nun virgül-ok (comma ok) deyimine uygun olarak (T, bool) döndürüyoruz. İkincisi, dilimi kısaltmadan önce son hücreyi sıfır değerle eziyoruz: T bir işaretçi ya da işaretçi içeren bir struct ise, alttaki dizide kalan eski referans çöp toplayıcının o nesneyi serbest bırakmasını engellerdi.

down fonksiyonu önce smallest değişkeninde düğümün kendisini, sol çocuğunu ve sağ çocuğunu karşılaştırır. Üçünün en küçüğü düğümün kendisiyse iş bitmiştir; değilse o çocukla yer değiştirip bir seviye aşağıda aynı soruyu tekrar sorar. l < n ve r < n kontrolleri, son seviyede çocuğu eksik olan düğümleri doğal olarak halleder.

Tam program

Aşağıdaki program heap'i üç biçimde kullanıyor: cmp.Less ile tamsayı min-heap'i, ters karşılaştırmayla bir max-heap ve ciddiyet derecesine göre hasta sıralayan bir acil servis kuyruğu. İçindeki Heapify fonksiyonunu bir sonraki bölümde inceleyeceğiz.

package main

import (
	"cmp"
	"fmt"
)

// Heap, less fonksiyonuna göre en "küçük" elemanı kökte tutan ikili heap'tir.
type Heap[T any] struct {
	data []T
	less func(a, b T) bool
}

// New, boş bir heap oluşturur.
func New[T any](less func(a, b T) bool) *Heap[T] {
	return &Heap[T]{less: less}
}

// Heapify, verilen dilimi yerinde heap'e çevirir: O(n).
// Dilimin sahipliği heap'e geçer.
func Heapify[T any](data []T, less func(a, b T) bool) *Heap[T] {
	h := &Heap[T]{data: data, less: less}
	for i := len(data)/2 - 1; i >= 0; i-- {
		h.down(i)
	}
	return h
}

func (h *Heap[T]) Len() int { return len(h.data) }

func (h *Heap[T]) Push(x T) {
	h.data = append(h.data, x)
	h.up(len(h.data) - 1)
}

func (h *Heap[T]) Peek() (T, bool) {
	if len(h.data) == 0 {
		var zero T
		return zero, false
	}
	return h.data[0], true
}

func (h *Heap[T]) Pop() (T, bool) {
	var zero T
	if len(h.data) == 0 {
		return zero, false
	}
	top := h.data[0]
	last := len(h.data) - 1
	h.data[0] = h.data[last]
	h.data[last] = zero
	h.data = h.data[:last]
	h.down(0)
	return top, true
}

func (h *Heap[T]) up(i int) {
	for i > 0 {
		parent := (i - 1) / 2
		if !h.less(h.data[i], h.data[parent]) {
			break
		}
		h.data[i], h.data[parent] = h.data[parent], h.data[i]
		i = parent
	}
}

func (h *Heap[T]) down(i int) {
	n := len(h.data)
	for {
		smallest := i
		if l := 2*i + 1; l < n && h.less(h.data[l], h.data[smallest]) {
			smallest = l
		}
		if r := 2*i + 2; r < n && h.less(h.data[r], h.data[smallest]) {
			smallest = r
		}
		if smallest == i {
			return
		}
		h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
		i = smallest
	}
}

type patient struct {
	name     string
	severity int
}

func main() {
	// 1) Tamsayılar için min-heap
	nums := New(cmp.Less[int])
	for _, x := range []int{5, 2, 8, 1, 9, 3} {
		nums.Push(x)
	}
	top, _ := nums.Peek()
	fmt.Println("tepe:", top, "| eleman sayısı:", nums.Len())
	fmt.Print("min-heap: ")
	for nums.Len() > 0 {
		x, _ := nums.Pop()
		fmt.Print(x, " ")
	}
	fmt.Println()

	// 2) Aynı veri, ters karşılaştırma: max-heap (heapify ile)
	maxHeap := Heapify([]int{5, 2, 8, 1, 9, 3}, func(a, b int) bool { return a > b })
	fmt.Print("max-heap: ")
	for maxHeap.Len() > 0 {
		x, _ := maxHeap.Pop()
		fmt.Print(x, " ")
	}
	fmt.Println()

	// 3) Struct'lar: en ciddi hasta önce
	er := New(func(a, b patient) bool { return a.severity > b.severity })
	er.Push(patient{"Ayşe", 3})
	er.Push(patient{"Mehmet", 9})
	er.Push(patient{"Zeynep", 6})
	er.Push(patient{"Can", 1})
	for er.Len() > 0 {
		p, _ := er.Pop()
		fmt.Printf("%s (ciddiyet %d)\n", p.name, p.severity)
	}

	_, ok := er.Pop()
	fmt.Println("boş heap'ten Pop:", ok)
}

tepe: 1 | eleman sayısı: 6
min-heap: 1 2 3 5 8 9
max-heap: 9 8 5 3 2 1
Mehmet (ciddiyet 9)
Zeynep (ciddiyet 6)
Ayşe (ciddiyet 3)
Can (ciddiyet 1)
boş heap'ten Pop: false

New(cmp.Less[int]) ifadesine bak: cmp.Less jenerik bir fonksiyondur ve [int] ile örneklendirildiğinde tam olarak func(a, b int) bool imzasına sahip bir değere dönüşür. Ayrıca her Pop sonucunun sıralı çıktığına dikkat et. Heap'in içi sıralı olmasa da, tekrar tekrar en küçüğü çekmek elemanları sıralı verir. Heap sıralaması tam olarak bu fikre dayanır: diziyi yerinde bir max-heap'e çevirir, sonra kökü tekrar tekrar dizinin sonuna taşıyıp heap'i bir küçültür. Sonuç O(n log n) süren, ek bellek istemeyen ama kararlı olmayan bir sıralamadır.

Heapify: O(n) ile yapılandırma

Elinde zaten n elemanlı bir dilim varsa heap'i nasıl kurarsın? İlk akla gelen, boş bir heap'e elemanları tek tek Push etmektir: n kez O(log n), toplam O(n log n). Oysa daha iyisi mümkün.

Heapify (Floyd'un yöntemi olarak da bilinir) dilimi olduğu gibi alır ve son iç düğümden köke doğru her düğümü aşağı kaydırır:

func Heapify[T any](data []T, less func(a, b T) bool) *Heap[T] {
	h := &Heap[T]{data: data, less: less}
	for i := len(data)/2 - 1; i >= 0; i-- {
		h.down(i)
	}
	return h
}

Döngünün neden len(data)/2 - 1 konumundan başladığını görmek kolay: n/2 ve sonrasındaki indekslerin sol çocuğu 2*i+1 ≥ n olur, yani hepsi yapraktır ve tek başına bir yaprak zaten geçerli bir heap'tir. Aşağıdan yukarı ilerlediğimiz için bir düğümü aşağı kaydırdığımız anda onun iki alt ağacı çoktan geçerli birer heap haline gelmiştir; down tam da bu durumda doğru çalışır.

Neden O(n)?

Kilit gözlem şudur: aşağı kaydırmanın maliyeti düğümün yüksekliğiyle (altında kalan seviye sayısıyla), yukarı kaydırmanın maliyeti ise derinliğiyle (köke uzaklığıyla) orantılıdır. Tam ikili ağaçta düğümlerin yaklaşık yarısı yapraktır, dörtte biri yaprakların hemen üstündedir ve bu böyle gider. Heapify'da kalabalık alt seviyeler neredeyse hiç iş yapmaz; uzun yolu yalnızca birkaç üst düğüm yürür. Tek tek eklemede ise tam tersi olur: kalabalık alt seviyelerdeki her eleman köke kadar tırmanmak zorunda kalabilir.

15 düğümlü mükemmel bir ikili ağaçta en kötü durumdaki yer değiştirme sayıları şöyledir:

Genel durumda yüksekliği h olan yaklaşık n/2ʰ⁺¹ düğüm vardır ve her biri en fazla h adım iner. Toplam iş:

n/4 · 1 + n/8 · 2 + n/16 · 3 + … = n · (1/4 + 2/8 + 3/16 + …) = n · 1

Parantez içindeki seri 1'e yakınsar; yani toplam yer değiştirme sayısı n'yi aşmaz ve heapify O(n) sürer. Teoriyi ölçümle doğrulayalım. Aşağıdaki program azalan sıralı bir dilimi (min-heap için en kötü girdi) iki yöntemle heap'e çeviriyor ve yer değiştirmeleri sayıyor:

package main

import "fmt"

// siftUp ve siftDown yaptıkları yer değiştirme sayısını döndürür.
func siftUp(a []int, i int) int {
	swaps := 0
	for i > 0 {
		p := (i - 1) / 2
		if a[i] >= a[p] {
			break
		}
		a[i], a[p] = a[p], a[i]
		i = p
		swaps++
	}
	return swaps
}

func siftDown(a []int, i int) int {
	swaps := 0
	n := len(a)
	for {
		m := i
		if l := 2*i + 1; l < n && a[l] < a[m] {
			m = l
		}
		if r := 2*i + 2; r < n && a[r] < a[m] {
			m = r
		}
		if m == i {
			return swaps
		}
		a[i], a[m] = a[m], a[i]
		i = m
		swaps++
	}
}

// descending, n, n-1, ..., 1 dilimini üretir.
func descending(n int) []int {
	a := make([]int, n)
	for i := range a {
		a[i] = n - i
	}
	return a
}

func main() {
	fmt.Printf("%9s %14s %10s\n", "n", "tek tek Push", "heapify")
	for _, n := range []int{15, 1023, 1<<20 - 1} {
		// 1) Boş heap'e tek tek ekle
		a := make([]int, 0, n)
		pushSwaps := 0
		for _, x := range descending(n) {
			a = append(a, x)
			pushSwaps += siftUp(a, len(a)-1)
		}

		// 2) Yerinde heapify
		b := descending(n)
		heapifySwaps := 0
		for i := n/2 - 1; i >= 0; i-- {
			heapifySwaps += siftDown(b, i)
		}

		fmt.Printf("%9d %14d %10d\n", n, pushSwaps, heapifySwaps)
	}
}

n   tek tek Push    heapify
       15             34         11
     1023           8194       1013
  1048575       18874370    1048555

Tek tek eklemede yer değiştirme sayısı n log n gibi büyürken heapify'da her zaman n'nin altında kalıyor. Bir milyonu aşan elemanda fark yaklaşık 18 kat. Go'nun heap.Init fonksiyonu da tam olarak bu algoritmayı kullanır ve belgelerinde karmaşıklığı O(n) olarak verilir.

container/heap paketi

Go'nun standart kütüphanesinde hazır bir heap var: container/heap. Ancak bu paket bir veri tipi değil, bir algoritmalar kümesidir. Heap'i sen tanımlarsın (genellikle bir dilim tipi), paket de o tip üzerinde yukarı ve aşağı kaydırma yapar. Bunun için tipinin şu arayüzü uygulaması gerekir:

// container/heap paketindeki tanım
type Interface interface {
	sort.Interface // Len() int, Less(i, j int) bool, Swap(i, j int)
	Push(x any)    // x'i Len() konumuna ekle
	Pop() any      // Len()-1 konumundaki elemanı çıkar ve döndür
}

İlk üç metot sort.Interface arayüzünden gelir. Kafa karıştıran kısım son ikisidir: senin yazdığın Push ve Pop metotları hiçbir heap mantığı içermez. Push elemanı dilimin sonuna ekler, Pop dilimin sonundaki elemanı çıkarır; o kadar. Heap düzenini paketin fonksiyonları sağlar:

• heap.Push(h, x) önce senin h.Push(x) metodunu çağırıp elemanı sona ekler, sonra onu yukarı kaydırır.
• heap.Pop(h) önce kökü sonuncuyla yer değiştirir (h.Swap(0, n-1)), yeni kökü ilk n-1 eleman içinde aşağı kaydırır ve en sonda senin h.Pop() metodunu çağırarak sona taşınmış en küçük elemanı çıkarır.

Yani paket, bizim Heap[T] tipimizin yaptığının aynısını yapıyor; yalnızca iş bölümü farklı. Pakette beş fonksiyon var:

En yaygın kullanım, bir tamsayı dilimini heap'e çevirmektir:

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap, container/heap için tamsayı min-heap'idir.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// Push ve Pop dilimin uzunluğunu değiştirdiği için işaretçi alıcı kullanır.
func (h *IntHeap) Push(x any) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func main() {
	h := &IntHeap{7, 2, 9, 4}
	heap.Init(h) // O(n) heapify
	heap.Push(h, 1)

	fmt.Println("dilim:", *h) // sıralı değil!
	fmt.Println("en küçük:", (*h)[0])

	fmt.Print("sırayla çıkanlar: ")
	for h.Len() > 0 {
		fmt.Print(heap.Pop(h), " ")
	}
	fmt.Println()
}

dilim: [1 2 9 7 4]
en küçük: 1
sırayla çıkanlar: 1 2 4 7 9

Çıktının ilk satırı önemli bir gerçeği gösteriyor: heap'in içindeki dilim sıralı değildir. Yalnızca (*h)[0] en küçük elemandır; geri kalanlar ancak heap.Pop ile sırayla çıkar.

Len, Less ve Swap değer alıcıyla yazılabilir çünkü dilimin uzunluğunu değiştirmezler; elemanları yerinde değiştirmek için dilim başlığının kopyası yeterlidir. Push ve Pop ise dilimin uzunluğunu değiştirdiği için işaretçi alıcı kullanmak zorundadır. Bu yüzden heap fonksiyonlarına her zaman bir işaretçi (h := &IntHeap{...}) verilir.

Öncelik kuyruğu uygulaması

Gerçek hayatta öncelikler değişir. Diyelim bir görev yöneticisi yazıyorsun: görevler bir öncelikle eklenir, en acil olan önce işlenir, ama bir görevin önceliği kuyruktayken artabilir. Heap'teki bir elemanın değerini değiştirmek heap özelliğini bozabilir; bunu onarmak için heap.Fix(h, i) vardır. Fakat Fix elemanın indeksini ister ve elemanlar her yer değiştirmede başka bir konuma taşınır. Çözüm: her görev heap içindeki güncel konumunu kendisi tutsun ve Swap bu alanı her seferinde güncellesin.

package main

import (
	"container/heap"
	"fmt"
)

type Task struct {
	name     string
	priority int // büyük sayı = daha acil
	seq      int // eşit öncelikte eklenme sırası
	index    int // heap içindeki konumu; heap.Fix için gerekli
}

type PriorityQueue []*Task

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	if pq[i].priority != pq[j].priority {
		return pq[i].priority > pq[j].priority // yüksek öncelik önce çıkar
	}
	return pq[i].seq < pq[j].seq // eşitlikte önce eklenen önce çıkar
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
	t := x.(*Task)
	t.index = len(*pq)
	*pq = append(*pq, t)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	t := old[n-1]
	old[n-1] = nil // çöp toplayıcı için referansı bırak
	t.index = -1   // artık kuyrukta değil
	*pq = old[:n-1]
	return t
}

// update, kuyruktaki bir görevin önceliğini değiştirir ve düzeni onarır.
func (pq *PriorityQueue) update(t *Task, priority int) {
	t.priority = priority
	heap.Fix(pq, t.index)
}

func main() {
	pq := &PriorityQueue{}
	tasks := map[string]*Task{}
	add := func(name string, priority int) {
		t := &Task{name: name, priority: priority, seq: len(tasks)}
		tasks[name] = t
		heap.Push(pq, t)
	}

	add("e-posta yanıtla", 2)
	add("sunucu çöktü", 10)
	add("rapor yaz", 5)
	add("kahve molası", 1)
	add("kod incelemesi", 5)
	add("birim testleri", 2)

	// Müşteri aradı: raporun aciliyeti arttı.
	pq.update(tasks["rapor yaz"], 8)

	for pq.Len() > 0 {
		t := heap.Pop(pq).(*Task)
		fmt.Printf("%-16s öncelik=%d\n", t.name, t.priority)
	}
}

sunucu çöktü     öncelik=10
rapor yaz        öncelik=8
kod incelemesi   öncelik=5
e-posta yanıtla  öncelik=2
birim testleri   öncelik=2
kahve molası     öncelik=1

Kodun önemli noktaları:

• index alanı: Push ve Swap her seferinde günceller. Böylece update içinde heap.Fix(pq, t.index) doğru konumu bilir. Fix önce aşağı kaydırmayı dener, eleman hiç inmediyse yukarı kaydırır; önceliğin arttığını mı azaldığını mı bilmen gerekmez.
• seq alanı: Heap kararlı değildir: eşit öncelikli iki elemanın çıkış sırası eklenme sırasıyla aynı olmak zorunda değildir. "e-posta yanıtla" ile "birim testleri" aynı önceliğe sahip; eşitlikte eklenme sırasına bakan ikinci karşılaştırma sonucu öngörülebilir kılıyor.
• Pop içindeki temizlik: Çıkan görevin dilimdeki referansı nil yapılır ve index alanı -1 olur. Kuyruktan çıkmış bir görevle yanlışlıkla Fix çağırırsan bu değer hatayı erken fark etmeni sağlar.

Önceliği güncellemek de, bir görevi heap.Remove(pq, t.index) ile tamamen iptal etmek de logaritmik sürer:

Klasik problemler

Top-K: en büyük k eleman

Bir oyunda milyonlarca skor akarken en yüksek 10 skoru takip etmek istiyorsun. Hepsini sıralamak O(n log n) sürer ve bütün veriyi bellekte tutmayı gerektirir. Daha iyisi k elemanlı bir min-heap kullanmaktır.

İlk bakışta ters gelebilir: en büyükleri istiyoruz, neden min-heap? Heap'i k kişilik bir finalist listesi gibi düşün. Listeye girmek için listedeki en düşük puanı geçmen yeterli; girdiğinde en düşük puanlı finalist elenir. Min-heap'in kökü tam olarak bu eleme sınırıdır: ona O(1) sürede bakarız, yerine yenisini koymak O(log k) sürer.

package main

import (
	"container/heap"
	"fmt"
	"slices"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// topK, akıştaki en büyük k sayıyı tutan min-heap'i döndürür.
func topK(stream []int, k int) IntHeap {
	h := &IntHeap{}
	for _, x := range stream {
		if h.Len() < k {
			heap.Push(h, x)
		} else if x > (*h)[0] {
			(*h)[0] = x    // eleme sınırındaki aday elendi
			heap.Fix(h, 0) // yeni elemanı yerine indir: O(log k)
		}
	}
	return *h
}

func main() {
	scores := []int{42, 17, 93, 8, 71, 56, 99, 23, 64, 88}

	for _, k := range []int{3, 5} {
		h := topK(scores, k)
		best := slices.Clone(h)
		slices.Sort(best)
		slices.Reverse(best)
		fmt.Printf("en büyük %d: %v | %d. en büyük: %d\n", k, best, k, h[0])
	}
}

en büyük 3: [99 93 88] | 3. en büyük: 88
en büyük 5: [99 93 88 71 64] | 5. en büyük: 64

Döngü bittiğinde heap'in kökü akıştaki k. en büyük elemandır. Kökün yerine yeni değeri yazıp heap.Fix(h, 0) çağırmak, Pop ardından Push yapmaktan daha ucuzdur: tek bir aşağı kaydırma yeter. Heap hiçbir zaman k elemandan büyümediği için bellek de O(k) kalır; veri bir akıştan geliyorsa bütününü görmen bile gerekmez.

K sıralı listeyi birleştirme

Elinde her biri kendi içinde sıralı k tane liste var ve bunları tek bir sıralı liste halinde birleştirmek istiyorsun. Bu problem, belleğe sığmayan büyük veriyi parçalar halinde sıralayıp sonra birleştiren harici sıralamanın (external sort) temel adımıdır.

Fikir basit: her listenin henüz kullanılmamış ilk elemanı bir aday. Adaylar arasından en küçüğü bulmak tam bir heap işi. Heap'e her listenin ilk elemanını koy; en küçüğü çek, sonuca ekle ve aynı listenin sıradaki elemanını heap'e koy. Heap'te hiçbir zaman k'dan fazla eleman bulunmaz.

package main

import (
	"container/heap"
	"fmt"
)

// item, heap'teki bir aday: değer ve nereden geldiği.
type item struct {
	value int
	list  int // hangi listeden
	pos   int // o listedeki konumu
}

type minHeap []item

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func mergeK(lists [][]int) []int {
	h := &minHeap{}
	total := 0
	for i, l := range lists {
		total += len(l)
		if len(l) > 0 {
			*h = append(*h, item{value: l[0], list: i, pos: 0})
		}
	}
	heap.Init(h) // k aday: O(k)

	result := make([]int, 0, total)
	for h.Len() > 0 {
		it := heap.Pop(h).(item)
		result = append(result, it.value)
		if next := it.pos + 1; next < len(lists[it.list]) {
			heap.Push(h, item{value: lists[it.list][next], list: it.list, pos: next})
		}
	}
	return result
}

func main() {
	lists := [][]int{
		{1, 4, 7, 10},
		{2, 5, 8},
		{0, 3, 6, 9, 12},
		{},
	}
	fmt.Println(mergeK(lists))
}

[0 1 2 3 4 5 6 7 8 9 10 12]

Heap'teki her kayıt, değerin yanında hangi listenin hangi konumundan geldiğini de taşıyor; sıradaki elemanı bulmak için bu bilgi şart. Toplam N eleman varsa her biri heap'e bir kez girip bir kez çıkar ve heap'in boyutu k ile sınırlıdır. Aynı fikir bağlı listelerle de çalışır: indeks yerine düğüm işaretçisi saklarsın ve sıradaki eleman node.Next olur.

Dijkstra ve diğer graf algoritmaları

Dijkstra algoritması her adımda "henüz kesinleşmemiş düğümler arasında mesafesi en küçük olanı" seçer; bu bir min-öncelik kuyruğudur. Bir düğüme daha kısa bir yol bulunduğunda iki seçenek vardır: heap.Fix ile düğümün önceliğini güncellemek ya da kuyruğa yeni mesafeyle ikinci bir kayıt ekleyip, çekilen kaydın eskimiş olup olmadığını kontrol etmek (tembel silme, lazy deletion). İkincisi index takibi gerektirmediği için pratikte daha yaygındır. Heap, Prim algoritmasında da aynı rolü üstlenir.

Heap mi, başka bir yapı mı?

Heap'i şu durumlarda seç:

• Sürekli değişen bir veride tekrar tekrar "en küçük" ya da "en büyük" soruluyorsa: zamanlayıcılar, görev kuyrukları, olay simülasyonları.
• Tam sıralama değil kısmi sıralama yetiyorsa: top-k, k yollu birleştirme, hareketli medyan.
• Dijkstra, Prim ve A* gibi "sıradaki en iyi aday" mantığıyla çalışan graf algoritmalarında.

Şu durumlarda başka bir yapı düşün:

• Rastgele bir elemanı aramak ya da silmek sık gerekiyorsa: indeks takibi yoksa heap'te bu O(n) sürer.
• Verinin tamamını bir kez sıralı gezmen yetiyorsa: slices.Sort daha basittir.
• Hem en küçüğe hem en büyüğe sık erişmen gerekiyorsa: dengeli bir ağaç ya da iki heap düşün.
• Eleman sayısı çok küçükse (birkaç düzine): sırasız bir dilimi taramak genellikle yeterince hızlıdır ve kodu sadeleştirir.

Sık yapılan hatalar

• heap.Push yerine h.Push çağırmak. Kod derlenir ama eleman yukarı kaydırılmadığı için heap özelliği bozulur. Arayüz metotlarını yalnızca paket çağırmalı.
• heap.Init çağırmayı unutmak. Dilimi elle doldurduktan sonra Init çağırmazsan ilk Pop bile yanlış eleman döndürebilir.
• Top-k'da yanlış heap türünü seçmek. En büyük k eleman için max-heap kullanırsan tepede en büyük durur; eleme sınırını O(1) sürede göremezsin.
• Önceliği değiştirip heap.Fix çağırmamak. Değeri değişen eleman yanlış yerde kalır ve sonraki Pop işlemleri hatalı sırada çıkar.
• Swap içinde index alanını güncellememek. Fix ve Remove yanlış elemanı taşır; hata çoğu zaman çok sonra, alakasız bir yerde ortaya çıkar.
• Heap dilimini sıralı sanmak. fmt.Println(*h) sıralı bir çıktı vermez. Sıralı sonuç için elemanları Pop et ya da bir kopyayı slices.Sort ile sırala.
• Push ve Pop için değer alıcı kullanmak. Uzunluk değişikliği kopyada kalır ve eklenen elemanlar kaybolur. Bu iki metot işaretçi alıcıyla yazılmalı.
• Çıkarılan elemanın referansını dilimde bırakmak. İşaretçi tutan heap'lerde old[n-1] = nil yapmazsan, çıkardığın nesneyi çöp toplayıcı bir süre serbest bırakamaz.

Alıştırmalar

package main

import "fmt"

func isMinHeap(a []int) bool {
	n := len(a)
	for i := range n / 2 { // yalnızca çocuğu olan düğümler
		if l := 2*i + 1; a[l] < a[i] {
			return false
		}
		if r := 2*i + 2; r < n && a[r] < a[i] {
			return false
		}
	}
	return true
}

func main() {
	tests := [][]int{
		{},
		{1, 3, 2, 7, 4, 5},
		{1, 2, 3, 4, 5, 6, 7},
		{2, 5, 3, 1},
		{5, 5, 5},
	}
	for _, t := range tests {
		fmt.Println(t, isMinHeap(t))
	}
}

[] true
[1 3 2 7 4 5] true
[1 2 3 4 5 6 7] true
[2 5 3 1] false
[5 5 5] true

package main

import (
	"container/heap"
	"fmt"
	"slices"
)

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func lastStoneWeight(stones []int) int {
	h := MaxHeap(slices.Clone(stones)) // çağıranın dilimini bozma
	heap.Init(&h)
	for h.Len() > 1 {
		y := heap.Pop(&h).(int) // en ağır
		x := heap.Pop(&h).(int) // ikinci en ağır
		if y != x {
			heap.Push(&h, y-x)
		}
	}
	if h.Len() == 0 {
		return 0
	}
	return h[0]
}

func main() {
	fmt.Println(lastStoneWeight([]int{2, 7, 4, 1, 8, 1}))
	fmt.Println(lastStoneWeight([]int{3, 3}))
	fmt.Println(lastStoneWeight([]int{10}))
}

1
0
10

package main

import (
	"cmp"
	"container/heap"
	"fmt"
	"slices"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

func minMeetingRooms(meetings [][2]int) int {
	sorted := slices.Clone(meetings)
	slices.SortFunc(sorted, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })

	ends := &IntHeap{} // kullanımdaki odaların bitiş zamanları
	for _, m := range sorted {
		if ends.Len() > 0 && (*ends)[0] <= m[0] {
			heap.Pop(ends) // en erken boşalan oda artık serbest
		}
		heap.Push(ends, m[1])
	}
	return ends.Len()
}

func main() {
	fmt.Println(minMeetingRooms([][2]int{{0, 30}, {5, 10}, {15, 20}}))
	fmt.Println(minMeetingRooms([][2]int{{7, 10}, {2, 4}}))
	fmt.Println(minMeetingRooms([][2]int{{1, 5}, {2, 6}, {3, 7}, {5, 8}}))
}

2
1
3

package main

import (
	"container/heap"
	"fmt"
)

// IntHeap, less alanı sayesinde hem min hem max heap olabilir.
type IntHeap struct {
	data []int
	less func(a, b int) bool
}

func (h IntHeap) Len() int           { return len(h.data) }
func (h IntHeap) Less(i, j int) bool { return h.less(h.data[i], h.data[j]) }
func (h IntHeap) Swap(i, j int)      { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *IntHeap) Push(x any)        { h.data = append(h.data, x.(int)) }
func (h *IntHeap) Pop() any {
	x := h.data[len(h.data)-1]
	h.data = h.data[:len(h.data)-1]
	return x
}
func (h *IntHeap) Peek() int { return h.data[0] }

type MedianFinder struct {
	lower *IntHeap // küçük yarı: max-heap
	upper *IntHeap // büyük yarı: min-heap
}

func NewMedianFinder() *MedianFinder {
	return &MedianFinder{
		lower: &IntHeap{less: func(a, b int) bool { return a > b }},
		upper: &IntHeap{less: func(a, b int) bool { return a < b }},
	}
}

func (m *MedianFinder) Add(x int) {
	if m.lower.Len() == 0 || x <= m.lower.Peek() {
		heap.Push(m.lower, x)
	} else {
		heap.Push(m.upper, x)
	}
	// Denge: lower, upper'dan en fazla 1 eleman fazla olabilir.
	if m.lower.Len() > m.upper.Len()+1 {
		heap.Push(m.upper, heap.Pop(m.lower))
	} else if m.upper.Len() > m.lower.Len() {
		heap.Push(m.lower, heap.Pop(m.upper))
	}
}

// Median, en az bir eleman eklendikten sonra çağrılmalıdır.
func (m *MedianFinder) Median() float64 {
	if m.lower.Len() > m.upper.Len() {
		return float64(m.lower.Peek())
	}
	return float64(m.lower.Peek()+m.upper.Peek()) / 2
}

func main() {
	mf := NewMedianFinder()
	for _, x := range []int{5, 15, 1, 3, 8, 7, 9, 10} {
		mf.Add(x)
		fmt.Printf("%d eklendi -> medyan %g\n", x, mf.Median())
	}
}

5 eklendi -> medyan 5
15 eklendi -> medyan 10
1 eklendi -> medyan 5
3 eklendi -> medyan 4
8 eklendi -> medyan 5
7 eklendi -> medyan 6
9 eklendi -> medyan 7
10 eklendi -> medyan 7.5

Kısa sınav

Özet

• Heap, tam ikili ağaç şekline ve ebeveyn ile çocuk arasındaki sıralama kuralına uyan bir yapıdır; min-heap'te en küçük, max-heap'te en büyük eleman her zaman köktedir.
• Tam ağaçta boşluk olmadığı için heap düz bir dilimde saklanır: sol çocuk 2*i+1, sağ çocuk 2*i+2, ebeveyn (i-1)/2.
• Push sona ekleyip yukarı kaydırır, Pop son elemanı köke taşıyıp küçük çocukla aşağı kaydırır; ikisi de O(log n), Peek O(1) sürer.
• Heapify son iç düğümden köke doğru aşağı kaydırarak heap'i O(n) sürede kurar; heap.Init bu algoritmayı kullanır.
• container/heap ile tipin Len, Less, Swap, Push ve Pop metotlarını uygular, ama ekleme ve çıkarmayı her zaman heap.Push ve heap.Pop ile yaparsın.
• Değeri değişen bir eleman için heap.Fix(h, i) kullanılır; bunun için elemanın indeksini Swap içinde güncel tutmak gerekir. Heap kararlı değildir, eşitlikte sıra istiyorsan ek bir alanla karşılaştır.
• En büyük k eleman için k boyutlu min-heap (O(n log k)), k sıralı listeyi birleştirmek için k adaylı min-heap (O(N log k)) kullanılır.
• Heap sıralı değildir ve rastgele arama O(n) sürer; gücü tek bir soruda yatar: "Sıradaki en öncelikli eleman hangisi?"