İçeriğe geç

Menü

Berk Akademi
Yorumlar Google yorumları Özel Ders Başvuru Ücretsiz ön görüşme Ana Sayfa

Heap Sort Nasıl Çalışır? Yığın Sıralaması Adım Adım Örnek

heap-sort-nasil-calisir-yigin-siralama-adim-adim-ornek
Bu yazıda neler var?
  1. Heap Sort hangi adımlarla sıralama yapar?
  2. Bir dizi max heap olarak nasıl düşünülür?
  3. Örnek dizi üzerinde heap oluşturma ve eleman çıkarma
  4. Heap Sort neden O(n log n) zaman alır?
  5. Python ile Heap Sort nasıl uygulanır?
  6. Uygulamada hangi Heap Sort hatalarına dikkat edilir?
  7. Sık Sorulan Sorular

Heap Sort, yani yığın sıralaması, bir diziyi önce max heap yapısına dönüştürür. Ardından kökte bulunan en büyük değeri dizinin sıralı sonuna taşır, küçülen heap üzerinde heapify işlemini uygular ve aynı adımları kalan elemanlar için tekrarlar.

Bu nedenle algoritmayı anlamanın anahtarı, heap yapısının tamamını ezberlemekten çok kökün nasıl seçildiğini, heap boyutunun nasıl küçüldüğünü ve bozulan düzenin nasıl yeniden kurulduğunu izlemektir.

Heap Sort hangi adımlarla sıralama yapar?

Heap Sort, diziyi dört temel adımın tekrarlanmasıyla sıralar. Max heap kullanıldığında her turda en büyük değer belirlenir ve dizinin sağ tarafında doğru konumuna yerleştirilir.

  1. Max heap oluşturma: Dizideki değerler, her ebeveynin çocuklarından büyük veya onlara eşit olduğu bir yapıya dönüştürülür. Böylece en büyük değer kökte bulunur.
  2. Kökü sona taşıma: Kök düğümdeki en büyük değer, heap olarak kabul edilen bölümün sonundaki değerle yer değiştirir. Bu değer artık sıralı bölümde kalır.
  3. Heap boyutunu küçültme: Az önce sona taşınan değer heap alanından çıkarılır. Dizi fiziksel olarak küçülmez, yalnızca heap sınırı bir konum sola çekilir.
  4. Kalan yapıyı düzenleme: Kök konumuna gelen yeni değer, max heap kuralını bozmuş olabilir. Heapify işlemi bu değeri gerektiği kadar aşağı taşıyarak kalan bölümün düzenini yeniden kurar.

İkinci adımdan sonra en büyük değer sağ tarafta birikir. Her turda heap alanı bir eleman küçüldüğü için, algoritma sonunda dizi küçükten büyüğe sıralanır. Bu akışın heap kurma ve ardından kökten eleman çıkarma olmak üzere iki aşamada ele alındığı MIT OpenCourseWare heap sort ders notlarında da görülebilir.

Bir dizi max heap olarak nasıl düşünülür?

Bir dizi max heap olarak nasıl düşünülür?

Max heap yapısında her ebeveyn düğümün değeri, doğrudan bağlı olduğu çocukların değerlerinden küçük olamaz. Bu kural sağlandığında en büyük değer her zaman kökte bulunur. Ancak kökten aşağı doğru ilerleyen tüm değerlerin tamamen sıralı olması gerekmez.

Heap, çoğunlukla tam ikili ağaç biçiminde düşünülür ve bellekte dizi olarak tutulur. 0 tabanlı bir dizide i indeksindeki düğümün çocukları şu konumlarda bulunur:

  • Sol çocuk: 2i + 1
  • Sağ çocuk: 2i + 2

[4, 10, 3, 5, 1] dizisi ağaç biçiminde şöyle gösterilebilir:

        4
      /   
    10     3
   /  
  5    1

Bu görünümde kökün çocuklarından biri olan 10, ebeveyni 4'ten büyük olduğu için yapı henüz max heap değildir. Heapify sırasında bu tür ihlaller aşağı doğru giderilerek düzeltilir.

Bir dizide son ebeveyn düğümünün indeksi n // 2 - 1 formülüyle bulunur. Beş elemanlı örnekte 5 // 2 - 1 = 1 sonucuna ulaşılır. Bu nedenle heap oluşturma işlemi genellikle 1 numaralı indeksten başlayıp 0 numaralı köke doğru ilerler. Priority queue yapılarında da benzer heap mantığı, önceliği yüksek elemana erişimi düzenlemek için kullanılır; Heap Sort ise bu yapıyı doğrudan sıralama amacıyla işletir.

Örnek dizi üzerinde heap oluşturma ve eleman çıkarma

[4, 10, 3, 5, 1] dizisi, son ebeveyn düğümünden köke doğru heapify uygulanarak bir max heap hâline getirilir. Sıfır tabanlı dizi gösteriminde son ebeveyn düğümünün indisi floor(n / 2) - 1 ifadesiyle bulunur. Beş elemanlı bu dizide işlem indisi 1 olan düğümden başlar.

İndisi 1 olan 10 düğümünün çocukları 5 ve 1 olduğu için bu alt ağaçta değişiklik yapılmaz. Ardından kökteki 4 değeri, daha büyük olan çocuğu 10 ile yer değiştirir. 4 değeri yeni konumunda 5 değerinden küçük kaldığı için bir kez daha aşağı taşınır ve max heap [10, 5, 3, 4, 1] olarak oluşur.

Aşama Heap boyutu Dizinin aldığı hâl Yapılan işlem
Başlangıç 5 [4, 10, 3, 5, 1] Son ebeveyn düğümünden başlayarak heapify uygulanır.
Max heap oluşturuldu 5 [10, 5, 3, 4, 1] Her ebeveyn, çocuklarından büyük veya onlara eşit hâle gelir.
1. çıkarma 4 [5, 4, 3, 1, 10] 10 sona taşınır, kalan bölüm yeniden düzenlenir.
2. çıkarma 3 [4, 1, 3, 5, 10] 5 sıralı bölüme eklenir, heap boyutu küçültülür.
3. çıkarma 2 [3, 1, 4, 5, 10] 4 sona alınır ve iki elemanlık heap düzenlenir.
4. çıkarma 1 [1, 3, 4, 5, 10] Son iki eleman karşılaştırılarak sıralama tamamlanır.

Her çıkarma işleminde kökteki en büyük değer dizinin sağındaki sıralı bölüme taşınır. Heap boyutu soldaki bölümle sınırlanırken sıralı bölüm sağdan büyür. Bu yapı ikili arama ağacıyla karıştırılmamalıdır; heap'te sol çocuğun kökten küçük, sağ çocuğun kökten büyük olması gibi bir arama ağacı kuralı bulunmaz.

Heap Sort neden O(n log n) zaman alır?

Heap Sort neden O(n log n) zaman alır?

Heap Sort'un toplam zaman karmaşıklığı O(n log n) değeridir. Bunun ilk nedeni, dizinin max heap hâline getirilmesinin alt ağaçların yüksekliklerine göre birlikte değerlendirilmesi ve toplamda O(n) sürmesidir. Bu yöntem, her elemanı köke tek tek ekleyip yeniden düzenlemekten daha verimlidir.

Bir kök çıkarıldıktan sonra son eleman köke alınır ve heapify bu değeri aşağı doğru taşıyabilir. İkili heap'in her seviyesinde düğüm sayısı yaklaşık iki katına çıktığı için, n elemanlı ağacın yüksekliği yaklaşık log₂ n seviyesindedir. Bu nedenle bir heapify işleminin en kötü durum maliyeti O(log n) olur.

En büyük elemanların çıkarılması yaklaşık n kez tekrarlandığından, bu aşamanın maliyeti n adet O(log n) işlemiyle O(n log n) olur. İlk heap oluşturma maliyeti bunun yanında daha küçük kaldığı için toplam sonuç değişmez. Bu karmaşıklık ve algoritmanın çalışma özellikleri Princeton Algorithms kaynaklarında da açıklanır.

Heap Sort, sıralama için ayrı bir dizi oluşturmak yerine elemanları aynı dizi içinde takas eder. Bu nedenle yerinde sıralama yaklaşımına uyar. Ancak eşit değerlere sahip kayıtların başlangıçtaki göreli sırasını koruma garantisi yoktur. Örneğin 2A ve 2B aynı anahtara sahip iki kayıt olsun. Kökün sona taşınması sırasında yapılan takaslar, sonuçta 2B kaydını 2A kaydının önüne geçirebilir.

Python ile Heap Sort nasıl uygulanır?

Python'da Heap Sort, diziyi önce max heap hâline getirir, ardından kökteki en büyük değeri dizinin son kullanılabilir konumuna taşır. Her takastan sonra küçülen heap üzerinde heapify çağrılarak yapı yeniden düzenlenir.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        heapify(arr, end, 0)

    return arr


numbers = [4, 10, 3, 5, 1]
print(heap_sort(numbers))

İlk döngü, n // 2 - 1 indeksinden başlayıp köke doğru ilerler. Bu indeks, son ebeveyn düğümünü gösterir. Yaprak düğümlerin çocuğu olmadığı için onlar üzerinde ayrıca heapify çalıştırmak gerekmez.

heapify içinde sol çocuk için 2 * i + 1, sağ çocuk için 2 * i + 2 hesaplanır. Bu iki değer ve mevcut düğüm karşılaştırılır. En büyük değer çocuklardan birindeyse takas yapılır ve değişen alt ağaçta işlem sürdürülür.

heap_sort içindeki ikinci döngüde kök, end indeksindeki elemanla takas edilir. Takas edilen en büyük değer artık doğru sıralama konumundadır. Bu nedenle sonraki heapify çağrısında aktif heap boyutu end olarak verilir. Programın çıktısı [1, 3, 4, 5, 10] olur.

Fonksiyon diziyi yerinde değiştirir, yani sıralama için ikinci bir dizi oluşturmaz. Aynı dizi sıralanır ve heap_sort bu diziyi geri döndürür. Heap kurma aşamasının maliyeti O(n), tüm sıralama işleminin maliyeti O(n log n) olarak değerlendirilir. Bu analiz, Princeton University'nin Robert Sedgewick ve Kevin Wayne imzalı Algorithms, 4th Edition, 2011 materyalindeki Heap Sort açıklamasıyla uyumludur.

Uygulamada hangi Heap Sort hatalarına dikkat edilir?

Heap Sort uygulamasında hatalar çoğunlukla heap kurma sınırının, aktif heap boyutunun veya heap ile ikili arama ağacının özelliklerinin yanlış anlaşılmasından kaynaklanır.

Heap kurma döngüsünü yanlış indeksten başlatmak

Heap kurma döngüsünü son elemandan başlatmak gereksizdir çünkü son eleman bir yaprak düğümdür. Daha önemlisi, döngü son ebeveyn düğümünü atlayarak başlatılırsa bazı alt ağaçlar max heap özelliğini kazanamaz.

  • Kontrol: Başlangıç indeksi n // 2 - 1 olmalı.
  • Kontrol: Döngü köke doğru ilerlemeli ve -1 sınırına kadar çalışmalı.
  • Kontrol: Her ebeveyn için heapify(arr, n, i) çağrılmalı.

Kök takasından sonra heap boyutunu küçültmemek

Her turda kökteki en büyük değer dizinin sonuna taşınır. Bu eleman artık heap'in parçası olmadığı hâlde eski heap boyutuyla heapify çağrılırsa sıralanmış bölüm yeniden değiştirilir ve sonuç bozulabilir.

  • Kontrol: Takastan sonra aktif heap boyutu bir azaltılmalı.
  • Kontrol: heapify çağrısında ikinci parametre olarak end kullanılmalı.
  • Kontrol: Sıralanmış bölümün başlangıç indeksine kadar korunması sağlanmalı.

Heap yapısını ikili arama ağacıyla karıştırmak

Max heap'te temel koşul, her ebeveynin çocuklarından büyük veya onlara eşit olmasıdır. Sol ve sağ alt ağaçların kendi içinde sıralı olması gerekmez. İkili arama ağacında ise genellikle sol alt ağaçtaki değerler düğümden küçük, sağ alt ağaçtaki değerler düğümden büyüktür. Bu iki yapı aynı ağaç biçimine sahipmiş gibi düşünülürse hem karşılaştırma mantığı hem de dizi indeksleri yanlış uygulanabilir.

Uygulamayı tamamladıktan sonra ebeveyn çocuk ilişkilerini ve döngü sınırlarını farklı örneklerle kontrol etmek için algoritmik düşünme testi yardımcı bir alıştırma olarak kullanılabilir.

Sık Sorulan Sorular

Heap Sort kararlı bir sıralama algoritması mıdır?

Heap Sort kararlı bir sıralama algoritması değildir; aynı değere sahip elemanların dizideki göreli sırası takaslar sırasında değişebilir.

Heap oluşturma neden son elemandan değil son ebeveyn düğümünden başlar?

Heap oluşturma son ebeveyn düğümünden başlar çünkü yaprak düğümlerin çocuğu yoktur ve tek başlarına heap koşulunu zaten ihlal edemezler.

Heap Sort ek bir dizi kullanmadan nasıl çalışır?

Heap Sort ek bir dizi kullanmadan çalışır çünkü heap, giriş dizisinin kendi indeksleri üzerinde tutulur ve en büyük eleman takaslarla dizinin sonuna yerleştirilir.

Heap ile ikili arama ağacı arasındaki temel fark nedir?

Heap'te yalnızca ebeveyn ile çocuklar arasındaki büyüklük ilişkisi korunur; ikili arama ağacında ise sol ve sağ alt ağaçların düğüme göre sıralanması gerekir.

Heap Sort'u doğru uygulamak için heap kurma başlangıcını, aktif heap boyutunu ve kullanılan ağaç yapısının sıralama koşulunu her adımda birlikte kontrol etmek gerekir.

Bu içerik aradığın cevabı verdi mi?
Yanıtın, hangi yazıları geliştirmemiz gerektiğini anlamamıza yardımcı olur.
Bu içeriğin üretilmesinde yapay zeka araçlarından destek alınmıştır.

Bu konudan sonra ne okuyabilirsin?

Tüm yazılar

İlgili Eğitimler

Berk Keskin, yazılım geliştirici ve eğitmen
Yazar

Berk Keskin Kimdir?

Yazılıma 12 yaşında başladı; İzmir Ekonomi Üniversitesi'ni bölüm birincisi ve yüksek şeref öğrencisi olarak tamamladı. Bugün yalnızca eğitim vermekle kalmıyor, sektörde aktif olarak yazılım projeleri geliştiriyor ve gerçek dünya deneyimini birebir derslerine taşıyor. Ezberden uzak, mühendislik zihniyetini merkeze alan sürdürülebilir öğrenme sistemleri tasarlayarak sorgulayan, üreten ve problem çözebilen yeni nesil yazılımcılar yetiştiriyor.

Sektörel Deneyim & Projeler

  • Ticarify Entegrasyon Yazılım logosu CEO Ticarify Entegrasyon YazılımPazaryerleri ve e-ticaret sitelerine otomatik e-fatura kesimi, sipariş ve kargo takibi hizmetleri sunan e-Dönüşüm platformunun API mimarisini ve yazılım ekibini yönetmektedir.
  • Benim Düğünüm logosu CEO Benim DüğünümDijital etkinlik ve anı paylaşım platformu.
  • Siberdizayn logosu Yazılım Ekibi Lideri SiberdizaynYüksek anlık oyuncu trafiğine sahip oyun kontrol panelleri ve sunucu altyapıları geliştiren yazılım ekibine liderlik etmektedir.
  • MEDYOGRAFYA 360° Dijital Çözümler logosu Dijital Strateji Lideri MEDYOGRAFYA 360° Dijital ÇözümlerŞirketlerin dijital çözümlerde uzun vadede nasıl ilerleyeceğini planlamasına ve dijital dönüşüm süreçlerini yönetmesine destek olmaktadır.
  • İzmir Ekonomi Üniversitesi logosu Danışma Kurulu Üyesi İzmir Ekonomi ÜniversitesiMezun olduğu üniversitesinde, Bilgisayar Programcılığı bölümünün akademik müfredatını güncel sektör ihtiyaçlarına göre şekillendirmek adına Danışma Kurulu'nda görev almaktadır.
WhatsApp Hemen Ara