Yığın Sıralaması Algoritması: Heapify ve Heap Ağacı
Merhaba! Fatih Soysal olarak, bugün size verimli ve etkili bir sıralama algoritması olan Yığın Sıralaması (Heap Sort) algoritmasını detaylı bir şekilde anlatacağım. Bu algoritma, öncelikle verileri bir yığın (heap) veri yapısı içinde düzenleyerek çalışır. Yığınlar, özel bir ikili ağaç yapısıyla temsil edilir ve belirli özelliklere sahiptir. Bu özellikler sayesinde, yığının en büyük (veya en küçük) elemanı her zaman kökte bulunur. Bu özellik, algoritmanın verimliliğini artırır. Öncelikle yığın (heap) ve heapify işlemini açıklayalım. Ardından, yığın sıralamasının nasıl çalıştığına detaylı olarak bakacağız.
Yığın (Heap) Nedir?
Bir yığın, özel bir ikili ağaçtır. Bu ağaçta, her düğümün değeri, çocuk düğümlerinin değerlerinden büyük veya eşittir (maksimum yığın) veya küçük veya eşittir (minimum yığın). Yığın, genellikle bir dizi ile temsil edilir. Bu sayede, yığının elemanlarına hızlı bir şekilde erişilebilir. Yığın sıralamasında maksimum yığın kullanılır. Yani, dizinin ilk elemanı (kök) her zaman dizideki en büyük elemandır.
Heapify İşlemi
Heapify işlemi, bir ikili ağacı yığın yapısına dönüştürmek için kullanılır. Bu işlem, ağacın alt dallarından başlayarak yukarı doğru yapılır. Her düğüm için, düğümün değeri çocuk düğümlerinin değerleriyle karşılaştırılır. Eğer düğümün değeri çocuk düğümlerinin değerlerinden küçükse, düğümün değeri çocuk düğümlerinden biriyle yer değiştirilir. Bu işlem, ağacın kök düğümüne ulaşana kadar tekrarlanır. Sonuç olarak, ağaç bir yığın haline gelir ve en büyük eleman kökte bulunur.
Örneğin, şu diziyi ele alalım: [1, 12, 9, 5, 6, 10]. Bu diziyi yığın yapısına dönüştürmek için heapify işlemi uygulanır. Bu işlem sonucunda dizi [12, 10, 9, 5, 6, 1] gibi bir yapıya dönüşecektir. Burada 12, yani en büyük eleman kökte yer almaktadır.
Yığın Sıralaması Algoritması
Yığın sıralaması algoritması, öncelikle girilen diziyi bir maksimum yığına dönüştürerek çalışır. Daha sonra, yığının en büyük elemanı (kök) ile yığının son elemanı yer değiştirilir. Yığının boyutu bir azaltılır ve kalan yığın tekrar yığın yapısına dönüştürülür. Bu işlem, yığının boyutu sıfıra ulaşana kadar tekrarlanır. Sonuç olarak, dizi sıralanmış olur.
Bu algoritmanın zaman karmaşıklığı O(n log n)’dir. Bu, algoritmanın büyük veri setleri için de oldukça verimli olduğu anlamına gelir. Ayrıca, algoritma yerinde (in-place) sıralama yapar, yani ekstra bellek kullanmaz. Bu da onu daha da verimli kılar.
Yığın Sıralaması Kod Örneği (Python):
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
# Örnek kullanım
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sıralanmış dizi:", arr)
Bu kod, yığın sıralamasını adım adım göstermektedir. Öncelikle heapify fonksiyonu, yığın yapısını oluşturur. Sonrasında heapSort fonksiyonu, yığın yapısını kullanarak sıralamayı gerçekleştirir.
Yığın sıralaması, özellikle büyük veri kümeleri için oldukça etkili bir algoritmadır. Ancak, bazı durumlarda, diğer sıralama algoritmaları daha hızlı olabilir. Dolayısıyla, hangi algoritmanın kullanılacağı, veri setinin büyüklüğüne ve özelliklerine bağlıdır. Daha fazla bilgi için fatihsoysal.com adresini ziyaret edebilirsiniz.
Ayrıca, konu hakkında daha fazla bilgi edinmek için GeeksforGeeks ve Wikipedia kaynaklarına göz atabilirsiniz.
#Etiketler: Yığın Sıralaması, Heap Sort, Heapify, Heap Ağacı, Veri Yapıları, Algoritmalar, DSA, Başlangıç Seviyesi, Programlama, Python