---
title: "İkili Yığınlar (Binary Heaps)"
subtitle: "Öncelik kuyruğu (insert + delete_max) = set'in alt kümesi; complete binary tree diziye örtük gömülür (left 2i+1, right 2i+2, parent (j−1)//2); max-heap özelliği + heapify up/down O(log n); yerinde heapsort O(n log n) ve doğrusal build = yüksekliklerin toplamı = O(n)"
---
::: {.callout-note title="Bölüm bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 8: Binary Heaps](https://www.youtube.com/watch?v=Xnpo1atN-Iw) (≈51 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 8: Binary Heaps](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/lecture-8-binary-heaps/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 12 (L8)
- **Hoca:** Erik Demaine
- **Okuma süresi:** ≈26 dk
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d12}
Ders 10 (L7) AVL ağaçlarıyla her sequence/set işlemini $O(\log n)$'e indirdi. Bugün, AVL'nin **basitleştirilmiş bir hâlini** kuruyoruz: **ikili yığın (binary heap)**. Aynı $O(\log n)$ sınırlarını verir ama iki üstünlüğü vardır — **doğrusal-zaman build** ve, asıl önemlisi, **yerinde (in-place) sıralama** (heapsort).
> *"Today, we're going to cover a different kind of tree-like data structure called a heap — a binary heap. It's going to let us solve sorting problem in a new way."* — Demaine, 0:19
Üç temel kavram bu derste yan yana gelir:
1. **Öncelik kuyruğu (priority queue)** — set arayüzünün alt kümesi: insert + delete_max; bu kısıtlama yeni güç verir.
2. **Complete binary tree ↔ dizi** — yığın, diziye gömülü tam-ağaçtır (işaretçisiz, örtük; index aritmetiği).
3. **Max-heap özelliği + heapify** — her düğüm çocuklarından büyük-eşit; ekle/sil heapify up/down ile $O(\log n)$.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 12'nin (L8) kavram haritası: kök = ikili yığın. Dört dal — (1) öncelik kuyruğu, set arayüzünün alt kümesidir (insert + delete_max); daha az söz veren arayüz daha güçlü optimizasyon açar. (2) complete binary tree, diziye örtük (işaretçisiz) gömülür; düğüm bağları yalnız index aritmetiğiyle bulunur (left 2i+1, right 2i+2, parent (j−1)//2) → yükseklik ⌈log n⌉, rotasyon gerekmez. (3) max-heap özelliği (her düğüm çocuklarından büyük-eşit, maksimum kökte) heapify up/down ile korunur, insert/delete_max O(log n). (4) heapsort yerinde (prefix yığın) ve O(n log n); doğrusal build ise yüksekliklerin toplamıdır = O(n). Sonuç: öncelik kuyruğu + bedava in-place sıralama."
flowchart TD
A["Ders 12 (L8): İkili Yığınlar"] --> PQ["Öncelik kuyruğu<br/>set arayüzünün alt kümesi"]
PQ --> PQ1["insert + delete_max<br/>az söz veren arayüz = çok güç"]
A --> CT["Complete binary tree ↔ dizi<br/>örtük, işaretçisiz"]
CT --> CT1["index aritmetiği<br/>sol 2i+1, sağ 2i+2, parent (j−1)//2"]
CT --> CT2["yükseklik ⌈log n⌉<br/>rotasyon gerekmez"]
A --> MH["Max-heap özelliği + heapify<br/>her düğüm çocuklarından büyük-eşit"]
MH --> MH1["maksimum kökte<br/>heapify up/down ile O(log n)"]
A --> HS["Heapsort + doğrusal build"]
HS --> HS1["yerinde, prefix yığın<br/>O(n log n) tek in-place"]
HS --> HS2["doğrusal build<br/>yüksekliklerin toplamı = O(n)"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class PQ,CT,MH,HS branch
class PQ1,CT1,CT2,MH1,HS1,HS2 leaf
```
::: {.callout-tip title="Builder Notu — Sadeleştirme = Güç"}
İkili yığın, AVL'nin *basitleştirilmiş* hâli — tüm set yerine yalnızca "maksimumu bul/sil" istediğimiz için, complete binary tree'yi (rotasyonsuz!) koruyabiliriz. Az söz veren bir arayüz, daha güçlü optimizasyon imkânı açar.
- **Geriye → Ders 10 (AVL):** AVL keyfi BST şekliyle rotasyon gerektirir; yığın şekli $n$ tarafından zaten sabittir → rotasyon yok, yalnız heapify (takas).
- **İleriye → graph algoritmaları:** Dijkstra ve Prim, öncelik kuyruğunu (yığını) doğrudan kullanır — "en yakın sıradakini al" mantığı.
- **İleriye → sistem:** router paket önceliği, işletim sistemi process scheduling, olay-tabanlı simülasyon hep öncelik kuyruğudur.
- **İleriye → heapsort:** $O(n \log n)$ *ve* in-place — ek bellek ayıramayan ortamlarda (gömülü, çekirdek) merge sort'a tercih edilir.
Tek cümle: *Öncelik kuyruğunu, diziye gömülü dengeli bir tam-ağaçla (yığın) çözersek, ekle/sil $O(\log n)$ olur ve yerinde $O(n \log n)$ sıralama (heapsort) bedava gelir.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 12 (L8) İkili Yığın motoru (_engine.py D12 bölümü:
# heap_left'ten complete_tree_depth_height_sums'a) + Slate+Amber viz
# (_viz.py COL_* + apply_style). Bu hücre gizlidir (#| echo: false).
# Aşağıdaki TÜM figür hücreleri bu hücrede tanımlanan
# heap_left / heap_right / heap_parent / is_max_heap / max_heapify_up /
# max_heapify_down / heap_insert / heap_delete_max / build_heap_linear /
# heapsort_inplace / heapsort_trace / heapify_up_trace / heapify_down_trace /
# complete_tree_depth_height_sums + COL_* / apply_style'ı IMPORT ETMEDEN kullanır.
#
# Notion'daki öğretim içeriği (görünür ```python blokları) bu motorun tarif
# seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Standalone testte savefig
# kullanılır; Quarto render'da jupyter inline backend'i ayarlar.
# Yalnız D12 gerekenler gömülür.
# ============================================================================
import math
import matplotlib.pyplot as plt
from matplotlib.patches import Circle, FancyBboxPatch, FancyArrowPatch
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
# ---------------------------------------------------------------------------
# _engine.py D12 (L8) — İkili Yığınlar: complete tree ↔ dizi, max-heap,
# heapify, heapsort. Düz fonksiyonlar (ders-paralel; işaretçisiz, örtük dizi).
# ---------------------------------------------------------------------------
def heap_left(i):
"""Sol çocuk index'i (L8 §6): 2i + 1."""
return 2 * i + 1
def heap_right(i):
"""Sağ çocuk index'i: 2i + 2 (sol çocuğun sağ kardeşi)."""
return 2 * i + 2
def heap_parent(j):
"""Parent index'i: (j − 1) // 2 (tamsayı bölme; kök için tanımsız, j ≥ 1)."""
return (j - 1) // 2
def is_max_heap(Q, n=None):
"""Max-heap özelliği denetimi (L8 §7): her i için Q[i] ≥ çocukları."""
if n is None:
n = len(Q)
for i in range(n):
for c in (heap_left(i), heap_right(i)):
if c < n and Q[i] < Q[c]:
return False
return True
def max_heapify_up(Q, j):
"""insert sonrası KABARMA (L8 §8): parent küçükse takas + yukarı özyinele.
Döndürür: takas sayısı (≤ derinlik = O(log n))."""
swaps = 0
while j > 0:
p = heap_parent(j)
if Q[p] >= Q[j]:
break
Q[p], Q[j] = Q[j], Q[p]
j = p
swaps += 1
return swaps
def max_heapify_down(Q, i, n=None):
"""delete_max sonrası AŞAĞI SÜZME (L8 §9): iki çocuktan BÜYÜĞÜYLE takas +
aşağı özyinele. Döndürür: takas sayısı (≤ yükseklik = O(log n))."""
if n is None:
n = len(Q)
swaps = 0
while True:
l, r, big = heap_left(i), heap_right(i), i
if l < n and Q[l] > Q[big]:
big = l
if r < n and Q[r] > Q[big]:
big = r
if big == i:
return swaps
Q[i], Q[big] = Q[big], Q[i]
i = big
swaps += 1
def heap_insert(Q, x):
"""insert (L8 §8): SONA ekle (tek geçerli yer) + heapify_up. O(log n)."""
Q.append(x)
max_heapify_up(Q, len(Q) - 1)
def heap_delete_max(Q):
"""delete_max (L8 §9): kök ↔ son takas, son öğeyi sil, kökten heapify_down.
O(log n). Döndürür: maksimum."""
Q[0], Q[-1] = Q[-1], Q[0]
top = Q.pop()
if Q:
max_heapify_down(Q, 0)
return top
def build_heap_linear(A):
"""DOĞRUSAL build (L8 §10): bottom-up heapify-down — yüksekliklerin
toplamı = O(n). Yerinde dönüştürür, listeyi döndürür."""
n = len(A)
for i in range(n // 2 - 1, -1, -1):
max_heapify_down(A, i, n)
return A
def heapsort_inplace(A):
"""In-place heapsort (L8 §10): doğrusal build + 'kök↔son takas, yığını
küçült, süz' n kez → dizi YUKARI SIRALI. O(n log n), ek alan O(1)."""
build_heap_linear(A)
for end in range(len(A) - 1, 0, -1):
A[0], A[end] = A[end], A[0] # max'i sıralı soneke gönder
max_heapify_down(A, 0, end) # prefix yığını onar
return A
def heapsort_trace(A):
"""fig-heapsort için: her delete_max adımında (prefix_yığın, sıralı_sonek)."""
Q = build_heap_linear(list(A))
steps = [{"heap": list(Q), "sorted": []}]
for end in range(len(Q) - 1, 0, -1):
Q[0], Q[end] = Q[end], Q[0]
max_heapify_down(Q, 0, end)
steps.append({"heap": Q[:end], "sorted": Q[end:]})
return {"steps": steps, "output": list(Q)}
def heapify_up_trace(Q, x):
"""fig-heapify-up için: insert(x) kabarma izi — her takasta dizi durumu."""
Q = list(Q)
Q.append(x)
j = len(Q) - 1
states = [{"array": list(Q), "pos": j}]
while j > 0 and Q[heap_parent(j)] < Q[j]:
p = heap_parent(j)
Q[p], Q[j] = Q[j], Q[p]
j = p
states.append({"array": list(Q), "pos": j})
return {"states": states, "final": Q}
def heapify_down_trace(Q):
"""fig-heapify-down için: delete_max izi — kök↔son takas + süzme adımları."""
Q = list(Q)
Q[0], Q[-1] = Q[-1], Q[0]
top = Q.pop()
i = 0
states = [{"array": list(Q), "pos": i}]
n = len(Q)
while True:
l, r, big = heap_left(i), heap_right(i), i
if l < n and Q[l] > Q[big]:
big = l
if r < n and Q[r] > Q[big]:
big = r
if big == i:
break
Q[i], Q[big] = Q[big], Q[i]
i = big
states.append({"array": list(Q), "pos": i})
return {"removed_max": top, "states": states, "final": Q}
def complete_tree_depth_height_sums(n):
"""Doğrusal-build tanığı (L8 §10): n düğümlü complete tree'de
Σ derinlik (≈ n log n — tek tek insert maliyeti) vs
Σ yükseklik (≤ 2n — bottom-up build maliyeti, O(n)).
Döndürür: (sum_depths, sum_heights)."""
if n <= 0:
return 0, 0
sum_d = sum(int(math.log2(i + 1)) for i in range(n)) # depth(i)=⌊log₂(i+1)⌋
def height(i):
h = 0
j = heap_left(i)
while j < n: # complete tree: sol zincir = yükseklik
h += 1
j = heap_left(j)
return h
sum_h = sum(height(i) for i in range(n))
return sum_d, sum_h
```
## 1. Öncelik Kuyruğu Arayüzü {#sec-1-oncelik-kuyrugu-arayuzu}
**Öncelik kuyruğu**, öğeleri anahtarlarına (önceliklerine) göre tutar ve iki temel işlem sunar: insert (öğe ekle) ve delete_max (en yüksek öncelikli öğeyi sil ve döndür). Bu, set arayüzünün bir **alt kümesidir** — ve alt kümeler ilginçtir, çünkü daha basit/hızlı çözülebilirler.
> *"priority queue... This is a subset of the set interface."* — Demaine, 0:40
Motivasyon her yerde: router'da paket önceliği, işletim sisteminde hangi process'i çalıştıracağını seçmek, olayları zaman sırasına göre işlemek — ve bu sınıfta ileride çizge algoritmaları.
## 2. Set AVL ile Çözüm {#sec-2-set-avl-ile}
Set AVL ağacı bu işlemleri zaten yapar: insert/delete_max $O(\log n)$, build $O(n \log n)$ (önce sıralama gerekir). find_max'i bir **alt ağaç zenginleştirmesiyle** (her düğümde alt ağacın maksimum anahtarı) $O(1)$'e bile indirebiliriz.
> *"set AVL is our most powerful data structure."* — Demaine, 3:33
Yani aslında "işimiz bitti". Ama bugün **ikili yığın** öğreneceğiz: AVL kadar güçlü değil, sadece priority queue'yu çözüyor — ama daha basit, build'i bir log faktör hızlı, ve **in-place sıralama** veriyor.
## 3. Priority Queue Sort {#sec-3-priority-queue-sort}
Öncelik kuyruğu arayüzünü gerçekleştiren *herhangi* bir yapıdan bir sıralama algoritması doğar: tüm öğeleri ekle, sonra hepsini delete_max ile çıkar. delete_max büyükten küçüğe verdiği için, ters-sıralı çıkar; lineer zamanda ters çevir → sıralı.
> *"given any data structure that implements a priority queue interface... I can make a sorting algorithm. Insert all the items, delete all the items."* — Demaine, 8:29
Çalışma süresi: $T_{\text{build}}(n) + n \cdot T_{\text{delete\_max}}$ — veya $n \cdot (T_{\text{insert}} + T_{\text{delete\_max}})$. Hangi yapıyı koyarsan, o sıralamayı alırsın.
## 4. Üç Sıralama: Birleştirici Çerçeve {#sec-4-uc-siralama-birlestirici}
Priority queue sort, daha önce gördüğümüz üç sıralamayı **tek çerçevede** birleştirir:
- **Set AVL** (insert/delete $O(\log n)$) → **AVL sort**, $O(n \log n)$.
- **Sırasız dizi** (insert $O(1)$, delete_max $O(n)$ — maksimumu tara, sona taşı) → **selection sort**, $O(n^2)$.
- **Sıralı dizi** (insert $O(n)$ — kaydır, delete_max $O(1)$ — son öğe) → **insertion sort**, $O(n^2)$.
> *"arrays give us selection sort... insertion sort."* — Demaine, 11:53
Selection ve insertion sort **in-place** (sabit ek alan) ama $O(n^2)$; AVL sort ve merge sort $O(n \log n)$ ama in-place *değil*. Bugünkü hedef: **$n \log n$ *ve* in-place** — ikili yığın ile (heapsort).
@fig-pq-sort-frame bunu tek çerçevede toplar: aynı "hepsini insert, sonra hepsini delete_max" tarifi; hangi veri yapısını koyarsan o sıralama doğar. Hedef satır 4 — ikili yığın, iki işlemi de $O(\log n)$ dengeler ve sonuç hem $O(n \log n)$ hem yerinde.
```{python}
#| label: fig-pq-sort-frame
#| fig-cap: "Öncelik kuyruğu sıralaması — birleştirici çerçeve: PQ'yu hangi yapı uygularsa o sıralama doğar (L8 §3-4). Üst kutu TEK tarifi anlatır: tüm öğeleri insert et → sonra hepsini delete_max ile çek (çekiş sırası = azalan sıralı). Altta 4 satır yapı → sıralama: (1) sırasız dizi [insert O(1) / delete_max O(n)] → Selection Sort O(n²); (2) sıralı dizi [insert O(n) / delete_max O(1)] → Insertion Sort O(n²); (3) küme AVL ağacı [O(log n)/O(log n)] → AVL Sort O(n log n); (4) İKİLİ YIĞIN [O(log n)/O(log n)] → HEAPSORT O(n log n) + IN-PLACE rozeti (amber vurgu, hedef satır). Dizi PQ'lar bir işlemi ucuz yapar ama diğerini O(n)'e iter → O(n²); yığın iki işlemi de O(log n) dengeler → O(n log n). Motor kanıtı: Q=[]; insert [4,1,7,3,9,2,6]; drain ×7 = [9,7,6,4,3,2,1] = sorted(desc)."
#| fig-width: 10.5
#| fig-height: 6.8
# fig-pq-sort-frame (L8 §3-4): PQ sort birleştirici çerçeve — 4 yapı → 4 sıralama.
# Üst tarif şematik; ASSERT ile PQ sort tarifi motordan (heap_insert/heap_delete_max)
# canlı doğrulanır. COL_* / plt gizli setup hücresinden.
def _pq_cost_badge(ax, x, y, w, h, text, *, hot=False):
if hot:
fc, ec, tcol = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
else:
fc, ec, tcol = COL_WHITE, COL_SLATE_400, COL_SLATE_500
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=1.6, zorder=4))
ax.text(x + w * 0.5, y + h * 0.5, text, ha="center", va="center",
fontsize=8.3, color=tcol, weight="bold", zorder=5)
def _pq_struct_box(ax, x, y, w, h, label, *, target=False):
if target:
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 2.8
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x + w * 0.5, y + h * 0.5, label, ha="center", va="center",
fontsize=10, color=tcol, weight="bold", zorder=5)
def _pq_algo_box(ax, x, y, w, h, algo, big_o, *, target=False, inplace=False):
if target:
fc, ec, algo_col = COL_AMBER_100, COL_ACCENT, COL_AMBER_700
o_col = COL_AMBER_700
else:
fc, ec, algo_col = COL_BG, COL_PRIMARY, COL_TEXT
o_col = COL_AMBER_600 if "²" in big_o else COL_PRIMARY
lw = 2.8 if target else 1.8
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x + w * 0.5, y + h * 0.60, algo, ha="center", va="center",
fontsize=10, color=algo_col, weight="bold", zorder=5)
ax.text(x + w * 0.5, y + h * 0.24, big_o, ha="center", va="center",
fontsize=9.5, color=o_col, weight="bold", zorder=5)
if inplace:
bw, bh = 1.18, 0.34
bx, by = x + w - bw - 0.06, y + h - bh - 0.05
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=COL_AMBER_700, ec=COL_AMBER_700, linewidth=1.0, zorder=6))
ax.text(bx + bw * 0.5, by + bh * 0.5, "IN-PLACE", ha="center",
va="center", fontsize=7.6, color=COL_WHITE, weight="bold",
zorder=7)
# ---- Motor bağlantısı: PQ sort tarifinin canlı kanıtı (veri MOTORDAN) ----
_pq_src = [4, 1, 7, 3, 9, 2, 6]
_pq_Q = []
for _x in _pq_src:
heap_insert(_pq_Q, _x)
_pq_drain = [heap_delete_max(_pq_Q) for _ in range(len(_pq_src))]
assert _pq_drain == sorted(_pq_src, reverse=True) == [9, 7, 6, 4, 3, 2, 1]
assert _pq_Q == []
fig, ax = plt.subplots(figsize=(10.5, 6.8))
fig.patch.set_facecolor(COL_WHITE)
top_x, top_w, top_h = 0.0, 13.6, 1.40
top_y = 0.0
ax.add_patch(FancyBboxPatch(
(top_x, top_y), top_w, top_h,
boxstyle="round,pad=0.04,rounding_size=0.14",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.4, zorder=2))
ax.text(top_x + top_w * 0.5, top_y + top_h * 0.74,
"Öncelik kuyruğu sıralaması (PQ sort) — TEK tarif",
ha="center", va="center", fontsize=12, color=COL_TEXT,
weight="bold", zorder=5)
ax.text(top_x + top_w * 0.5, top_y + top_h * 0.34,
"tüm öğeleri insert et → sonra hepsini delete_max ile çek "
"(çekiş sırası = AZALAN sıralı)",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
arr_x = top_x + top_w * 0.5
ax.add_patch(FancyArrowPatch(
(arr_x, top_y - 0.02), (arr_x, top_y - 0.62),
arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_600,
linewidth=2.4, zorder=5))
ax.text(arr_x + 0.18, top_y - 0.34,
"PQ'yu hangi yapı uygularsa o sıralama doğar",
ha="left", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic", zorder=5)
struct_x, struct_w = 0.0, 3.55
cost_x = struct_x + struct_w + 0.45
cost_w = 3.55
algo_x = cost_x + cost_w + 0.45
algo_w = 4.55
head_y = top_y - 1.10
ax.text(struct_x + struct_w * 0.5, head_y, "VERİ YAPISI (PQ)",
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.text(cost_x + cost_w * 0.5, head_y, "insert / delete_max",
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=5)
ax.text(algo_x + algo_w * 0.5, head_y, "DOĞAN SIRALAMA",
ha="center", va="center", fontsize=9.5, color=COL_PRIMARY,
weight="bold", zorder=5)
rows = [
("sırasız dizi", "O(1)", "O(n)", "Selection Sort", "O(n²)", False, False),
("sıralı dizi", "O(n)", "O(1)", "Insertion Sort", "O(n²)", False, False),
("küme AVL ağacı", "O(log n)", "O(log n)", "AVL Sort", "O(n log n)", False, False),
("İKİLİ YIĞIN", "O(log n)", "O(log n)", "HEAPSORT", "O(n log n)", True, True),
]
row_h = 0.92
row_gap = 0.30
first_row_top = head_y - 0.42
badge_w, badge_h = 1.58, 0.50
row_y = []
for r, (struct, c_ins, c_del, algo, big_o, target, inplace) in enumerate(rows):
y = first_row_top - row_h - r * (row_h + row_gap)
row_y.append(y)
if target:
ax.add_patch(FancyBboxPatch(
(struct_x - 0.22, y - 0.22),
(algo_x + algo_w) - (struct_x - 0.22) + 0.22,
row_h + 0.44,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc="none", ec=COL_ACCENT, linewidth=2.2, zorder=1,
linestyle=(0, (5, 2))))
_pq_struct_box(ax, struct_x, y, struct_w, row_h, struct, target=target)
ax.add_patch(FancyArrowPatch(
(struct_x + struct_w + 0.04, y + row_h * 0.5),
(cost_x - 0.06, y + row_h * 0.5),
arrowstyle="-|>", mutation_scale=12,
color=COL_ACCENT if target else COL_SLATE_400,
linewidth=2.0 if target else 1.4, zorder=3))
hot_ins = c_ins == "O(log n)"
hot_del = c_del == "O(log n)"
bx1 = cost_x + 0.04
bx2 = cost_x + cost_w - badge_w - 0.04
by = y + (row_h - badge_h) * 0.5
ax.text(bx1 + badge_w * 0.5, by + badge_h + 0.16, "insert",
ha="center", va="center", fontsize=7.2, color=COL_SLATE_500,
zorder=5)
ax.text(bx2 + badge_w * 0.5, by + badge_h + 0.16, "delete_max",
ha="center", va="center", fontsize=7.2, color=COL_SLATE_500,
zorder=5)
_pq_cost_badge(ax, bx1, by, badge_w, badge_h, c_ins, hot=hot_ins)
_pq_cost_badge(ax, bx2, by, badge_w, badge_h, c_del, hot=hot_del)
ax.add_patch(FancyArrowPatch(
(cost_x + cost_w + 0.04, y + row_h * 0.5),
(algo_x - 0.06, y + row_h * 0.5),
arrowstyle="-|>", mutation_scale=12,
color=COL_ACCENT if target else COL_SLATE_400,
linewidth=2.0 if target else 1.4, zorder=3))
_pq_algo_box(ax, algo_x, y, algo_w, row_h, algo, big_o,
target=target, inplace=inplace)
for r in range(len(rows) - 1):
sep_y = (row_y[r] - 0.22 + row_y[r + 1] + row_h + 0.22) * 0.5
ax.plot([struct_x - 0.22, algo_x + algo_w],
[sep_y, sep_y], color=COL_SLATE_400, linewidth=0.8,
linestyle=(0, (2, 3)), zorder=0)
note_y = row_y[-1] - 0.62
ax.text((struct_x + algo_x + algo_w) * 0.5, note_y,
"Aynı çerçeve, farklı yapı = farklı sıralama. Hedef: satır 4 — "
"n log n VE yerinde (ek bellek yok).",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text((struct_x + algo_x + algo_w) * 0.5, note_y - 0.40,
"dizi PQ'lar (satır 1-2) bir işlemi ucuz yapar AMA diğerini O(n)'e "
"iter → O(n²); yığın iki işlemi de O(log n) dengeler → O(n log n)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=5)
fig.suptitle(
"Öncelik kuyruğu sıralaması — birleştirici çerçeve: yapı seçimi sıralama algoritmasını belirler",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.set_xlim(struct_x - 0.55, algo_x + algo_w + 0.55)
ax.set_ylim(note_y - 0.85, top_y + top_h + 0.30)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 5. Hedef: n log n + Yerinde (Complete Binary Tree) {#sec-5-hedef-n-log}
In-place olmak için, $n$ öğeyi tam $n$ dizi gözünde tutmalıyız. $\log n$ performans için de bir **ağaç** gerekir. Çözüm: ağacı bir **diziye gömmek**. Hangi ağaç? **Complete binary tree (tam ikili ağaç)**: her $i$. derinlikte $2^i$ düğüm, *son* seviye hariç; son seviye **sola yaslı (left-justified)**.
> *"these two properties together is what I call a complete binary tree."* — Demaine, 17:10
Complete binary tree her zaman dengelidir — yüksekliği tam **$\lceil \log n \rceil$** (mümkün olan en iyi). Rotasyona gerek yoktur.
## 6. Complete Binary Tree ↔ Dizi {#sec-6-complete-binary-tree}
Tam ikili ağaç ile dizi arasında bir **birebir eşleme (bijection)** vardır: düğümleri **derinlik sırasında** (level order — A, sonra B, C, sonra D, E, F, G...) diziye yaz. $n$ verilince tek bir ağaç şekli vardır (yukarıdan aşağı, soldan sağa dolar).
> *"between complete binary trees and arrays is a bijection."* — Demaine, 18:33
Bu yüzden işaretçi saklamaya gerek yok — sadece dizi: **örtük veri yapısı (implicit data structure)**.
> *"This is what we call an implicit data structure... no pointers, just an array of the n items."* — Demaine, 20:28
**Çalışılan Örnek — index aritmetiği.** İşaretçileri index hesabıyla bul. $i$. düğüm için:
- Sol çocuk: $2i + 1$.
- Sağ çocuk: $2i + 2$ (sol çocuğun sağ kardeşi).
- Parent ($j$ çocuksa): $(j - 1) // 2$ (tamsayı bölme).
Örnek: index 4'teki düğümün sol çocuğu $2 \cdot 4 + 1 = 9$; sağ çocuğu $2 \cdot 4 + 2 = 10$ — dizi boyutunu aşıyorsa o çocuk yoktur. Ters yön de tutarlı: $\text{parent}(9) = (9 - 1) // 2 = 4$. Tüm bunlar sabit zaman; complete binary tree'nin özel yapısı sayesinde mümkün.
@fig-complete-tree-array bu bijeksiyonu somutlar: 11 düğümlü bir max-heap, hem ağaç hem dizi olarak; index 4 düğümü amber dolgu, çocukları 9 ve 10 amber çerçeve, formül kutusunda $\text{left}(4) = 9$, $\text{right}(4) = 10$, $\text{parent}(9) = 4$ doğrulanır.
```{python}
#| label: fig-complete-tree-array
#| fig-cap: "Complete binary tree ⟷ dizi: işaretçisiz örtük yapı (L8 §5-6, İMZA figür). Üst: 11 düğümlü complete binary tree, 4 düzey, son düzey SOLA YASLI (etiketli); her düğüm dairesinde değer, yanında index rozeti (i=0..10). Alt: aynı 11 değerin dizi şeridi (her hücre altında index). Her ağaç düğümünden dizi hücresine ince bağ çizgisi (level-order bijeksiyon). index 4 düğümü amber DOLGU; çocukları index 9 ve 10 amber ÇERÇEVE; sağda formül kutusu: left(4) = 2·4+1 = 9, right(4) = 2·4+2 = 10, parent(9) = (9−1)//2 = 4, parent(10) = (10−1)//2 = 4. Düğüm bağları YALNIZ index aritmetiğiyle bulunur — işaretçi (next/left/right) YOK. Yükseklik = ⌈log n⌉ → işlemler O(log n); ağaç dolu ve sola yaslı → dengeleme rotasyonu gerekmez (BST/AVL aksine). Motor: build_heap_linear([25,16,21,5,12,18,19,1,3,9,7]) zaten max-heap; is_max_heap True; heap_left(4)=9, heap_right(4)=10, heap_parent(9)=4, heap_parent(10)=4 (Demaine 20:28)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-complete-tree-array (L8 §5-6 İMZA): complete tree ⟷ dizi bijeksiyon + index
# aritmetiği. Veri MOTORDAN (build_heap_linear / is_max_heap / heap_left/right/parent).
_CT_R = 0.34
_CT_CELL_W = 1.00
_CT_CELL_H = 0.78
def _ct_depth_of(i):
return int(math.log2(i + 1))
def _ct_tree_coords(n, x_left, x_right, y_top, y_gap):
coords = {}
span = x_right - x_left
for i in range(n):
d = _ct_depth_of(i)
slots = 2 ** d
col = i - (2 ** d - 1)
x = x_left + (col + 0.5) / slots * span
y = y_top - d * y_gap
coords[i] = (x, y)
return coords
def _ct_array_coords(n, x0, y_strip):
return {i: (x0 + (i + 0.5) * _CT_CELL_W, y_strip + _CT_CELL_H * 0.5)
for i in range(n)}
_ct_raw = [25, 16, 21, 5, 12, 18, 19, 1, 3, 9, 7]
Q = build_heap_linear(list(_ct_raw))
assert Q == _ct_raw
n = len(Q)
assert is_max_heap(Q) and n == 11
i_sel = 4
l_sel = heap_left(i_sel)
r_sel = heap_right(i_sel)
assert l_sel == 9 and r_sel == 10
assert heap_parent(l_sel) == i_sel and heap_parent(r_sel) == i_sel
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
x_left, x_right = 0.0, 11.0
y_top = 0.0
y_gap = 1.35
max_depth = _ct_depth_of(n - 1)
y_strip = y_top - (max_depth + 1) * y_gap - 0.70
tc = _ct_tree_coords(n, x_left, x_right, y_top, y_gap)
ac = _ct_array_coords(n, x_left, y_strip)
highlight_frame = {l_sel, r_sel}
highlight_fill = {i_sel}
for i in range(n):
tx, ty = tc[i]
axx, ayy = ac[i]
on_hot = i in highlight_frame or i in highlight_fill
ax.plot([tx, axx], [ty - _CT_R, ayy + _CT_CELL_H * 0.5],
color=COL_AMBER_600 if on_hot else COL_SLATE_400,
linewidth=1.4 if on_hot else 0.7,
alpha=0.9 if on_hot else 0.45,
linestyle=(0, (2, 2)), zorder=0)
for i in range(n):
for c in (heap_left(i), heap_right(i)):
if c < n:
px, py = tc[i]
cx, cy = tc[c]
hot = (i == i_sel)
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=2.8 if hot else 1.5,
zorder=2 if hot else 1, solid_capstyle="round")
for i in range(n):
x, y = tc[i]
if i in highlight_fill:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 3.0, COL_AMBER_700
elif i in highlight_frame:
fc, ec, lw, tcol = COL_BG, COL_ACCENT, 3.0, COL_TEXT
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.7, COL_TEXT
ax.add_patch(Circle((x, y), _CT_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, str(Q[i]), ha="center", va="center",
fontsize=12, color=tcol, weight="bold", zorder=6)
badge_col = COL_AMBER_700 if (i in highlight_frame or i in highlight_fill) else COL_SLATE_500
ax.text(x + _CT_R + 0.06, y + _CT_R - 0.02, f"i={i}", ha="left", va="bottom",
fontsize=7.5, color=badge_col,
weight="bold" if (i in highlight_frame or i in highlight_fill) else "normal",
zorder=7)
for i in range(n):
x = x_left + i * _CT_CELL_W
if i in highlight_fill:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
elif i in highlight_frame:
fc, ec, lw, tcol = COL_BG, COL_ACCENT, 2.6, COL_TEXT
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.5, COL_TEXT
ax.add_patch(FancyBboxPatch(
(x, y_strip), _CT_CELL_W * 0.92, _CT_CELL_H, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=3))
cx = x + _CT_CELL_W * 0.46
ax.text(cx, y_strip + _CT_CELL_H * 0.5, str(Q[i]), ha="center", va="center",
fontsize=11.5, color=tcol, weight="bold", zorder=5)
ax.text(cx, y_strip - 0.20, str(i), ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, zorder=5)
ax.text(x_left - 0.45, y_strip + _CT_CELL_H * 0.5, "Q[ ]", ha="right", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5)
last_level_first = 2 ** max_depth - 1
last_filled = n - 1
lx, _ct_ly0 = tc[last_level_first]
rx, ly = tc[last_filled]
ax.annotate(
"son düzey SOLA YASLI\n(slotlar soldan dolar — sağ uç boş)",
xy=((lx + rx) * 0.5, ly - _CT_R - 0.05),
xytext=((lx + rx) * 0.5, ly - _CT_R - 0.78),
ha="center", va="center", fontsize=8.5, color=COL_AMBER_700,
weight="bold", linespacing=1.3, zorder=8,
arrowprops=dict(arrowstyle="-|>", color=COL_AMBER_700, linewidth=1.6,
shrinkA=2, shrinkB=4))
box_x, box_y = x_right + 0.55, y_top - 1.05
box_w, box_h = 4.55, 2.70
ax.add_patch(FancyBboxPatch(
(box_x, box_y - box_h), box_w, box_h,
boxstyle="round,pad=0.06,rounding_size=0.12",
fc=COL_BG, ec=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(box_x + box_w * 0.5, box_y - 0.36,
"index aritmetiği (i = 4)", ha="center", va="center",
fontsize=10.5, color=COL_AMBER_700, weight="bold", zorder=6)
lines = [
("left(4) = 2·4 + 1", f"= {l_sel}"),
("right(4) = 2·4 + 2", f"= {r_sel}"),
("parent(9) = (9−1) // 2", f"= {heap_parent(l_sel)}"),
("parent(10)= (10−1) // 2", f"= {heap_parent(r_sel)}"),
]
ly0 = box_y - 0.86
for k, (lhs, rhs) in enumerate(lines):
yk = ly0 - k * 0.44
ax.text(box_x + 0.24, yk, lhs, ha="left", va="center",
fontsize=10, color=COL_TEXT, family="monospace", zorder=6)
ax.text(box_x + box_w - 0.24, yk, rhs, ha="right", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold",
family="monospace", zorder=6)
fig.suptitle(
"Complete binary tree ⟷ dizi: işaretçisiz örtük yapı (yığın saklama)",
color=COL_TEXT, fontsize=13, weight="bold", y=0.975)
ax.text((x_left + x_right) * 0.5, y_top + 0.62,
"düğüm bağları YALNIZ index aritmetiğiyle bulunur — işaretçi (next/left/right) YOK",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=8)
ax.text((x_left + x_right) * 0.5 + 1.0, y_strip - 0.70,
"yükseklik = ⌈log n⌉ → işlemler O(log n) · ağaç DOLU ve sola yaslı → "
"dengeleme ROTASYONU GEREKMEZ (BST/AVL aksine) · (Demaine 20:28)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=8)
ax.set_xlim(x_left - 0.9, box_x + box_w + 0.6)
ax.set_ylim(y_strip - 1.15, y_top + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 7. Max-Heap Özelliği {#sec-7-max-heap-ozelligi}
Son bir kural: **max-heap özelliği** — her düğüm $i$ için $Q[i].\text{key} \ge Q[j].\text{key}$ ($j$ sol veya sağ çocuk). Yani her düğüm iki çocuğundan da büyük-eşittir; iki çocuğun birbirine göre sırası *umursanmaz* (BST'den farkı budur).
> *"the max-heap property: Q[i] is greater than or equal to Q[j] for both children."* — Demaine, 26:02
Önemli lemma: bu özellik her yerde sağlanıyorsa, her düğüm **alt ağacındaki tüm düğümlerden** büyük-eşittir (geçişlilikle: aşağı yolda her kenar anahtarı azaltmaz). Dolayısıyla **maksimum kökte** durur.
> *"every node i is greater than or equal to all nodes in its subtree."* — Demaine, 27:39
## 8. insert ve max_heapify_up {#sec-8-insert-ve-max}
insert(x): yeni öğeyi yalnızca dizinin **sonuna** ekleyebiliriz (son yaprak, $\text{index} = \text{size} - 1$). Ama bu max-heap özelliğini bozabilir → düzelt.
**Çalışılan Örnek — max_heapify_up.** Eklenen düğümden başla. Parent'ının anahtarı çocuktan küçükse (kural ihlali), ikisini **takas et**; sonra parent ile **özyinele** (yukarı çık). Öğe en fazla kök seviyesine kadar "kabarır". Yalnızca bu tek öğe yanlış yerde olduğundan, hareket durduğunda max-heap özelliği sağlanmıştır.
> *"max_heapify_up... it goes up one... the running time is the height of the tree, which is log n."* — Demaine, 36:06
Süre: ağaç yüksekliği = **$O(\log n)$**.
@fig-heapify-up bu kabarmayı somut bir örnekte gösterir: $[9, 5, 8, 3, 1]$ yığınına 10 eklenir; 10 sona (index 5) konur, parent 8'den büyük olduğu için takas edilir (index 2), sonra parent 9'dan da büyük olduğu için bir kez daha takas edilir — toplam 2 kabarma — ve 10 köke ulaşır.
```{python}
#| label: fig-heapify-up
#| fig-cap: "insert + kabarma (heapify_up): yeni öğe sona eklenir, parent'ından büyükçe yukarı süzülür (L8 §8). Üç panel yan yana; her panel: yığının complete-tree çizimi (6 düğüm) + altında o anki dizi şeridi. Motor izi heapify_up_trace([9,5,8,3,1], 10): **(1) 10 SONA eklenir** index 5 (tek geçerli yer) → dizi [9,5,8,3,1,10]; parent index 2 = 8 < 10 → İHLAL, kabarma gerekir. **(2) 8 ↔ 10 takas** → 10 yukarı index 2; dizi [9,5,10,3,1,8]; parent index 0 = 9 < 10 → hâlâ İHLAL. **(3) 9 ↔ 10 takas** → 10 KÖKTE index 0; dizi [10,5,9,3,1,8]; max-heap ONARILDI. Kabaran öğe 10 amber dolgu; İHLAL eden kenar amber + 'İHLAL' etiketi. Her takas en fazla bir seviye çıkar → takas sayısı (2) ≤ ağaç derinliği = O(log n). Motor: final kök = 10, is_max_heap(final) True (Demaine 36:06)."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-heapify-up (L8 §8): insert(10) kabarma izi, 3 panel.
# Veri MOTORDAN (heapify_up_trace([9,5,8,3,1],10) / is_max_heap / heap_parent).
_HU_R = 0.34
_HU_Y_GAP = 1.25
_HU_NODE_X = {0: 1.5, 1: 0.5, 2: 2.5, 3: 0.0, 4: 1.0, 5: 2.0}
_HU_NODE_DEPTH = {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 2}
def _hu_coords(idx, x_off, y_top):
return x_off + _HU_NODE_X[idx], y_top - _HU_NODE_DEPTH[idx] * _HU_Y_GAP
def _hu_draw_tree(ax, arr, x_off, y_top, *, fill_idx=None, violation_edge=None):
nn = len(arr)
for i in range(nn):
for c in (heap_left(i), heap_right(i)):
if c < nn:
px, py = _hu_coords(i, x_off, y_top)
cx, cy = _hu_coords(c, x_off, y_top)
hot = (violation_edge is not None and violation_edge == (i, c))
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.6,
zorder=2 if hot else 1, solid_capstyle="round")
if hot:
mx, my = (px + cx) * 0.5, (py + cy) * 0.5
ax.text(mx - 0.30, my, "İHLAL", ha="right", va="center",
fontsize=8.0, color=COL_AMBER_700, weight="bold",
style="italic", zorder=9)
for i in range(nn):
x, y = _hu_coords(i, x_off, y_top)
if fill_idx is not None and i == fill_idx:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700
else:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.7, COL_TEXT
ax.add_patch(Circle((x, y), _HU_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y, str(arr[i]), ha="center", va="center",
fontsize=12, color=tcol, weight="bold", zorder=6)
def _hu_strip(ax, arr, x_off, y_strip, *, hot_idx=None, tag=None):
sw = 0.66
for k, v in enumerate(arr):
x = x_off + k * sw
hot = (hot_idx is not None and k == hot_idx)
ax.add_patch(FancyBboxPatch(
(x, y_strip), sw * 0.86, 0.50, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.4 if hot else 1.3, zorder=3))
ax.text(x + sw * 0.43, y_strip + 0.25, str(v), ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700 if hot else COL_TEXT,
weight="bold", zorder=5)
ax.text(x + sw * 0.43, y_strip - 0.20, str(k), ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, zorder=5)
if tag is not None:
ax.text(x_off + len(arr) * sw * 0.5 - sw * 0.07, y_strip - 0.50, tag,
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=5)
def _hu_title(ax, x_center, y_title, text, sub=None):
ax.text(x_center, y_title, text, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=10)
if sub is not None:
ax.text(x_center, y_title - 0.38, sub, ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=10)
_hu_tr = heapify_up_trace([9, 5, 8, 3, 1], 10)
_hu_states = _hu_tr["states"]
assert [s["array"] for s in _hu_states] == [
[9, 5, 8, 3, 1, 10], [9, 5, 10, 3, 1, 8], [10, 5, 9, 3, 1, 8]]
assert _hu_tr["final"] == [10, 5, 9, 3, 1, 8] and _hu_tr["final"][0] == 10
assert is_max_heap(_hu_tr["final"])
assert [s["pos"] for s in _hu_states] == [5, 2, 0]
arr0, arr1, arr2 = (s["array"] for s in _hu_states)
pos0, pos1, pos2 = (s["pos"] for s in _hu_states)
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
panel_span = 2.5
gap_between = 1.7
x_off1 = 0.0
x_off2 = panel_span + gap_between
x_off3 = 2 * (panel_span + gap_between)
y_top = 0.0
cx1 = x_off1 + 1.25
cx2 = x_off2 + 1.25
cx3 = x_off3 + 1.25
y_title = y_top + 1.55
y_note = y_top + 0.72
y_strip = y_top - 2 * _HU_Y_GAP - 1.05
p0 = heap_parent(pos0)
_hu_draw_tree(ax, arr0, x_off1, y_top, fill_idx=pos0, violation_edge=(p0, pos0))
_hu_title(ax, cx1, y_title, "1) 10 SONA eklenir", sub=f"index {pos0} (tek geçerli yer)")
ax.text(cx1, y_note, f"parent {arr0[p0]} < 10 → İHLAL\nkabarma gerekir",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=10, linespacing=1.3)
_hu_strip(ax, arr0, x_off1, y_strip, hot_idx=pos0, tag="heap dizisi (10 → index 5)")
p1 = heap_parent(pos1)
_hu_draw_tree(ax, arr1, x_off2, y_top, fill_idx=pos1, violation_edge=(p1, pos1))
_hu_title(ax, cx2, y_title, "2) 8 ↔ 10 takas", sub=f"10 yukarı → index {pos1}")
ax.text(cx2, y_note, f"parent {arr1[p1]} < 10 → hâlâ İHLAL\nbir kez daha kabar",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=10, linespacing=1.3)
_hu_strip(ax, arr1, x_off2, y_strip, hot_idx=pos1, tag="8 ile yer değiştirdi")
_hu_draw_tree(ax, arr2, x_off3, y_top, fill_idx=pos2)
_hu_title(ax, cx3, y_title, "3) 9 ↔ 10 takas", sub=f"10 KÖKTE → index {pos2}")
ax.add_patch(FancyBboxPatch(
(cx3 - 1.30, y_note - 0.22), 2.6, 0.44,
boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=9))
ax.text(cx3, y_note, "max-heap ONARILDI ✓", ha="center", va="center",
fontsize=8.6, color=COL_AMBER_700, weight="bold", zorder=10)
_hu_strip(ax, arr2, x_off3, y_strip, hot_idx=pos2, tag="9 ile yer değiştirdi")
for sep_x in (x_off1 + panel_span + gap_between * 0.5,
x_off2 + panel_span + gap_between * 0.5):
ax.plot([sep_x, sep_x], [y_strip - 0.6, y_title + 0.3],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"insert + kabarma (heapify_up): yeni öğe sona eklenir, "
"parent'ından büyükçe yukarı süzülür",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.text((x_off1 + x_off3 + panel_span) * 0.5, y_strip - 1.00,
"her takas en fazla bir seviye çıkar → takas sayısı ≤ ağaç derinliği "
"= O(log n) (Demaine 36:06)",
ha="center", va="center", fontsize=8.8, color=COL_SLATE_500,
style="italic", zorder=10)
ax.set_xlim(x_off1 - 0.7, x_off3 + panel_span + 0.7)
ax.set_ylim(y_strip - 1.35, y_title + 0.55)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 9. delete_max ve max_heapify_down {#sec-9-delete-max-ve}
delete_max: maksimum kökte (index 0), ama dizide yalnızca **son** öğeyi verimli silebiliriz. Çözüm: kökü son yaprakla **takas et**, son öğeyi sil (delete_last). Şimdi köke küçük bir değer geldi → düzelt.
**max_heapify_down:** kökten başla; iki çocuktan **büyüğüyle** takas et (böylece her iki kenar da kuralı sağlar), sonra o çocukta özyinele (aşağı in). Yaprağa ulaşınca dur.
> *"Heapify down. We're going to take that item and push it down... until max-heap property is satisfied."* — Demaine, 39:16
Süre yine **$O(\log n)$**. (Yığında hiç rotasyon yok — yalnızca takas.)
@fig-heapify-down bu süzmeyi gösterir: $[10, 9, 8, 3, 1, 5]$ yığınında max 10 kökte; kök son yaprak 5 ile takas edilip 10 silinir; köke gelen 5, iki çocuk 9 ve 8'in büyüğü olan 9 ile takas edilir (1 süzme) ve kök 9 olur — final $[9, 5, 8, 3, 1]$, hâlâ max-heap.
```{python}
#| label: fig-heapify-down
#| fig-cap: "delete_max → aşağı süzme (heapify_down): kök↔son takas, sil, büyük çocukla süz (L8 §9, İMZA figür). Üç panel soldan sağa; motor izi heapify_down_trace([10,9,8,3,1,5]). **(1) max kökte** — kök 10 + son yaprak 5 amber dolgu, aralarında çift yönlü takas oku; max = 10 (yalnız kökte), son yaprak 5 yukarı taşınır; dizi-gömme sol 2i+1 · sağ 2i+2. **(2) son öğe silindi → İHLAL** — 10 çıkarıldı (soluk düğüm + dışarı ok), 5 kökte ama sol çocuk 9 > 5 → yığın özelliği bozuldu (kalın slate çerçeve); ara dizi [5,9,8,3,1]. **(3) büyük çocukla takas → aşağı süz** — 5 ↔ 9 takası (iki çocuk 9 ve 8'in BÜYÜĞÜ 9 seçilir, böylece her iki kenar da kuralı sağlar); final [9,5,8,3,1], 9 kök, ONARILDI. En fazla yükseklik kadar takas = O(log n); rotasyon YOK, yalnız takas. Motor: removed_max = 10, final kök = 9, is_max_heap(final) True (Demaine 39:16)."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-heapify-down (L8 §9 İMZA): delete_max süzme izi, 3 panel.
# Veri MOTORDAN (heapify_down_trace([10,9,8,3,1,5]) / is_max_heap / heap_left).
_HD_R = 0.34
_HD_Y_GAP = 1.30
_HD_NODE_XY = {
0: (1.50, 0.0),
1: (0.75, -_HD_Y_GAP),
2: (2.25, -_HD_Y_GAP),
3: (0.375, -2 * _HD_Y_GAP),
4: (1.125, -2 * _HD_Y_GAP),
5: (1.875, -2 * _HD_Y_GAP),
}
def _hd_coords(idx, x_off, y_top):
bx, by = _HD_NODE_XY[idx]
return x_off + bx, y_top + by
def _hd_edges(nn):
edges = []
for i in range(nn):
for c in (heap_left(i), heap_right(i)):
if c < nn:
edges.append((i, c))
return edges
def _hd_draw_heap(ax, arr, x_off, y_top, *,
fill_idx=None, frame_idx=None, faded_idx=None, hot_edges=None):
fill_idx = set(fill_idx or [])
frame_idx = set(frame_idx or [])
faded_idx = set(faded_idx or [])
hot_edges = set(hot_edges or [])
nn = len(arr)
for (pa, ch) in _hd_edges(nn):
px, py = _hd_coords(pa, x_off, y_top)
cx, cy = _hd_coords(ch, x_off, y_top)
faded = pa in faded_idx or ch in faded_idx
hot = frozenset((pa, ch)) in hot_edges
ax.plot([px, cx], [py, cy],
color=COL_ACCENT if hot else COL_SLATE_400,
linewidth=3.0 if hot else 1.6,
alpha=0.30 if faded else 1.0,
zorder=2 if hot else 1, solid_capstyle="round")
for idx in range(nn):
x, y = _hd_coords(idx, x_off, y_top)
if idx in faded_idx:
fc, ec, lw, tcol, al = COL_WHITE, COL_SLATE_400, 1.4, COL_SLATE_400, 0.45
elif idx in fill_idx:
fc, ec, lw, tcol, al = COL_AMBER_100, COL_ACCENT, 2.8, COL_AMBER_700, 1.0
elif idx in frame_idx:
fc, ec, lw, tcol, al = COL_WHITE, COL_PRIMARY, 3.2, COL_TEXT, 1.0
else:
fc, ec, lw, tcol, al = COL_BG, COL_PRIMARY, 1.6, COL_TEXT, 1.0
ax.add_patch(Circle((x, y), _HD_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5, alpha=al))
ax.text(x, y, str(arr[idx]), ha="center", va="center",
fontsize=12, color=tcol, weight="bold", zorder=6, alpha=al)
def _hd_swap_arrow(ax, idx_a, idx_b, x_off, y_top, label, *, color=COL_AMBER_700,
rad=0.32, lab_dx=-0.62, lab_dy=0.0, lab_ha="right"):
ax_, ay_ = _hd_coords(idx_a, x_off, y_top)
bx_, by_ = _hd_coords(idx_b, x_off, y_top)
ax.add_patch(FancyArrowPatch(
(ax_, ay_), (bx_, by_), arrowstyle="<|-|>", mutation_scale=15,
color=color, linewidth=2.6, zorder=8,
shrinkA=_HD_R * 60, shrinkB=_HD_R * 60,
connectionstyle=f"arc3,rad={rad}"))
mx, my = (ax_ + bx_) * 0.5, (ay_ + by_) * 0.5
ax.text(mx + lab_dx, my + lab_dy, label, ha=lab_ha, va="center",
fontsize=8.5, color=color, weight="bold", zorder=9)
def _hd_strip(ax, values, x_off, y_strip, *, highlight=None, tag=None):
highlight = set(highlight or [])
sw = 0.60
for k, v in enumerate(values):
x = x_off + k * sw
hot = k in highlight
ax.add_patch(FancyBboxPatch(
(x, y_strip), sw * 0.86, 0.46, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if hot else COL_BG,
ec=COL_ACCENT if hot else COL_PRIMARY,
linewidth=2.2 if hot else 1.3, zorder=3))
ax.text(x + sw * 0.43, y_strip + 0.23, str(v), ha="center", va="center",
fontsize=9, color=COL_TEXT, weight="bold", zorder=5)
ax.text(x + sw * 0.43, y_strip - 0.18, str(k), ha="center", va="center",
fontsize=7, color=COL_SLATE_500, zorder=5)
if tag is not None:
ax.text(x_off + len(values) * sw * 0.5 - sw * 0.07, y_strip - 0.50, tag,
ha="center", va="center", fontsize=8, color=COL_SLATE_500,
style="italic", zorder=5)
def _hd_title(ax, x_center, y_title, text, sub=None):
ax.text(x_center, y_title, text, ha="center", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=10)
if sub is not None:
ax.text(x_center, y_title - 0.38, sub, ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=10)
_hd_src = [10, 9, 8, 3, 1, 5]
_hd_tr = heapify_down_trace(_hd_src)
removed = _hd_tr["removed_max"]
_hd_arrs = [s["array"] for s in _hd_tr["states"]]
assert removed == 10
assert _hd_arrs[0] == [5, 9, 8, 3, 1] and _hd_arrs[-1] == [9, 5, 8, 3, 1]
assert _hd_tr["final"] == [9, 5, 8, 3, 1] and _hd_tr["final"][0] == 9
assert is_max_heap(_hd_tr["final"]) and len(_hd_arrs) == 2
p1_arr = list(_hd_src)
p2_arr = list(_hd_arrs[0])
p3_arr = list(_hd_tr["final"])
fig, ax = plt.subplots(figsize=(11.0, 6.4))
fig.patch.set_facecolor(COL_WHITE)
panel_span = 2.7
gap_between = 1.55
x_off1 = 0.0
x_off2 = panel_span + gap_between
x_off3 = 2 * (panel_span + gap_between)
y_top = 0.0
cx1 = x_off1 + 1.50
cx2 = x_off2 + 1.50
cx3 = x_off3 + 1.50
y_title = y_top + 1.70
y_strip = y_top - 2 * _HD_Y_GAP - 1.05
_hd_draw_heap(ax, p1_arr, x_off1, y_top, fill_idx={0, len(p1_arr) - 1})
_hd_swap_arrow(ax, 0, len(p1_arr) - 1, x_off1, y_top, "takas",
rad=0.45, lab_dx=0.70, lab_dy=0.30, lab_ha="left")
_hd_title(ax, cx1, y_title, "1) max kökte — kök ↔ son yaprak takası",
sub=f"max = {removed} (yalnız kökte) · son yaprak {p1_arr[-1]} yukarı taşınır")
_hd_strip(ax, p1_arr, x_off1, y_strip, highlight={0, len(p1_arr) - 1},
tag="dizi-gömme (sol 2i+1 · sağ 2i+2)")
_hd_draw_heap(ax, p2_arr, x_off2, y_top, frame_idx={0},
hot_edges={frozenset((0, heap_left(0)))})
rx, ry = _hd_coords(0, x_off2, y_top)
ax.add_patch(FancyArrowPatch(
(rx + _HD_R + 0.05, ry + _HD_R + 0.05), (rx + 1.35, ry + 0.95),
arrowstyle="-|>", mutation_scale=14, color=COL_AMBER_600,
linewidth=2.0, zorder=8, connectionstyle="arc3,rad=0.25"))
ax.add_patch(Circle((rx + 1.55, ry + 1.05), _HD_R * 0.78,
facecolor=COL_WHITE, edgecolor=COL_SLATE_400,
linewidth=1.6, zorder=8, linestyle=(0, (3, 2))))
ax.text(rx + 1.55, ry + 1.05, str(removed), ha="center", va="center",
fontsize=10, color=COL_SLATE_500, weight="bold", zorder=9)
ax.text(rx + 1.55, ry + 1.05 + _HD_R * 0.78 + 0.14, "çıkarıldı",
ha="center", va="bottom", fontsize=7.5, color=COL_SLATE_500,
style="italic", zorder=9)
_hd_title(ax, cx2, y_title, "2) son öğe silindi → yığın İHLAL",
sub=f"kök {p2_arr[0]} < sol çocuk {p2_arr[heap_left(0)]} · özellik bozuldu")
_hd_strip(ax, p2_arr, x_off2, y_strip, highlight={0}, tag="kök yeni · henüz süzülmedi")
_hd_draw_heap(ax, p3_arr, x_off3, y_top, fill_idx={0},
hot_edges={frozenset((0, heap_left(0)))})
_hd_swap_arrow(ax, 0, heap_left(0), x_off3, y_top, "büyük çocukla\ntakas",
color=COL_AMBER_700, rad=-0.30, lab_dx=0.95, lab_dy=0.15, lab_ha="left")
_hd_title(ax, cx3, y_title, "3) büyük çocukla takas → aşağı süz",
sub="iki çocuğun BÜYÜĞÜ seçilir · yığın onarıldı")
ax.add_patch(FancyBboxPatch(
(cx3 - 1.10, y_title - 0.90), 2.2, 0.42,
boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=9))
ax.text(cx3, y_title - 0.69, "ONARILDI ✓", ha="center", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=10)
_hd_strip(ax, p3_arr, x_off3, y_strip, highlight={0}, tag="yığın özelliği geri geldi")
for sep_x in (x_off1 + panel_span + gap_between * 0.5,
x_off2 + panel_span + gap_between * 0.5):
ax.plot([sep_x, sep_x], [y_strip - 0.55, y_title + 0.10],
color=COL_SLATE_400, linewidth=1.0, linestyle=(0, (3, 3)), zorder=0)
fig.suptitle(
"delete_max → aşağı süzme (heapify_down): kök↔son takas, sil, büyük çocukla süz",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.text((x_off1 + x_off3 + panel_span) * 0.5, y_strip - 1.15,
"her seviyede iki çocuğun BÜYÜĞÜ seçilir — böylece her iki kenar da kuralı "
"sağlar · en fazla yükseklik kadar takas = O(log n) · rotasyon YOK, yalnız takas",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=10)
ax.set_xlim(x_off1 - 0.7, x_off3 + panel_span + 0.9)
ax.set_ylim(y_strip - 1.55, y_title + 0.45)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 10. Yerinde Heapsort ve Doğrusal Build {#sec-10-yerinde-heapsort-ve}
**In-place heapsort:** Diziyi büyütüp küçültmek yerine, yığını dizinin bir **önekinde (prefix)** tut. insert = size'ı artır (sonraki A öğesini yığına kat); delete_max = size'ı azalt (son öğeyi düşür). Hiç yeniden boyutlandırma yok → her işlem **en kötü durum $O(1)$** ek. Tüm öğeleri yığına al, sonra delete_max ile çıkar; en büyük öğe sona gider → dizi **yukarı sıralı** olur.
> *"that is what's normally called heapsort."* — Demaine, 48:05
Bu, **$n \log n$ *ve* in-place** (bu sınıftaki tek böyle algoritma).
@fig-heapsort tek dizi içinde prefix yığının küçülüp sıralı sonekin büyümesini gösterir: $[2, 7, 1, 9, 3, 6]$ önce doğrusal build ile $[9, 7, 6, 2, 3, 1]$ yığınına dönüşür; her adım kökü (max) prefix-sonu ile takas eder, yığını 1 küçültür, kökü süzer — çıktı $[1, 2, 3, 6, 7, 9]$.
```{python}
#| label: fig-heapsort
#| fig-cap: "Yerinde heapsort (in-place): prefix yığın küçülür, sıralı sonek büyür (L8 §10, İMZA figür). 6 satır dizi şeridi, her satır 6 hücre = TEK dizi (in-place). Motor izi heapsort_trace([2,7,1,9,3,6]). Satır 1 = doğrusal build sonrası: tamamı yığın [9,7,6,2,3,1] (slate hücreler, SOL etiket 'yığın'). Her sonraki satır: kök ↔ prefix-sonu takas oku → prefix yığın 1 hücre küçülür, kopan max sıralı soneke geçer (yeni amber hücre yıldızlı ★); yığın slate (SOL etiket), sonek amber (SAĞ etiket 'sıralı'). Son satır: tamamı sıralı [1,2,3,6,7,9] (amber). Sağda kutu: ek bellek YOK, yığın + sıralı = AYNI dizi. Her adım kökü (max) yığının sonuna takas eder → sıralı soneğe katar, yığını 1 küçültür, kökü süzer; n log n VE yerinde (bu sınıfın tek böyle algoritması). Motor: build = [9,7,6,2,3,1], 6 adım, output = [1,2,3,6,7,9] (Demaine 48:05)."
#| fig-width: 10.0
#| fig-height: 6.8
# fig-heapsort (L8 §10 İMZA): in-place heapsort — prefix yığın + sıralı sonek.
# Veri MOTORDAN (heapsort_trace([2,7,1,9,3,6])). Figür yalnız bunu çizer.
_HS_CELL_W, _HS_CELL_H = 0.92, 0.74
_HS_ROW_GAP = 1.18
def _hs_row(ax, y, full, heap_len, x0, *, row_label, swap_pair=None,
new_sorted_idx=None, is_final=False):
nn = len(full)
xs = [x0 + k * _HS_CELL_W for k in range(nn)]
centers = []
for k, v in enumerate(full):
x = xs[k]
in_heap = (k < heap_len)
if in_heap:
fc, ec, lw, tcol = COL_BG, COL_PRIMARY, 1.7, COL_TEXT
elif k == new_sorted_idx:
fc, ec, lw, tcol = COL_AMBER_300, COL_AMBER_700, 2.6, COL_TEXT
else:
fc, ec, lw, tcol = COL_AMBER_100, COL_ACCENT, 2.2, COL_AMBER_700
ax.add_patch(FancyBboxPatch(
(x, y), _HS_CELL_W * 0.92, _HS_CELL_H, boxstyle="square,pad=0.0",
fc=fc, ec=ec, linewidth=lw, zorder=2))
cx, cy = x + _HS_CELL_W * 0.46, y + _HS_CELL_H * 0.5
centers.append((cx, cy))
ax.text(cx, cy, str(v), ha="center", va="center",
fontsize=11.5, color=tcol, weight="bold", zorder=4)
if k == new_sorted_idx:
ax.text(x + _HS_CELL_W * 0.86, y + _HS_CELL_H + 0.10, "★",
ha="center", va="center", fontsize=11,
color=COL_AMBER_700, zorder=6)
ax.text(x0 - 0.45, y + _HS_CELL_H * 0.5, row_label, ha="right", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5)
if swap_pair is not None:
a, b = swap_pair
cxa = centers[a][0]
cxb = centers[b][0]
ytop = y + _HS_CELL_H + 0.30
ax.add_patch(FancyArrowPatch(
(cxa, ytop), (cxb, ytop), arrowstyle="-|>", mutation_scale=13,
color=COL_AMBER_700, linewidth=2.0, zorder=5,
connectionstyle="arc3,rad=-0.45"))
mx = (cxa + cxb) * 0.5
ax.text(mx, ytop + 0.30, "kök ↔ son takas", ha="center", va="bottom",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
if heap_len > 0:
hx_mid = x0 + (heap_len - 1) * _HS_CELL_W * 0.5 + _HS_CELL_W * 0.46
ax.text(hx_mid, y - 0.20, "yığın", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=4)
if heap_len < nn:
sx0 = x0 + heap_len * _HS_CELL_W
sx_mid = sx0 + (nn - heap_len - 1) * _HS_CELL_W * 0.5 + _HS_CELL_W * 0.46
ax.text(sx_mid, y - 0.20, "sıralı", ha="center", va="center",
fontsize=7.5, color=COL_AMBER_700, style="italic",
weight="bold", zorder=4)
if 0 < heap_len < nn:
bx = x0 + heap_len * _HS_CELL_W - _HS_CELL_W * 0.04
ax.plot([bx, bx], [y - 0.06, y + _HS_CELL_H + 0.06],
color=COL_SLATE_400, linewidth=1.4, linestyle=(0, (2, 2)),
zorder=3)
if is_final:
ax.text(xs[-1] + _HS_CELL_W + 0.30, y + _HS_CELL_H * 0.5, "tamamı sıralı ✓",
ha="left", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
return centers
_hs_src = [2, 7, 1, 9, 3, 6]
_hs_tr = heapsort_trace(_hs_src)
_hs_steps = _hs_tr["steps"]
_hs_output = _hs_tr["output"]
assert _hs_steps[0]["heap"] == [9, 7, 6, 2, 3, 1]
assert len(_hs_steps) == 6 and _hs_output == [1, 2, 3, 6, 7, 9]
for _i, _s in enumerate(_hs_steps):
assert _s["sorted"] == sorted(_s["sorted"])
assert len(_s["heap"]) + len(_s["sorted"]) == 6
nhs = len(_hs_src)
fig, ax = plt.subplots(figsize=(10.0, 6.8))
fig.patch.set_facecolor(COL_WHITE)
x0 = 0.0
y_first = 0.0
y_rows = [y_first - r * _HS_ROW_GAP for r in range(len(_hs_steps))]
for r, st in enumerate(_hs_steps):
heap = st["heap"]
sorted_suf = st["sorted"]
full = list(heap) + list(sorted_suf)
assert len(full) == nhs
heap_len = len(heap)
if r == 0:
label = "build (doğrusal)"
swap_pair = None
new_idx = None
else:
label = f"Adım {r}"
new_idx = heap_len
swap_pair = (0, heap_len)
is_final = (r == len(_hs_steps) - 1)
_hs_row(ax, y_rows[r], full, heap_len, x0,
row_label=label, swap_pair=swap_pair,
new_sorted_idx=new_idx, is_final=is_final)
final_full = list(_hs_steps[-1]["heap"]) + list(_hs_steps[-1]["sorted"])
assert final_full == _hs_output
box_x = x0 + nhs * _HS_CELL_W + 0.55
box_y = y_rows[0] - 0.05
box_w, box_h = 3.55, _HS_CELL_H + 0.18
ax.add_patch(FancyBboxPatch(
(box_x, box_y), box_w, box_h,
boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.0, zorder=2))
ax.text(box_x + box_w * 0.5, box_y + box_h * 0.5,
"ek bellek YOK\nyığın + sıralı = AYNI dizi",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=4, linespacing=1.3)
fig.suptitle(
"Yerinde heapsort (in-place): prefix yığın küçülür, sıralı sonek büyür",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
y_bottom = y_rows[-1]
ax.text(x0 + nhs * _HS_CELL_W * 0.5, y_bottom - 0.78,
"her adım kökü (max) yığının sonuna takas eder → sıralı soneğe katar, "
"yığını 1 küçültür, kökü süzer",
ha="center", va="center", fontsize=9, color=COL_SLATE_500,
style="italic", zorder=5)
ax.text(x0 + nhs * _HS_CELL_W * 0.5, y_bottom - 1.14,
"ek bellek YOK — yığın ile sıralı bölge AYNI dizide · "
"n log n VE yerinde (bu sınıfın tek böyle algoritması)",
ha="center", va="center", fontsize=9, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.set_xlim(x0 - 2.0, box_x + box_w + 0.4)
ax.set_ylim(y_bottom - 1.55, y_rows[0] + _HS_CELL_H + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
**Doğrusal build:** Öğeleri tek tek ekleyip yukarı-heapify yaparsan toplam derinliklerin toplamı = $n \log n$. Bunun yerine, hepsini diziye koyup **aşağıdan yukarıya heapify-down** yap. Bu, **yüksekliklerin toplamıdır** ve şaşırtıcı biçimde **$O(n)$**'dir (yapraklar çok ama yükseklikleri küçük; kök yüksek ama tek).
> *"heapify down from the bottom up... that's better. Because this is the sum of the heights of the nodes. And that turns out to be linear."* — Demaine, 49:24
@fig-linear-build bu üstünlüğü ölçer: $n = 15$ complete tree'de $\Sigma$ derinlik $= 34$ (tek tek insert, $\approx n \log n$) iken $\Sigma$ yükseklik $= 11$ (bottom-up build, $\le 2n = 30$); $n = 1023$'te uçurum büyür — 8194'e karşı 1013 (hâlâ $\le 2046$).
```{python}
#| label: fig-linear-build
#| fig-cap: "Doğrusal build = yüksekliklerin toplamı, Σ yükseklik ≤ 2n = O(n) (L8 §10). Sol panel: n=15 complete tree (4 seviye); iç düğümlerin yanında d=derinlik (slate) + h=yükseklik (amber) rozetleri; yapraklar (h=0) amber dolgu; altta iki toplam kutusu: Σderinlik = 34 (tek tek insert ~ n log n, slate) vs Σyükseklik = 11 (bottom-up build = O(n), amber) + '11 ≤ 2n = 30' etiketi; 8 yaprak hepsi h0 → yükseklik maliyeti sıfır. Sağ panel: büyüme grafiği n = 15, 127, 1023; Σderinlik (slate, n=1023 → 8194 fırlar ~ n log n) vs Σyükseklik (amber, n=1023 → 1013 doğrusal kalır) + 2n referans kesikli çizgi; n=1023'te UÇURUM 8194 ↔ 1013 vurgulanır. Yapraklar ÇOK ama yükseklikleri KÜÇÜK (h=0) — çok olandan az öde; bottom-up build O(n), tek tek insert ise n log n. Motor: complete_tree_depth_height_sums(15)=(34,11), (1023)=(8194,1013) (Demaine 49:24)."
#| fig-width: 11.0
#| fig-height: 6.4
# fig-linear-build (L8 §10): doğrusal build = yüksekliklerin toplamı.
# Veri MOTORDAN (complete_tree_depth_height_sums / heap_left).
_LB_R = 0.26
_LB_Y_GAP = 1.30
def _lb_node_depth(i):
return int(math.log2(i + 1))
def _lb_node_height(i, nn):
h = 0
j = heap_left(i)
while j < nn:
h += 1
j = heap_left(j)
return h
def _lb_node_xy(i, nn, x_lo, x_hi, y_top):
d = _lb_node_depth(i)
first = (1 << d) - 1
pos_in_level = i - first
count = 2 ** d
span = x_hi - x_lo
x = x_lo + (pos_in_level + 0.5) * (span / count)
y = y_top - d * _LB_Y_GAP
return x, y
def _lb_draw_tree(ax, nn, x_lo, x_hi, y_top):
for i in range(nn):
px, py = _lb_node_xy(i, nn, x_lo, x_hi, y_top)
for c in (heap_left(i), heap_left(i) + 1):
if c < nn:
cx, cy = _lb_node_xy(c, nn, x_lo, x_hi, y_top)
ax.plot([px, cx], [py, cy], color=COL_SLATE_400,
linewidth=1.4, zorder=1, solid_capstyle="round")
max_depth = _lb_node_depth(nn - 1)
for i in range(nn):
x, y = _lb_node_xy(i, nn, x_lo, x_hi, y_top)
h = _lb_node_height(i, nn)
d = _lb_node_depth(i)
is_leaf = (h == 0)
if is_leaf:
fc, ec = COL_AMBER_100, COL_ACCENT
else:
fc, ec = COL_BG, COL_PRIMARY
ax.add_patch(Circle((x, y), _LB_R, facecolor=fc, edgecolor=ec,
linewidth=1.8, zorder=5))
if d == max_depth:
continue
ax.text(x - _LB_R - 0.06, y, f"d{d}", ha="right", va="center",
fontsize=6.6, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(x + _LB_R + 0.06, y, f"h{h}", ha="left", va="center",
fontsize=6.6, color=COL_AMBER_700, weight="bold", zorder=6)
leaf_y = y_top - max_depth * _LB_Y_GAP
leaf_count = sum(1 for i in range(nn) if _lb_node_height(i, nn) == 0)
ax.text((x_lo + x_hi) * 0.5, leaf_y - _LB_R - 0.30,
f"{leaf_count} yaprak · hepsi d{max_depth}, h0 → yükseklik maliyeti SIFIR",
ha="center", va="center", fontsize=8.0, color=COL_AMBER_700,
weight="bold", zorder=6)
def _lb_sum_box(ax, x_center, y, width, title, value, formula, *, accent):
fc = COL_AMBER_100 if accent else COL_BG
ec = COL_ACCENT if accent else COL_SLATE_400
val_col = COL_AMBER_700 if accent else COL_SLATE_500
h_box = 1.05
ax.add_patch(FancyBboxPatch(
(x_center - width * 0.5, y), width, h_box,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=fc, ec=ec, linewidth=2.2, zorder=3))
ax.text(x_center, y + h_box - 0.22, title, ha="center", va="center",
fontsize=9, color=COL_TEXT, weight="bold", zorder=5)
ax.text(x_center, y + h_box * 0.46, value, ha="center", va="center",
fontsize=15, color=val_col, weight="bold", zorder=5)
ax.text(x_center, y + 0.14, formula, ha="center", va="center",
fontsize=7.3, color=COL_SLATE_500, style="italic", zorder=5)
n_tree = 15
sum_d15, sum_h15 = complete_tree_depth_height_sums(n_tree)
assert (sum_d15, sum_h15) == (34, 11)
ns = [15, 127, 1023]
depth_pts = []
height_pts = []
for nn in ns:
sd, sh = complete_tree_depth_height_sums(nn)
depth_pts.append(sd)
height_pts.append(sh)
sum_d1023, sum_h1023 = depth_pts[-1], height_pts[-1]
assert (sum_d1023, sum_h1023) == (8194, 1013)
assert sum_h15 <= 2 * n_tree and sum_h1023 <= 2 * 1023
fig, (ax_tree, ax_grow) = plt.subplots(
1, 2, figsize=(11.0, 6.4), gridspec_kw={"width_ratios": [1.18, 1.0]})
fig.patch.set_facecolor(COL_WHITE)
ax_tree.set_facecolor(COL_WHITE)
x_lo, x_hi = 0.0, 8.0
y_top = 0.0
_lb_draw_tree(ax_tree, n_tree, x_lo, x_hi, y_top)
ax_tree.text(x_hi, y_top + 0.55, "d = derinlik (kökten) · h = yükseklik (yaprağa)",
ha="right", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=6)
y_box = y_top - 4 * _LB_Y_GAP - 0.50
box_w = 3.35
_lb_sum_box(ax_tree, x_lo + box_w * 0.5 + 0.25, y_box, box_w,
"Σ derinlik (tek tek insert)", f"= {sum_d15}",
"her öğe derinliği kadar kabarır ~ n log n", accent=False)
_lb_sum_box(ax_tree, x_hi - box_w * 0.5 - 0.25, y_box, box_w,
"Σ yükseklik (bottom-up build)", f"= {sum_h15}",
"her düğüm yüksekliği kadar süzülür = O(n)", accent=True)
ax_tree.text(x_hi - box_w * 0.5 - 0.25, y_box - 0.36,
f"{sum_h15} ≤ 2n = {2 * n_tree}", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax_tree.set_title("n=15 complete tree — aynı yapı, iki maliyet",
color=COL_TEXT, fontsize=11.5, weight="bold")
ax_tree.set_xlim(x_lo - 0.7, x_hi + 0.7)
ax_tree.set_ylim(y_box - 0.75, y_top + 0.95)
ax_tree.set_aspect("equal")
ax_tree.axis("off")
ax_grow.set_facecolor(COL_WHITE)
ax_grow.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax_grow.spines.values():
spine.set_color(COL_SLATE_400)
ax_grow.tick_params(colors=COL_TEXT)
ax_grow.plot(ns, depth_pts, color=COL_PRIMARY, linewidth=2.6,
marker="o", markersize=6, zorder=4,
label="Σ derinlik (tek tek insert ~ n log n)")
ax_grow.plot(ns, height_pts, color=COL_ACCENT, linewidth=2.6,
marker="s", markersize=6, zorder=4,
label="Σ yükseklik (bottom-up build = O(n))")
ax_grow.plot(ns, [2 * nn for nn in ns], color=COL_AMBER_600, linewidth=1.6,
linestyle=(0, (5, 3)), zorder=3, label="2n referansı (Σ yükseklik ≤ 2n)")
for nn, sd in zip(ns, depth_pts):
ax_grow.annotate(str(sd), (nn, sd), textcoords="offset points",
xytext=(6, 7), fontsize=8.5, color=COL_PRIMARY,
weight="bold", zorder=6)
for nn, sh in zip(ns, height_pts):
ax_grow.annotate(str(sh), (nn, sh), textcoords="offset points",
xytext=(6, -13), fontsize=8.5, color=COL_AMBER_700,
weight="bold", zorder=6)
n_last = ns[-1]
ax_grow.annotate(
"", xy=(n_last, sum_d1023), xytext=(n_last, sum_h1023),
arrowprops=dict(arrowstyle="<->", color=COL_AMBER_700, linewidth=2.0),
zorder=5)
ax_grow.text(n_last - 30, (sum_d1023 + sum_h1023) * 0.5,
f"UÇURUM\n{sum_d1023} ↔ {sum_h1023}", ha="right", va="center",
fontsize=8.6, color=COL_AMBER_700, weight="bold", zorder=6,
linespacing=1.25)
ax_grow.set_xlabel("n (düğüm sayısı)", color=COL_TEXT, fontsize=10)
ax_grow.set_ylabel("toplam işlem maliyeti", color=COL_TEXT, fontsize=10)
ax_grow.set_xticks(ns)
ax_grow.set_xticklabels([str(nn) for nn in ns])
ax_grow.set_title("Büyüme: Σ derinlik fırlar, Σ yükseklik doğrusal kalır",
color=COL_TEXT, fontsize=11.5, weight="bold")
ax_grow.legend(loc="upper left", fontsize=8.2, framealpha=0.92)
ax_grow.set_ylim(0, sum_d1023 * 1.12)
fig.suptitle(
"Doğrusal build = yüksekliklerin toplamı (Σ yükseklik ≤ 2n = O(n))",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
fig.text(0.5, 0.012,
"yapraklar ÇOK ama yükseklikleri KÜÇÜK (h=0) — çok olandan az öde "
"· bottom-up build O(n), tek tek insert ise n log n (Demaine 49:24)",
ha="center", va="bottom", fontsize=8.6, color=COL_SLATE_500,
style="italic")
plt.tight_layout(rect=(0, 0.03, 1, 0.96))
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d12}
1. **Öncelik kuyruğu**: insert + delete_max; set arayüzünün alt kümesi.
2. **Priority queue sort**: ekle-hepsini + delete_max-hepsini → AVL/selection/insertion sort birleşir.
3. **Complete binary tree**: her derinlik dolu, son seviye sola yaslı; yükseklik $\lceil \log n \rceil$, dengeli.
4. **Dizi ↔ ağaç bijection**: derinlik sırası; örtük (işaretçisiz); left $2i+1$, right $2i+2$, parent $(j-1)//2$.
5. **Max-heap özelliği**: $Q[i] \ge$ çocukları; maksimum kökte; düğüm $\ge$ tüm alt ağacı.
6. **insert/delete_max**: max_heapify_up / max_heapify_down (takas + özyinele); $O(\log n)$.
7. **Heapsort**: prefix yığın, in-place, $O(n \log n)$; **doğrusal build** = yüksekliklerin toplamı = $O(n)$.
::: {.callout-important title="Tek Bir Cümle"}
İkili yığın, dengeli bir tam-ağacı diziye gömüp (işaretçisiz) max-heap özelliğini heapify ile korur; sonuç hem $O(\log n)$ öncelik kuyruğu hem de yerinde $O(n \log n)$ sıralama (heapsort).
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d12}
::: {.callout-note collapse="true" title="Soru 1: İkili yığın neden rotasyona ihtiyaç duymaz, oysa AVL ağacı duyar?"}
**Cevap:**
Yığın bir **complete binary tree**'dir — şekli $n$ tarafından zaten benzersiz biçimde belirlenir (yukarıdan aşağı, soldan sağa dolu) ve her zaman dengelidir (yükseklik $\lceil \log n \rceil$). Şekil sabit olduğundan dengeleme (rotasyon) gerekmez; yalnızca anahtarların yerini (heapify up/down ile takas) düzeltiriz. AVL ise keyfi şekilli bir BST olduğundan, dengeyi korumak için rotasyon şarttır. Yığının bu lüksü, yalnızca priority queue (set'in alt kümesi) çözmesinden gelir.
:::
::: {.callout-note collapse="true" title="Soru 2: index 4'teki düğümün çocukları ve index 9'un parent'ı nedir? Formülleri uygula."}
**Cevap:**
index 4'ün sol çocuğu $2 \cdot 4 + 1 = 9$, sağ çocuğu $2 \cdot 4 + 2 = 10$. index 9'un parent'ı $(9 - 1) // 2 = 4$ — tutarlı (9, 4'ün sol çocuğuydu). index 10'un parent'ı $(10 - 1) // 2 = 4$ (tamsayı bölme) — sağ çocuk da aynı parent'a döner. Bir çocuk index'i dizi boyutunu aşıyorsa o çocuk yoktur (yaprak).
:::
::: {.callout-note collapse="true" title="Soru 3: max-heap özelliği ile BST özelliği arasındaki fark nedir?"}
**Cevap:**
**BST**: sol alt ağaç $<$ düğüm $<$ sağ alt ağaç — *yatay* sıralama, traversal sırası anlamlı, find/range yapılır. **Max-heap**: düğüm $\ge$ her iki çocuğu — yalnızca *dikey* (ata-torun) ilişki; iki çocuğun birbirine göre sırası umursanmaz. Heap, anahtarları sıralı tutmaz, sadece "maksimum köktedir" garantisi verir; bu yüzden find(k) veya find_next yapamaz, ama find_max/delete_max'i çok ucuz yapar.
:::
::: {.callout-note collapse="true" title="Soru 4: Doğrusal build (heapify-down, bottom-up) neden O(n)'dir, oysa tek tek insert O(n log n)'dir?"}
**Cevap:**
Tek tek insert + heapify-up, her öğe için **derinlik** kadar iş yapar; toplam = derinliklerin toplamı = $O(n \log n)$ (çoğu öğe yapraktadır, derinliği $\sim \log n$). Bottom-up heapify-down ise her düğüm için **yükseklik** kadar iş yapar; toplam = yüksekliklerin toplamı. Yapraklar çoktur ama yükseklikleri 0-1; yüksek düğümler azdır. Bu ağırlıklı toplam $O(n)$'e yakınsar — "çok olandan az öde, az olandan çok öde".
:::
## Egzersizler {#sec-egzersizler-d12}
**Egzersiz 1.** Verilen bir diziyi complete binary tree olarak çiz (derinlik sırası); index aritmetiğiyle her düğümün çocuklarını/parent'ını doğrula.
**Egzersiz 2.** Bir max-heap'e yeni bir maksimum öğe ekle ve `max_heapify_up`'ı adım adım yürüt (köke kadar kabarma).
**Egzersiz 3.** Bir max-heap'ten delete_max yap: kök-son takas, delete_last, `max_heapify_down` (büyük çocukla takas). Sonucun hâlâ heap olduğunu doğrula.
**Egzersiz 4.** Python'da örtük yığın için index aritmetiğini ve heapify_down'ı yaz:
```python
def heapify_down(Q, i, n):
while True:
l, r = 2*i + 1, 2*i + 2
big = i
if l < n and Q[l] > Q[big]: big = l
if r < n and Q[r] > Q[big]: big = r
if big == i: return
Q[i], Q[big] = Q[big], Q[i]
i = big
```
**Egzersiz 5.** Heapsort'un neden in-place olduğunu (prefix yığın) açıkla. Merge sort neden in-place değildir? İkisinin de $O(n \log n)$ olmasına rağmen hangi durumda heapsort tercih edilir?
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d12}
**Ders 13 (L9): Çizgeler ve BFS (Breadth-First Search)**
Justin Solomon ile, veri yapılarından **çizge (graph) algoritmalarına** geçiyoruz: düğümler ve kenarlar, ve bir kaynaktan **enine arama (BFS)** ile ağırlıksız en kısa yollar. Öncelik kuyruğu, ilerideki ağırlıklı en kısa yollarda (Dijkstra) yeniden karşımıza çıkacak. (Not: ders akışında araya **Problem Oturumu** ve **Quiz 1 tekrarı** girer — kitap düzeninde Quiz 1 tekrarı araya giren **Ders 14 (Quiz 1 Review)**'tür.)
::: {.callout-warning title="Ders 13 Öncesi Yapılacak"}
- Bu dersin egzersizlerini, özellikle **Egzersiz 4**'ü (heapify_down) çöz.
- Üç fikri (complete tree ↔ array, max-heap özelliği, heapify) ve nasıl in-place heapsort verdiklerini ezberden anlat.
- Ana cümleyi tekrar oku: *"Dengeli tam-ağacı diziye gömüp heapify ile koru."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d12}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **Öncelik kuyruğu** | insert + delete_max; set'in alt kümesi | Böl. 1 |
| **Priority queue sort** | Ekle-hepsini + delete_max → AVL/selection/insertion | Böl. 3-4 |
| **Complete binary tree** | Her derinlik dolu, son seviye sola yaslı; yükseklik $\lceil \log n \rceil$ | Böl. 5 |
| **Dizi ↔ ağaç (örtük)** | left $2i+1$, right $2i+2$, parent $(j-1)//2$ | Böl. 6 |
| **Max-heap özelliği** | $Q[i] \ge$ çocukları; maksimum kökte | Böl. 7 |
| **max_heapify_up/down** | Takas + özyinele; insert/delete_max $O(\log n)$ | Böl. 8-9 |
| **Heapsort** | Prefix yığın; in-place; $O(n \log n)$ | Böl. 10 |
| **Doğrusal build** | Bottom-up heapify-down = yüksekliklerin toplamı = $O(n)$ | Böl. 10 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d12}
::: {.callout-tip title="6 köprü"}
Bu ders, "az söz veren arayüz ne kadar güç açar ve örtük yapı ne kazandırır" sezgisini kurar — köprülerin özeti:
1. **Öncelik kuyruğu** → Dijkstra/Prim (graph), event-driven simülasyon, OS scheduler, router QoS — her yerde "en öncelikliyi al".
2. **Heapsort (in-place, $n \log n$)** → bellek-kısıtlı sistemler (gömülü, çekirdek); ek tampon ayıramayan ortamlar.
3. **Örtük veri yapısı** → cache-dostu tasarım: işaretçisiz dizi, bellek yerelliği yüksek (heap, segment tree).
4. **Complete tree ↔ array** → segment tree / Fenwick tree'nin temeli; aynı index-aritmetiği indeksleme.
5. **Alt küme = daha fazla güç** → API tasarım ilkesi: daha az söz veren arayüz, daha güçlü garanti/optimizasyon sunabilir.
6. **Yüksekliklerin toplamı = $O(n)$** → amortize/ağırlıklı analiz sezgisi: "çok olandan az, az olandan çok öde".
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
İkili yığın, "her şeyi" değil yalnızca "maksimumu" istediğin için, dengeli bir tam-ağacı diziye işaretçisiz gömebilir ve rotasyonsuz korur. Bu kısıtlama iki armağan verir: doğrusal build ve — tek in-place $O(n \log n)$ sıralaman olan — heapsort.
:::
