--- title: 'İki Yığın' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/iki-yigin' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # İki Yığın Akan veride ortanca izleme; denge adımı kaldırıldığında 480 ortancanın 295'inin bozulması ve kalıbın kazancının akış uzadıkça büyümesi. Önceki beş kalıp girdinin tamamını elinde tuttu: dizi baştan sona görülebiliyor, istenen konuma dönülebiliyordu. Bu dersin kalıbı o olanağı kaybeder. Değerler **tek tek akar** ve her yeni değerden sonra bir soru yanıtlanmalıdır: o ana kadar görülenlerin **ortancası** nedir. Ortancayı bulmanın doğrudan yolu sıralı bir liste tutmaktır; her yeni değer doğru yere sokulur ve ortadaki okunur. Kalıp bunun yerine **iki yığın** tutar: küçük yarı bir **en büyük yığında**, büyük yarı bir **en küçük yığında**. Ortanca, iki yığının tepesinden okunur. Yığın koşulu, süzme işlemleri ve dizi gösterimi Veri Yapıları kursunun Yığınlar dersinde kuruldu; burada **tekrarlanmaz**, doğrudan kullanılır. Kalıbın ön koşulu iki yığının **dengede** kalmasıdır. Bu ders dengeyi bozup kaç ortancanın yanlış çıktığını sayar. ## Kalıp ve Denge Ön koşulu Her yeni değer önce yerine konur: küçük yarının tepesinden büyük değilse en büyük yığına, değilse en küçük yığına. Bu tek başına yetmez, çünkü değerler bir yana yığılabilir. İkinci adım **denge adımıdır**: yığınların boyu birden fazla ayrıldığında büyük olanın tepesi öbürüne aktarılır. Ortanca ancak iki yığının boyu doğruyken okunabilir. Toplam tek sayıdaysa büyük olan yığının tepesi ortancadır; çift sayıdaysa iki tepenin ortalaması. Denge bozuksa bu iki kural da yanlış yeri gösterir — kalıp yine bir sayı döndürür. **PK40.** Dağarcık 40 akıştır; her akış 12 değer taşır ve değerler −9 ile 20 arasındadır. Tohum `20260218`. Her akışta her değerden sonra bir ortanca sorulur; toplam **480** soru. **PK41.** Kâhin her değeri **doğrusal tarama** ile sıralı listeye sokar ve ortadakini okur. Her karşılaştırma bir adım sayılır. **PK42.** Kalıbın adımı, yığın işlemlerinin yaptığı **gerçek karşılaştırmalardır**; değerler karşılaştırmayı sayan bir sarmalayıcıya konur, adım tahmin edilmez. **PK43.** Ön koşulu bozan tek şey **denge adımının kaldırılmasıdır**. Değer yerleştirme kuralı, ortanca okuma kuralı, dağarcık ve tohum aynıdır. ```python import heapq TOHUM, UZUNLUK, DAGARCIK = 20260218, 12, 40 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def akis_dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK): r = uretec(tohum) return [{"no": i + 1, "akis": [r(30) - 9 for _ in range(uzunluk)]} for i in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 class Olcu: """Yiginin her karsilastirmasini sayan sarmalayici. yon=-1 en buyuk yigin verir.""" __slots__ = ("d", "yon", "s") def __init__(self, d, yon, s): self.d, self.yon, self.s = d, yon, s def __lt__(self, o): self.s.say() return self.d * self.yon < o.d * o.yon def kahin_ortanca(akis, s): """Her degeri dogrusal tarama ile sirali listeye sokar, ortadakini okur.""" sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali): s.say() if sirali[i] >= x: break i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, dengele, s): """ONKOSUL: iki yigin dengede kalmali. alt en buyuk yigin, ust en kucuk yigin.""" alt, ust, yanit = [], [], [] en_buyuk_fark = 0 for x in akis: if not alt or x <= alt[0].d: heapq.heappush(alt, Olcu(x, -1, s)) else: heapq.heappush(ust, Olcu(x, 1, s)) if dengele: if len(alt) > len(ust) + 1: heapq.heappush(ust, Olcu(heapq.heappop(alt).d, 1, s)) elif len(ust) > len(alt): heapq.heappush(alt, Olcu(heapq.heappop(ust).d, -1, s)) en_buyuk_fark = max(en_buyuk_fark, abs(len(alt) - len(ust))) if not alt: yanit.append(ust[0].d) elif not ust or len(alt) > len(ust): yanit.append(alt[0].d) elif len(ust) > len(alt): yanit.append(ust[0].d) else: yanit.append((alt[0].d + ust[0].d) / 2) return yanit, en_buyuk_fark K = akis_dagarcik() print("dagarcik:", len(K), "akis x", UZUNLUK, "deger =", len(K) * UZUNLUK, "ortanca") print("kurulum yanlis ortanca ayrilan akis/40 kalip kahin oran en buyuk fark") for ad, dengele in (("dengeli ", True), ("dengesiz ", False)): yanlis, ayrilan, ak, ah, fark = 0, 0, 0, 0, 0 for k in K: s1, s2 = Sayac(), Sayac() a, f = kalip_iki_yigin(k["akis"], dengele, s1) b = kahin_ortanca(k["akis"], s2) ak, ah = ak + s1.adim, ah + s2.adim fark = max(fark, f) bozuk = sum(1 for x, y in zip(a, b) if x != y) yanlis += bozuk ayrilan += bozuk > 0 print(f"{ad} {yanlis:14d} {ayrilan:15d} {ak:5d} {ah:5d} {ah / ak:5.2f}" f" {fark:13d}") ``` ``` dagarcik: 40 akis x 12 deger = 480 ortanca kurulum yanlis ortanca ayrilan akis/40 kalip kahin oran en buyuk fark dengeli 0 0 1261 1693 1.34 1 dengesiz 295 39 550 1693 3.08 12 ``` Dengeli kurulumda **480 ortancanın 480'i** kâhinle aynı; en büyük boy farkı **1**, yani denge hiç bozulmuyor. Denge adımı kaldırıldığında **295 ortanca** yanlış çıkıyor ve 40 akışın **39'u** bozuluyor. İkinci satırın adım sütunu dersin ana çelişkisini taşıyor: dengesiz kalıp **550** adım harcıyor, dengelinin **yarısından az**. Denge adımı, kalıbın toplam işinin büyük bölümünü oluşturuyor; onu kaldırmak kalıbı kâhine göre 1,34 kattan **3,08 kata** hızlandırıyor. En hızlı kurulum yine en bozuk kurulumdur. En büyük boy farkı da 1'den **12'ye** çıkıyor: bütün değerler tek bir yığında birikiyor. ## Dengesizlik Nasıl Yanlış Ortanca Üretiyor Denge adımı olmadan yerleştirme kuralı kendi kendini besler. Küçük bir değer geldiğinde küçük yarıya konur; küçük yarının tepesi daha da küçülmez, ama yarı büyür. Bir sonraki değer o büyümüş yarının tepesiyle karşılaştırılır ve çoğunlukla yine oraya düşer. Bir yığın şişerken öbürü boş kalır ve ortanca okuma kuralı sürekli **aynı** tepeye bakar. ```python import heapq def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def akis_dagarcik(tohum, n=40, uzunluk=12): r = uretec(tohum) return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)] def kahin_ortanca(akis): sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali) and sirali[i] < x: i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, dengele): """alt en buyuk yigin (isaret ters cevrilerek), ust en kucuk yigin.""" alt, ust, yanit = [], [], [] for x in akis: if not alt or x <= -alt[0]: heapq.heappush(alt, -x) else: heapq.heappush(ust, x) if dengele: if len(alt) > len(ust) + 1: heapq.heappush(ust, -heapq.heappop(alt)) elif len(ust) > len(alt): heapq.heappush(alt, -heapq.heappop(ust)) if not alt: yanit.append(ust[0]) elif not ust or len(alt) > len(ust): yanit.append(-alt[0]) elif len(ust) > len(alt): yanit.append(ust[0]) else: yanit.append((-alt[0] + ust[0]) / 2) return yanit ilk = akis_dagarcik(20260218)[0] print("akis 1 :", ilk) print(" kahin :", kahin_ortanca(ilk)) print(" dengeli :", kalip_iki_yigin(ilk, True)) print(" dengesiz :", kalip_iki_yigin(ilk, False)) print() print("tohum kurulum yanlis ortanca/480 ayrilan akis/40 ilk yanlis konum") for tohum in (20260218, 20260219): K = akis_dagarcik(tohum) for ad, dengele in (("dengeli ", True), ("dengesiz", False)): yanlis, ayrilan, ilk_konum = 0, 0, [] for akis in K: a, b = kalip_iki_yigin(akis, dengele), kahin_ortanca(akis) bozuk = [i + 1 for i, (x, y) in enumerate(zip(a, b)) if x != y] yanlis += len(bozuk) ayrilan += bool(bozuk) if bozuk: ilk_konum.append(bozuk[0]) ortalama = round(sum(ilk_konum) / len(ilk_konum), 2) if ilk_konum else 0 print(f"{tohum} {ad} {yanlis:18d} {ayrilan:15d} {ortalama:16}") ``` ``` akis 1 : [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1] kahin : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] dengeli : [-8, -6.5, -5, -3.0, -1, 0.5, 2, 1.5, 2, 2.0, 2, 2.0] dengesiz : [-8, -6.5, -5, -5, -5, -5, -5, -5, -5, -5, -5, -5] tohum kurulum yanlis ortanca/480 ayrilan akis/40 ilk yanlis konum 20260218 dengeli 0 0 0 20260218 dengesiz 295 39 3.44 20260219 dengeli 0 0 0 20260219 dengesiz 268 38 3.89 ``` Birinci akışın izi, mekanizmayı tek satırda gösteriyor. Dengeli kurulum kâhinin bütün yanıtlarını üretiyor. Dengesiz kurulum ilk üç ortancayı doğru veriyor, sonra **−5'te kilitleniyor** ve akışın sonuna kadar aynı sayıyı yazıyor. Değerler 16 ve 17'ye çıksa bile yanıt değişmiyor, çünkü bütün büyük değerler tek bir yığında birikmiş ve okunan tepe hep aynı kalmış. **PK44.** İkinci dağarcık `20260219` tohumundan gelir. Yanlış ortanca **268/480**, birincide **295/480**; ayrılan akış **38/40** ve **39/40**. Oranlar 0,56 ile 0,61 arasında, aynı büyüklük düzeninde — sonuç dağarcığa bağlı değildir. **PK45.** İlk yanlış ortanca ortalama **3,44'üncü** değerde çıkıyor. Denge en geç dördüncü değerde bozuluyor, yani kusur akışın sonunda değil **başında** oluşuyor. Bu son sayı, kusurun neden gözden kaçmadığından çok neden **kaçtığını** açıklar. İlk üç yanıt doğrudur; kısa bir sınama akışı bu üç yanıta bakıp geçerse hiçbir şey görmez. Kusur yalnız akış uzadıkça birikir ve tek bir yanlış ortanca da çıktıya bakarak seçilemez — dengesiz kalıp yine akla yatkın bir sayı döndürüyor. ## Kalıbın Kazancı Akış Uzadıkça Büyüyor On iki değerlik akışta dengeli kalıbın oranı **1,34**. Bu, kalıbı kurmaya değmeyecek kadar küçük bir kazançtır ve bir soru doğurur: iki yığın niçin var. Yanıt akış uzunluğundadır. Kâhinin her eklemesi listenin yarısını tarar, yani maliyeti o ana kadarki değer sayısıyla doğru orantılıdır; yığın eklemesi ise yığının **derinliği** kadar karşılaştırma yapar. **PK46.** Bu ölçümde akış sayısı 10'a indirilir ve akış uzunluğu 12'den 200'e çıkarılır. Dağarcık aynı üreteçten, aynı tohumla gelir; değişen tek şey uzunluktur. ```python import heapq def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def akis_dagarcik(tohum, n, uzunluk): r = uretec(tohum) return [[r(30) - 9 for _ in range(uzunluk)] for _ in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 class Olcu: """Yiginin her karsilastirmasini sayar. yon=-1 en buyuk yigin verir.""" __slots__ = ("d", "yon", "s") def __init__(self, d, yon, s): self.d, self.yon, self.s = d, yon, s def __lt__(self, o): self.s.say() return self.d * self.yon < o.d * o.yon def kahin_ortanca(akis, s): sirali, yanit = [], [] for x in akis: i = 0 while i < len(sirali): s.say() if sirali[i] >= x: break i += 1 sirali.insert(i, x) n = len(sirali) yanit.append(sirali[n // 2] if n % 2 else (sirali[n // 2 - 1] + sirali[n // 2]) / 2) return yanit def kalip_iki_yigin(akis, s): alt, ust, yanit = [], [], [] for x in akis: if not alt or x <= alt[0].d: heapq.heappush(alt, Olcu(x, -1, s)) else: heapq.heappush(ust, Olcu(x, 1, s)) if len(alt) > len(ust) + 1: heapq.heappush(ust, Olcu(heapq.heappop(alt).d, 1, s)) elif len(ust) > len(alt): heapq.heappush(alt, Olcu(heapq.heappop(ust).d, -1, s)) yanit.append(alt[0].d if len(alt) > len(ust) else (alt[0].d + ust[0].d) / 2) return yanit print("akis uzunlugu ayrilan akis/10 kalip kahin oran") for uzunluk in (12, 25, 50, 100, 200): K = akis_dagarcik(20260218, 10, uzunluk) ayrilan, ak, ah = 0, 0, 0 for akis in K: s1, s2 = Sayac(), Sayac() a = kalip_iki_yigin(akis, s1) b = kahin_ortanca(akis, s2) ak, ah = ak + s1.adim, ah + s2.adim ayrilan += (a != b) print(f"{uzunluk:13d} {ayrilan:15d} {ak:5d} {ah:6d} {ah / ak:6.2f}") ``` ``` akis uzunlugu ayrilan akis/10 kalip kahin oran 12 0 303 431 1.42 25 0 949 1602 1.69 50 0 2471 6440 2.61 100 0 5971 25292 4.24 200 0 13686 98651 7.21 ``` Ayrılan akış beş uzunlukta da **sıfır**: denge korunduğu sürece kalıp uzunluktan bağımsız olarak doğrudur. Oran ise 1,42'den **7,21'e** çıkıyor. Kâhinin adımı 431'den 98.651'e, yani **229 kat** artarken kalıbın adımı 303'ten 13.686'ya, **45 kat** artıyor. Kalıbı kurmanın gerekçesi bu sütundur. On iki değerlik bir akışta iki yığın tutmak gereksizdir; iki yüz değerlik bir akışta yedi kat, daha uzun akışlarda daha çok kazandırır. **Bir kalıbın kazancı bir sayı değil, bir eğilimdir** ve tek bir girdi büyüklüğünde ölçülürse yanlış okunur. ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Dengeli, 12 değerlik akış | 1693 adım | 1261 adım | **0/480 ortanca** | | Dengesiz, 12 değerlik akış | 1693 adım | 550 adım | **295/480 ortanca** | | Dengeli, 200 değerlik akış | 98.651 adım | 13.686 adım | **0/10 akış** | Birinci ve ikinci satır arasındaki tek fark iki satırlık bir denge adımıdır; o iki satır kalıbın adımının yarısından fazlasını harcar ve **295 yanlış yanıtı** önler. Üçüncü satır, o bedelin neden ödendiğini gösterir. Tablonun ayrılan girdi sütununda iki ayrı birim durduğuna dikkat edilmelidir. İlk iki satırda birim **ortancadır**, çünkü akan veride her değer bir soru üretir ve ölçülmesi gereken şey kaç sorunun yanlış yanıtlandığıdır. Üçüncü satırda birim **akıştır**, çünkü orada sorulan şey kalıbın uzunlukla bozulup bozulmadığıdır. İki birimi karıştırmak oranları karşılaştırılamaz kılar: 295/480 ile 0/10 aynı ölçekte okunamaz. Akan veri ölçen her kalıpta bu ayrım açıkça yazılmalıdır. ## Özet - İki yığın kalıbı akan veride ortancayı, küçük yarıyı en büyük yığında ve büyük yarıyı en küçük yığında tutarak iki tepe okumasıyla verir. - Ön koşul iki yığının dengede kalmasıdır; denge adımı kaldırıldığında 480 ortancanın **295'i** yanlış çıkıyor ve 40 akışın 39'u bozuluyor. - Denge adımı kalıbın adımının yarısından fazlasını harcar: onsuz kalıp 1261 yerine 550 adım harcıyor ve oran 1,34'ten 3,08'e çıkıyor. - İlk yanlış ortanca ortalama 3,44'üncü değerde çıkıyor; kusur akışın başında oluşur ama ilk birkaç yanıt doğru olduğu için kısa bir sınamada görünmez. - Kalıbın kazancı akış uzunluğuyla büyür: oran 12 değerde 1,42, 200 değerde 7,21 ve ayrılan akış her uzunlukta sıfırdır. ## Sonraki Adım İki yığın, ortancayı yani **sıralı düzende ortadaki** değeri verdi. Ortanca özel bir durumdur; genel soru, sıralı düzende **k'ıncı** değerin ne olduğudur. Sonraki ders bu soruyu iki ayrı kalıpla yanıtlar — k boyutlu bir yığınla ve bölümlemeyle — ve ikisini de aynı kâhinle sınar. Orada ön koşul veriye değil **sorunun kendisine** dokunur: tekrarlı değerlerde "k'ıncı eleman" ile "k'ıncı ayrı değer" aynı şey değildir ve aradaki fark sayılacaktır.