Temel Algoritma ve Veri Yapıları: Binary Search, Hash Map ve Heap Örnekleri

Bu makale, yazılıma yeni başlayanlar ve pratik uygulama arayan geliştiriciler için Binary Search (ikili arama), Hash Map (anahtar-değer yapıları) ve Heap (öncelik kuyruğu) veri yapılarını açıklayan, örneklerle desteklenen bir rehberdir. Her bölümde tanım, ne zaman kullanılacağı, Python örnekleri ve zaman karmaşıklığına kısa notlar bulunmaktadır.

1. Binary Search (İkili Arama)

Binary Search, sıralı (sorted) bir dizide hedef değeri hızlıca bulmak için kullanılan bir arama algoritmasıdır. Temel fikir, aranan aralığı yarıya bölerek ilerlemektir. Bu yöntemin temel gereksinimi veri kümesinin önceden sıralanmış olmasıdır (Wikipedia — Binary search; eğitim notları için de bkz. Patika.dev Binary Search).

1. Aralığın ortancası (mid) hesaplanır.
2. Ortanca eleman hedefe eşitse bulunur; değilse hedefin hangi yarıda olduğuna göre aralık güncellenir.
3. Aralık boşalana kadar 1-2 adım tekrarlanır.

Temel iteratif Python örneği (küçük ve anlaşılır):

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

Zaman karmaşıklığı: O(log n) (ortalama ve en kötü durumda). Bellek: iteratif versiyon için O(1), özyinelemeli (recursive) versiyon için O(log n) çağrı yığını olabilir.

Yanlış kullanım hataları ve ipuçları:

• Dizi sıralı değilse doğru sonuç vermez; girdi doğrulaması yapın.
• Off-by-one hatalarına dikkat edin: < ve <= karşılaştırmalarını test edin.
• Tekrarlayan elemanlar varsa sol/sağ sınırı bulmak için algoritmayı küçükçe değiştirin (first/last occurrence).

2. Hash Map (Anahtar — Değer Yapıları)

Hash Map (veya hash table), anahtar-değer çiftlerini depolayan ve ortalama O(1) zamanda erişim sağlayabilen bir veri yapısıdır. Ana fikir: anahtarlar bir hash fonksiyonuyla dizideki bir kovana (bucket) dönüştürülür; aynı kovana düşenler için çarpışma (collision) yönetimi gerekir. Genel bilgiler için genel kaynaklara bakılabilir (Kaynak: genel veri yapıları notları).

Çarpışma yönetimi yaklaşımları:

• Zincirleme (chaining): Her kovanda bağlı liste veya dinamik dizi tutulur.
• Açık adresleme (open addressing): Yeni bir pozisyon aranır (linear probing, quadratic probing vb.).

Python'da yerleşik dict tipini kullanmak en yaygın pratiktir. Basit bir frekans sayma örneği:

def count_freq(items):
counts = {}
for x in items:
counts[x] = counts.get(x, 0) + 1
return counts

Zaman karmaşıklığı (ortalama): arama/ekleme/silme O(1). Ancak kötü hash fonksiyonu veya aşırı çarpışma durumunda en kötü durumda O(n) olabilir. Bu nedenle pratikte iyi hash fonksiyonları ve yeniden boyutlandırma (resize) stratejileri önemlidir.

Pratik ipuçları:

• Anahtar olarak mutabl (değişebilir) tipleri kullanmayın; hashlenebilir (immutable) tip tercih edin.
• Bellek-kullanımı erişim hızını etkiler; büyük tablolar için yük faktörünü (load factor) düşünün.
• Özel hash gereksinimleriniz varsa test ve benchmark yapın.

3. Heap (Öncelik Kuyruğu)

Heap, elemanları öncelik sırasına göre organize eden bir veri yapısıdır. En yaygın uygulama binary heap'tir; bu yapı hem dizi (array) üzerinde saklanır hem de min-heap veya max-heap olarak kullanılabilir. Min-heap'te en küçük değer kökte, max-heap'te en büyük değer köktedir.

Binary heap array gösterimi için indeks ilişkileri (0 tabanlı):

• parent(i) = (i - 1) // 2
• left(i) = 2 * i + 1
• right(i) = 2 * i + 2

Sık kullanılan işlemler ve karmaşıklıkları:

• peek (köke bakma): O(1)
• push (ekleme): O(log n)
• pop (kökü çıkarma): O(log n)
• heapify (diziyi heap'e çevirme): O(n)

Python'da heapq modülü min-heap sağlar. Kısa örnek:

import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
smallest = heapq.heappop(heap) # 2

Uygulama alanları: öncelik sıralama, zaman planlayıcı (scheduler), Dijkstra benzeyen algoritmalar, sürekli veri akışında top-k gibi işlemler.

4. Hangi Durumda Hangi Yapıyı Seçmelisiniz?

Kısa karar kılavuzu:

• Eğer veriniz sıralıysa ve arama yapacaksanız: Binary Search hızlı ve basit bir tercihtir (O(log n)).
• Sık anahtar tabanlı erişimler, güncellemeler ve eşleşmeler varsa: Hash Map uygundur (ortalama O(1)).
• Önceliklere göre sürekli en büyük/en küçük elemanı almak gerekiyorsa: Heap (priority queue) tercih edilir.

5. Uygulama ve Test Kontrol Listesi (Experience)

• Binary Search: girişin sıralı olduğunu doğrulayın; boş dizi ve tek eleman durumlarını test edin; duplicate senaryoları için first/last occurrence testleri ekleyin.
• Hash Map: custom key veya karma fonksiyon kullanıyorsanız çarpışma testleri yapın; boyutlandırma (resize) ve bellek kullanımını gözlemleyin.
• Heap: push/pop sıralarını test edin; heapify ile başlangıç performansını karşılaştırın; top-k senaryolarında bellek sınırlarını değerlendirin.
• Benchmark: gerçek veriyle mikro-benchmark yapın; farklı giriş boyutları ve desenleri için zaman ve bellek ölçün.

6. Küçük Alıştırmalar

1. Sorted bir dizide ilk eşleşmenin indeksini bulan binary search implement edin (first occurrence).
2. Bir metindeki kelime frekanslarını Hash Map kullanarak hesaplayın ve en sık 10 kelimeyi bulun.
3. Gelen bir sayılar akışında k en büyük sayıyı sürekli takip etmek için heap kullanın (streaming top-k).

Kaynaklar ve ileri okuma:

• Binary search — Wikipedia (algoritma tanımı ve analizleri).
• Binary Search Dersi — Patika.dev (eğitsel açıklamalar ve örnekler).
• Binary Search Tree Dersi — Patika.dev (ağaç temelli arama yapıları için ek kaynak).
• Binary Search videolu anlatım — YouTube (görsel öğrenme için).

Not: Bu makale temel kavramları ve uygulama örneklerini içerir. Gerçek projelerde performans gereksinimine göre ek profil oluşturma, bellek optimizasyonu ve test stratejileri uygulamanız önerilir.