Bu eğitimde, yığın sıralama algoritmasının nasıl çalıştığını öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da yığın sıralamanın çalışma örneklerini bulacaksınız.
Yığın Sıralama, bilgisayar programlamada popüler ve verimli bir sıralama algoritmasıdır. Yığın sıralama algoritmasının nasıl yazılacağını öğrenmek, iki tür veri yapısı hakkında bilgi gerektirir - diziler ve ağaçlar.
Sıralamak istediğimiz ilk sayı kümesi bir dizide saklanır, örneğin (10, 3, 76, 34, 23, 32)ve sıraladıktan sonra, sıralı bir dizi elde ederiz(3,10,23,32,34,76)
Yığın sıralama, dizinin öğelerini yığın adı verilen özel bir tür tam ikili ağaç olarak görselleştirerek çalışır.
Ön koşul olarak, tam bir ikili ağaç ve yığın veri yapısı hakkında bilgi sahibi olmanız gerekir.
Dizi Dizinleri ve Ağaç Öğeleri arasındaki ilişki
Tam bir ikili ağacın, herhangi bir düğümün çocuklarını ve ebeveynlerini bulmak için kullanabileceğimiz ilginç bir özelliği vardır.
Dizideki herhangi bir öğenin dizini i ise, dizindeki 2i+1öğe sol alt öğe ve 2i+2dizindeki öğe sağ alt öğe olur. Ayrıca, i indeksindeki herhangi bir elemanın ebeveyni alt sınırı ile verilir (i-1)/2.
Dizi ve yığın indeksleri arasındaki ilişki
Hadi deneyelim,
1'in sol çocuğu (dizin 0) = (2 * 0 + 1) dizindeki öğe = 1 dizindeki öğe = 12 1'in sağ alt öğesi = (2 * 0 + 2) dizindeki öğe = 2 dizindeki öğe = 9 Benzer şekilde, 12'nin sol alt öğesi (dizin 1) = (2 * 1 + 1) dizindeki öğe = 3 dizindeki öğe = 5 12'nin sağ çocuğu = (2 * 1 + 2) dizindeki öğe = 4 dizindeki öğe = 6
Herhangi bir düğümün ebeveynini bulmak için kuralların geçerli olduğunu da doğrulayalım
9'un üst öğesi (konum 2) = (2-1) / 2 = ½ = 0,5 ~ 0 dizin = 1 12'nin üst öğesi (konum 1) = (1-1) / 2 = 0 dizin = 1
Dizi dizinlerinin ağaç konumlarıyla bu eşlemesini anlamak, Yığın Veri Yapısının nasıl çalıştığını ve Yığın Sıralamayı uygulamak için nasıl kullanıldığını anlamak için kritik öneme sahiptir.
Yığın Veri Yapısı Nedir?
Yığın, ağaç tabanlı özel bir veri yapısıdır. Bir ikili ağacın bir yığın veri yapısını izlediği söylenir.
- tam bir ikili ağaç
- Ağaçtaki tüm düğümler, çocuklarından daha büyük olma özelliğini izler, yani en büyük öğe kökte ve hem alt öğelerinde hem de kökten daha küçüktür vb. Böyle bir yığın, maksimum yığın olarak adlandırılır. Bunun yerine, tüm düğümler çocuklarından daha küçükse buna min-heap denir
Aşağıdaki örnek diyagram, Max-Heap ve Min-Heap'i göstermektedir.
Maksimum Yığın ve Min Yığın
Daha fazla bilgi edinmek için lütfen Heap Data Structure'ı ziyaret edin.
Bir ağaç nasıl "yığınlanır"
Tam bir ikili ağaçtan başlayarak, yığının tüm yaprak olmayan öğelerinde heapify adlı bir işlevi çalıştırarak onu bir Max-Heap haline getirebiliriz.
Heapify özyineleme kullandığından, kavraması zor olabilir. Öyleyse önce bir ağacı sadece üç elementle nasıl yığınlayacağınızı düşünelim.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Temel vakaları yığınla
Yukarıdaki örnek iki senaryo göstermektedir - biri kökün en büyük unsur olduğu ve hiçbir şey yapmamıza gerek yok. Ve bir çocukken kökün daha büyük bir öğeye sahip olduğu ve max-heap özelliğini korumak için değiştirmemiz gereken bir diğeri.
Daha önce yinelemeli algoritmalarla çalıştıysanız, muhtemelen bunun temel durum olması gerektiğini belirlemişsinizdir.
Şimdi birden fazla seviyenin olduğu başka bir senaryo düşünelim.
Alt ağaçları zaten maksimum yığın olduğunda kök öğesi nasıl yığınlanır
En üstteki öğe bir maksimum yığın değildir, ancak tüm alt ağaçlar maksimum yığınlardır.
Tüm ağaç için maksimum yığın özelliğini korumak için, doğru konumuna ulaşana kadar 2'yi aşağı doğru itmeye devam etmeliyiz.
Alt ağaçları maksimum yığınlar olduğunda kök öğesi nasıl yığınlanır
Bu nedenle, her iki alt ağacın da en fazla yığın olduğu bir ağaçta maks-yığın özelliğini korumak için, alt öğesinden daha büyük olana veya bir yaprak düğümü haline gelene kadar kök öğesinde yığınlamayı tekrar tekrar çalıştırmamız gerekir.
Bu koşulların ikisini birden bir yığın işlevinde birleştirebiliriz:
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Bu işlev hem temel durum hem de her boyuttaki ağaç için çalışır. Böylelikle, alt ağaçlar maksimum yığın olduğu sürece herhangi bir ağaç boyutu için maksimum yığın durumunu korumak için kök öğeyi doğru konuma taşıyabiliriz.
Maksimum yığın oluşturun
Herhangi bir ağaçtan bir maksimum yığın oluşturmak için, böylece her bir alt ağacı aşağıdan yukarıya yığınlamaya başlayabiliriz ve fonksiyon kök eleman dahil tüm öğelere uygulandıktan sonra bir maksimum yığın elde edebiliriz.
Tam bir ağaç olması durumunda, yaprak olmayan bir düğümün ilk dizini ile verilir n/2 - 1. Bundan sonraki diğer tüm düğümler yaprak düğümlerdir ve bu nedenle yığınlanmalarına gerek yoktur.
Böylece, maksimum yığın oluşturabiliriz.
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Dizi oluşturun ve hesaplayın 
Yığın sıralama 
için maksimum yığın 
oluşturma adımları Yığın sıralama için maksimum yığın oluşturma adımları Yığın sıralama için maksimum yığın oluşturma adımları
Yukarıdaki diyagramda gösterildiği gibi, en alçak en küçük ağaçları yığınlayarak başlıyoruz ve kök öğeye ulaşana kadar kademeli olarak yukarı hareket ediyoruz.
Buraya kadar her şeyi anladıysanız, tebrikler, Yığın sıralamasında ustalaşma yolundasınız.
Yığın Sıralama Nasıl Çalışır?
- Ağaç Max-Heap özelliğini karşıladığından, en büyük öğe kök düğümde saklanır.
- Takas: Kök öğeyi kaldırın ve dizinin sonuna koyun (n. Konum) Ağacın son öğesini (yığın) boş yere koyun.
- Kaldır: Yığın boyutunu 1 küçültün.
- Yığınla: Kökte en yüksek öğeye sahip olmak için kök öğeyi yeniden yığınlayın.
- Listedeki tüm öğeler sıralanana kadar işlem tekrarlanır.
Takas Et, Kaldır ve Yığınla
Aşağıdaki kod işlemi gösterir.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children 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 root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Yığın Sıralama Karmaşıklığı
Yığın Sıralama, O(nlog n)tüm durumlar için zaman karmaşıklığına sahiptir (en iyi durum, ortalama durum ve en kötü durum).
Nedenini anlayalım. N eleman içeren tam bir ikili ağacın yüksekliğilog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Yığın Sıralama, O(n log n)en kötü durumda bile zaman karmaşıklığına sahip olsa da, daha fazla uygulamaya sahip değildir (Hızlı Sıralama, Birleştirme Sıralama gibi diğer sıralama algoritmalarına kıyasla). Ancak, kalan öğeleri sıralı düzende tutmanın ek yükü olmadan öğe listesinden en küçük (veya en büyük) olanı çıkarmak istiyorsak, temel veri yapısı olan yığın verimli bir şekilde kullanılabilir. Örneğin Öncelik Sıraları için.
