Yığın Sıralama Algoritması (İle) Code in Python hem de C++)

Yığın Sıralama Algoritması Nedir?

Yığın Sıralama (Heap Sort), popüler ve hızlı sıralama algoritmalarından biridir. Tamamen ikili ağaç veri yapısı üzerine kuruludur. En büyük elemanı bulup en üste yerleştirerek maksimum yığını (max heap) oluşturacağız. Bunu ikili ağacın üst düğümüne yerleştireceğiz.

Diyelim ki bir dizi verildi, veri = [10,5, 7, 9, 4, 11, 45, 17, 60].

Dizide, eğer i-th (i=0,1,2,3 …) indeksi bir ebeveyn düğüm ise, o zaman (2i+1) ve (2i+2) sol ve sağ çocukları olacaktır. Bu diziyle tam bir ikili ağaç oluşturmak şöyle görünecektir:

Dizinin başından sonuna kadar yığınlaştırma işlemini yapacağız. Başlangıçta, diziyi bir ağaca dönüştürürsek yukarıdaki gibi görünecektir. Herhangi bir yığın özelliğini (min-yığın veya max yığın) korumadığını görebiliriz. Tüm düğümler için yığınlaştırma işlemini yaparak sıralanmış diziyi elde edeceğiz.

Yığın Sıralamanın Uygulanması

Yığın sıralama algoritmasının bazı kullanımları aşağıda verilmiştir:

• “Öncelik Kuyruklarının” oluşturulması yığın sıralamasını gerektirir. Çünkü yığın sıralaması, her ekleme yapıldıktan sonra öğeyi sıralanmış halde tutar.
• Yığın Veri Yapısı k'yı bulmada etkilidir^th Belirli bir dizideki en büyük öğe.
• Linux Çekirdeği yığın sıralamasını varsayılan olarak kullanır sıralama algoritması çünkü O (1) uzay karmaşıklığına sahiptir.

Örnekle Yığın Sıralaması Oluşturun

Burada, aşağıdaki tamamlanmış ikili ağaçtan bir maksimum yığın oluşturacağız.

Yaprak düğümleri 17, 60, 4, 11 ve 45'tir. Hiçbir alt düğümleri yoktur. Bu yüzden yaprak düğümlerdir. Bu yüzden, heapify yöntemini üst düğümlerinden başlatacağız. İşte adımlar:

) 1 Adım En soldaki alt ağacı seçin. Alt düğümler daha büyükse ana düğümü alt düğümle değiştirin.

Burada ana düğüm 9'dur. Alt düğümler ise 17 ve 60'tır. 60 en büyüğü olduğundan, 60 ve 9, eşitliği korumak için yer değiştirecektir. maksimum yığın.

) 2 Adım Şimdi en soldaki alt ağaç yığın halindedir. Bir sonraki ana düğüm 7'dir. Bu ebeveynin iki alt düğümü vardır ve en büyüğü 45'tir. Yani 45 ve 7 yer değiştirecektir.

) 3 Adım 60 ve 4 nolu düğümler 5 nolu ana düğüme sahiptir. “5”, 60 nolu alt düğümden daha küçük olduğu için değiştirilecektir.

) 4 Adım Artık düğüm 5'in alt düğümü 17,9 var. Bu, max heap özelliğini korumak değildir. Yani 5'in yerine 17 getirilecek.

) 5 Adım 10.node önce 60 ile, sonra da 17 ile yer değiştirecek. İşlem aşağıdaki gibi olacak.

) 6 Adım 5. adıma kadar maksimum yığını oluşturduk. Her ana düğüm, alt düğümlerinden daha büyüktür. Kök düğüm maksimum değere (60) sahiptir.

Not: Sıralanmış diziyi oluşturmak için maksimum değerli düğümü ardılıyla değiştirmemiz gerekir.

Bu işleme “extract maksimum”. Maksimum düğüm 60 olduğundan, konumunu 0'ıncı dizine sabitleyeceğiz ve 60 düğümü olmadan yığın oluşturacağız.

) 7 Adım 60 çıkarıldığında, bir sonraki maksimum değer 45'tir. "Ex" işlemini yapacağız.trac"t Max" ifadesi yine 45. düğümden geliyor.

Bu sefer 45'i alacağız ve kök düğümü halefi 17 ile değiştireceğiz.

gerçekleştirmemiz gerekiyor”Extract Maks”tüm öğeler sıralanana kadar.

Bu adımları uyguladıktan sonra biz de...tracTüm maksimum değerleri alırsak, aşağıdaki diziyi elde edeceğiz.

İkili Yığın Nedir?

İkili Yığın bir nevi tamdır ikili ağaç veri yapısı. Bu tür ağaç yapısında ana düğüm, alt düğümlerden ya daha büyük ya da daha küçüktür. Ana düğüm daha küçükse yığına "Min Heap" adı verilir ve ana düğüm daha büyükse yığına "Max Heap" adı verilir.

Aşağıda minimum yığın ve maksimum yığın örnekleri verilmiştir.

Yukarıdaki şekilde “Min Heap” dikkat ederseniz ana düğüm her zaman alt düğümlerden daha küçüktür. Ağacın başında en küçük değer olan 10’u bulabiliriz.

Benzer şekilde, “Max Heap” için ana düğüm her zaman alt düğümlerden daha büyüktür. “Max Heap” için maksimum eleman baş düğümde mevcuttur.

“Heapify” nedir?

"Heapify", düğümün konumunu garantileyen yığın ilkesidir. Heapify'da, maksimum yığın her zaman ebeveyn ve çocukla bir ilişki sürdürür ve bu ebeveyn düğümü çocuk düğümlerinden daha büyük olacaktır.

Örneğin, yeni bir düğüm eklendiğinde, yığını yeniden şekillendirmemiz gerekir. Ancak, düğümleri değiştirmemiz veya yerlerini değiştirmemiz ya da diziyi yeniden düzenlememiz gerekebilir. Bu yeniden şekillendirme süreci...ping Bir yığına "yığınlaştırma" denir.

İşte heapify'ın nasıl çalıştığına dair bir örnek:

Heapify için adımlar şunlardır:

) 1 Adım Düğüm 65, düğüm 60'ın sağ çocuğu olarak eklendi.

) 2 Adım Yeni eklenen düğümün üst düğümden büyük olup olmadığını kontrol edin.

) 3 Adım Ana düğümden daha büyük olduğu için sağdaki çocuğu ebeveyniyle değiştirdik.

Yığın nasıl inşa edilir

Yığın oluşturmadan veya bir ağacı yığınlaştırmadan önce, onu nasıl depolayacağımızı bilmemiz gerekir. Yığın tam bir ikili ağaç olduğundan, bir dizi yığının verilerini tutmak için.

Diyelim ki bir dizi toplam n eleman içeriyor. Eğer “i” inci indeks bir üst düğümse, o zaman sol düğüm indekste olacaktır (2i+1)ve sağ düğüm dizinde olacak (2i+2). Dizi indeksinin 0'dan başladığını varsayıyoruz.

Bunu kullanarak, maksimum yığını aşağıdaki gibi bir diziye kaydedelim:

Heapify algoritması heap özelliğini korur. Eğer ebeveyn uç değere sahip değilse (daha küçük veya daha büyük), en uç çocuk düğümüyle takas edilir.

Maksimum yığını yığın haline getirmenin adımları şunlardır:

) 1 Adım Yaprak düğümden başlayın.

) 2 Adım Ebeveyn ve çocuklar arasındaki maksimum değeri bulun.

) 3 Adım Alt düğümün değeri üst düğümden daha büyükse düğümleri değiştirin.

) 4 Adım Bir seviye yukarı çıkın.

) 5 Adım Dizin 2,3,4'a ulaşana veya ağacın tamamını sıralayana kadar 0 adımlarını izleyin.

İşte yinelemeli yığınlaştırma (maksimum yığın) için sözde kod:

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Sözde Code Yığın Sıralama için

Yığın sıralama algoritmasının sözde kodu şöyledir:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Yığın Sıralama Örneği Code in C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Çıktı:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Yığın Sıralama Örneği Code in Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Çıktı:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Heap Sort'un Zaman ve Mekan Karmaşıklık Analizi

Yığın sıralaması için analiz edebileceğimiz Zaman karmaşıklığı ve Uzay karmaşıklığı var. Zaman karmaşıklığı için şu durumlara sahibiz:

1. En iyi senaryo
2. Ortalama Vaka
3. En kötü durumda

Yığın tam bir ikili ağaç üzerinde uygulanır. Yani ikili ağacın alt seviyesinde maksimum sayıda düğüm olacaktır. Alt düzeyde n düğüm varsa, üst düzeyde n/2 düğüm bulunur.

Bu örnekte Düzey 3'te dört öğe, düzey 2'de iki öğe ve düzey 1'de bir öğe bulunmaktadır. Toplam n sayıda öğe varsa, yükseklik veya toplam seviye şu şekilde olacaktır: Giriş₂(N). Bu nedenle, tek bir öğenin eklenmesi maksimum Log(n) yineleme gerektirebilir.

Yığından maksimum değeri almak istediğimizde, sadece kök düğümü alırız. Sonra tekrar heapify'ı çalıştırırız. Her heapify Giriş₂(N) zaman. EskitracMaksimumu bulmak O(1) zaman alır.

Yığın Sıralama Algoritması için En İyi Durum Zaman Karmaşıklığı

Dizideki tüm öğeler zaten sıralandığında, yığının oluşturulması O(n) zaman alacaktır. Çünkü liste sıralanırsa bir öğenin eklenmesi O(1) olan sabit süreyi alacaktır.

Bu nedenle, en iyi durumda bir maksimum yığın veya minimum yığın oluşturmak O(n) zaman alacaktır.

Yığın Sıralama Algoritması için Ortalama Durum Zaman Karmaşıklığı

Bir öğe veya dosya eklemektracMaksimum maliyete ulaşmak O(log(n)) zaman alır. Dolayısıyla, yığın sıralama algoritmasının ortalama durum zaman karmaşıklığı şöyledir: O(n log(n)).

Yığın Sıralama Algoritması için En Kötü Durum Zaman Karmaşıklığı

Ortalama duruma benzer şekilde, en kötü senaryoda, n kez yığınlama yapmak zorunda kalabiliriz. Her yığınlama O(log(n)) zamana mal olacaktır. Bu nedenle, en kötü durum zaman karmaşıklığı şu şekilde olacaktır: O(n log(n)).

Yığın Sıralama Algoritması için Uzay Karmaşıklığı

Yığın sıralaması yerinde tasarlanmış bir algoritmadır. Bu, görevi gerçekleştirmek için ekstra veya geçici belleğe ihtiyaç duyulmadığı anlamına gelir. Uygulamayı görürsek, düğümlerin değişimini gerçekleştirmek için swap() kullandığımızı fark edeceğiz. Başka bir liste veya diziye gerek yoktu. Bu nedenle, alan karmaşıklığı O(1)'dir.

SSS