heap sort c with examples
Örneklerle Yığın Sıralamaya Giriş.
Heapsort, en verimli ayıklama tekniklerinden biridir. Bu teknik, verilen sıralanmamış diziden bir yığın oluşturur ve ardından diziyi sıralamak için öbeği yeniden kullanır.
Heapsort, karşılaştırmaya dayalı bir sıralama tekniğidir ve ikili yığın kullanır.
=> Kolay C ++ Eğitim Serisini Okuyun.
.jar dosyaları nasıl çalıştırılır
Ne öğreneceksin:
İkili Yığın Nedir?
İkili bir yığın, tam bir ikili ağaç kullanılarak temsil edilir. Tam bir ikili ağaç, her seviyedeki tüm düğümlerin yaprak düğümler ve düğümler dışında tamamen dolu olduğu bir ikili ağaçtır.
Bir ikili yığın veya basitçe bir yığın, öğelerin veya düğümlerin, kök düğümün iki alt düğümünden daha büyük olacağı bir şekilde depolandığı tam bir ikili ağaçtır. Buna maksimum yığın da denir.
İkili yığındaki öğeler, aynı zamanda, kök düğümün iki alt düğümden daha küçük olduğu min-yığın olarak da depolanabilir. Bir yığını bir ikili ağaç veya bir dizi olarak temsil edebiliriz.
Bir yığın bir dizi olarak temsil edilirken, indeksin 0'dan başladığını varsayarak, kök eleman 0'da saklanır. Genel olarak, eğer bir üst düğüm I konumunda ise, o zaman sol alt düğüm konumdadır (2 * I + 1) ve sağ düğüm (2 * I +2) 'de.
Genel Algoritma
Aşağıda, yığın sıralama tekniği için genel algoritma verilmiştir.
- Verilen verilerden, kök yığının en yüksek öğesi olacak şekilde bir maksimum yığın oluşturun.
- Kökü, yani en yüksek öğeyi yığından kaldırın ve onu yığının son öğesi ile değiştirin veya değiştirin.
- Ardından, maksimum yığın özelliklerini ihlal etmemek için maksimum yığın ayarlayın (yığın oluşturma).
- Yukarıdaki adım, yığın boyutunu 1 azaltır.
- Yığın boyutu 1'e düşene kadar yukarıdaki üç adımı tekrarlayın.
Verilen veri kümesini artan sırada sıralamak için genel algoritmada gösterildiği gibi, önce verilen veriler için bir maksimum yığın oluştururuz.
Aşağıdaki veri kümesiyle maks. Yığın oluşturmak için bir örnek alalım.
6, 10, 2, 4, 1
Bu veri seti için aşağıdaki gibi bir ağaç oluşturabiliriz.
Yukarıdaki ağaç gösteriminde, parantez içindeki sayılar dizideki ilgili konumları temsil eder.
Yukarıdaki gösterimin maksimum yığınını oluşturmak için, ana düğümün alt düğümlerinden daha büyük olması gereken yığın koşulunu yerine getirmemiz gerekir. Diğer bir deyişle, ağacı max-heap'e dönüştürmek için “yığın haline getirmemiz” gerekir.
Yukarıdaki ağacın yığınlaştırılmasından sonra, aşağıda gösterildiği gibi maksimum yığın elde edeceğiz.
Yukarıda gösterildiği gibi, bir diziden üretilen bu maksimum yığın var.
Ardından, yığın sıralamanın bir örneğini sunuyoruz. Max-heap yapısını gördükten sonra, bir max-heap oluşturmak için ayrıntılı adımları atlayacağız ve her adımda max heap'i doğrudan göstereceğiz.
İllüstrasyon
Aşağıdaki öğe dizisini düşünün. Bu diziyi yığın sıralama tekniğini kullanarak sıralamamız gerekir.
Sıralanacak dizi için aşağıda gösterildiği gibi bir maks-yığın oluşturalım.
Yığın oluşturulduktan sonra, onu aşağıda gösterildiği gibi bir Dizi biçiminde temsil ederiz.
Şimdi 1'i karşılaştırıyoruzstson düğüm ile düğüm (kök) ve sonra bunları değiştirin. Böylece, yukarıda gösterildiği gibi, 17 ve 3'ü değiştiririz, böylece 17 son konumda ve 3 ilk konumda olur.
belirli durumlarla nasıl başa çıkılır
Şimdi düğüm 17'yi öbekten kaldırıyoruz ve aşağıdaki gölgeli kısımda gösterildiği gibi sıralanmış diziye koyuyoruz.
Şimdi yine dizi elemanları için bir yığın oluşturuyoruz. Bu kez, öbekten bir öğe (17) sildiğimiz için yığın boyutu 1 azaltılır.
Kalan öğelerin yığını aşağıda gösterilmiştir.
Bir sonraki adımda aynı adımları tekrarlayacağız.
Kök öğeyi ve yığındaki son öğeyi karşılaştırır ve değiştiririz.
Takas ettikten sonra, ögeden 12 elemanını silip sıralı diziye kaydırıyoruz.
Bir kez daha, aşağıda gösterildiği gibi kalan öğeler için bir maksimum yığın oluşturuyoruz.
Şimdi kök ile son elemanı, yani 9 ve 3'ü değiştiriyoruz. Takas ettikten sonra, eleman 9 öbekten silinir ve sıralı bir diziye yerleştirilir.
Bu noktada, aşağıda gösterildiği gibi yığın içinde yalnızca üç öğemiz var.
6 ve 3'ü değiştirip öbekten 6 öğesini silip sıralanan diziye ekliyoruz.
Şimdi kalan öğelerden bir yığın oluşturuyoruz ve sonra her ikisini de birbiriyle değiştiriyoruz.
4 ve 3'ü değiştirdikten sonra, öbekten 4 numaralı elemanı silip sıralanan diziye ekliyoruz. Şimdi, aşağıda gösterildiği gibi yığında kalan tek bir düğümümüz var .
bunun için mülakat soruları yardım masası
Şimdi sadece bir düğüm kaldı, onu öbekten silip sıralanmış diziye ekliyoruz.
Böylece yukarıda gösterilen, yığın sıralaması sonucunda elde ettiğimiz sıralı dizidir.
Yukarıdaki resimde, diziyi artan sırada sıraladık. Diziyi azalan sırada sıralamak zorunda kalırsak, aynı adımları, ancak min-heap ile izlememiz gerekir.
Yığın sıralaması algoritması, en küçük elemanı seçtiğimiz ve onu sıralı bir diziye yerleştirdiğimiz seçim sıralamasıyla aynıdır. Bununla birlikte, performans söz konusu olduğunda yığın sıralama, seçim sıralamasından daha hızlıdır. Yığın sıralaması, seçim sıralamasının geliştirilmiş bir versiyonu olarak ifade edebiliriz.
Daha sonra Heapsort'u C ++ ve Java dilinde uygulayacağız.
Her iki uygulamadaki en önemli işlev, 'yığın oluşturma' işlevidir. Bu işlev, bir düğüm silindiğinde veya maksimum yığın oluşturulduğunda alt ağacı yeniden düzenlemek için ana yığın sıralaması rutini tarafından çağrılır.
Ağacı doğru bir şekilde yığdığımızda, ancak o zaman doğru elemanları uygun konumlarında elde edebiliriz ve böylece dizi doğru bir şekilde sıralanır.
C ++ Örneği
Aşağıda heapsort uygulaması için C ++ kodu verilmiştir.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Çıktı:
Giriş dizisi
4 17 3 12 9 6
Sıralanmış dizi
3 4 6 9 12 17
Daha sonra yığın sırasını Java dilinde uygulayacağız
Java Örneği
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Çıktı:
Giriş dizisi:
4 17 3 12 9 6
Sıralanmış dizi:
3 4 6 9 12 17
Sonuç
Heapsort, ikili yığın kullanan karşılaştırma tabanlı bir sıralama tekniğidir.
Her iki sıralama tekniği de dizideki en büyük veya en küçük öğeyi tekrar tekrar bulma ve ardından onu sıralanmış diziye yerleştirme gibi benzer mantıkla çalıştığından, seçim sıralamasına göre bir gelişme olarak adlandırılabilir.
Yığın sıralama, diziyi sıralamak için max-heap veya min-heap kullanır. Yığın sıralamadaki ilk adım, dizi verilerinden bir minimum veya maksimum yığın oluşturmak ve ardından kök öğeyi yinelemeli olarak silmek ve yığın içinde yalnızca bir düğüm bulunana kadar yığını yığınlamaktır.
Heapsort verimli bir algoritmadır ve seçimli sıralamadan daha hızlı çalışır. Neredeyse sıralanmış bir diziyi sıralamak veya dizideki en büyük veya en küçük elemanı bulmak için kullanılabilir.
Bununla birlikte, C ++ 'da sıralama teknikleri konusundaki konumuzu tamamladık. Bir sonraki eğitimimizden itibaren, veri yapılarıyla tek tek başlayacağız.
=> Tüm C ++ Eğitim Serisini Burada Arayın.
Önerilen Kaynaklar
- MongoDB Sort () Yöntemi Örneklerle
- Sözdizimi, Seçenekler ve Örneklerle Unix Sıralama Komutu
- Sıralamayı C ++ 'da Örneklerle Birleştirme
- Örneklerle C ++ 'da Kabuk Sıralama
- Örneklerle C ++ 'da Ekleme Sıralaması
- Örneklerle C ++ 'da Seçim Sırala
- Örneklerle C ++ 'da Kabarcık Sıralama
- Örneklerle C ++ 'da Hızlı Sıralama