Bu yazımızda Heapsort Algoritmasını ele alacağız. Yığın sıralama, verilen dizinin öğelerini kullanarak minimum yığın veya maksimum yığın oluşturarak öğeleri işler. Min-heap veya max-heap, kök elemanın dizinin minimum veya maksimum elemanını temsil ettiği dizinin sıralamasını temsil eder.
Yığın sıralaması temelde yinelemeli olarak iki ana işlemi gerçekleştirir:
- Dizinin elemanlarını kullanarak bir H yığını oluşturun.
- 1'de oluşturulan yığının kök öğesini tekrar tekrar silinstfaz.
Yığın sıralaması hakkında daha fazla bilgi sahibi olmadan önce, yığın sıralamasının kısa bir açıklamasına bakalım. Yığın.
Yığın nedir?
Bir yığın tam bir ikili ağaçtır ve ikili ağaç, düğümün en fazla iki çocuğa sahip olabileceği bir ağaçtır. Tam bir ikili ağaç, son düzey (yani yaprak düğüm) dışındaki tüm düzeylerin tamamen doldurulması ve tüm düğümlerin sola dayalı olması gereken bir ikili ağaçtır.
Yığın sıralaması nedir?
Heapsort popüler ve etkili bir sıralama algoritmasıdır. Yığın sıralama kavramı, listenin yığın kısmındaki öğeleri birer birer elemek ve daha sonra bunları listenin sıralanmış kısmına eklemektir.
Heapsort, yerinde sıralama algoritmasıdır.
2. çeyrek ne zaman başlıyor
Şimdi yığın sıralama algoritmasını görelim.
Algoritma
HeapSort(arr) BuildMaxHeap(arr) for i = length(arr) to 2 swap arr[1] with arr[i] heap_size[arr] = heap_size[arr] ? 1 MaxHeapify(arr,1) End
BuildMaxHeap(dizi)
BuildMaxHeap(arr) heap_size(arr) = length(arr) for i = length(arr)/2 to 1 MaxHeapify(arr,i) End
MaxHeapify(arr,i)
MaxHeapify(arr,i) L = left(i) R = right(i) if L ? heap_size[arr] and arr[L] > arr[i] largest = L else largest = i if R ? heap_size[arr] and arr[R] > arr[largest] largest = R if largest != i swap arr[i] with arr[largest] MaxHeapify(arr,largest) End
Heap sort algoritmasının çalışması
Şimdi Yığın Sıralama Algoritmasının çalışmasına bakalım.
Yığın sıralamada temel olarak öğelerin sınıflandırılmasında iki aşama vardır. Yığın sıralama algoritmasını kullanarak bunlar aşağıdaki gibidir:
- İlk adım, dizinin elemanlarını ayarlayarak bir yığın oluşturulmasını içerir.
- Yığın oluşturulduktan sonra, şimdi yığının kök öğesini dizinin sonuna kaydırarak tekrar tekrar kaldırın ve ardından yığın yapısını kalan öğelerle birlikte saklayın.
Şimdi bir örnek kullanarak yığın sıralamanın işleyişini detaylı olarak görelim. Daha net anlamak için sıralanmamış bir diziyi alalım ve onu yığın sıralamasını kullanarak sıralamaya çalışalım. Açıklamayı daha net ve kolay hale getirecektir.
Öncelikle verilen diziden bir yığın oluşturmalı ve onu maksimum yığına dönüştürmeliyiz.
Verilen yığını maksimum yığına dönüştürdükten sonra dizi elemanları -
Daha sonra kök öğeyi silmeliyiz (89) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (on bir). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 89 ile onbir, ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda yine kök öğeyi silmemiz gerekiyor (81) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (54). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 81 ile 54 ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda kök öğeyi silmeliyiz (76) tekrar maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (9). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 76 ile 9 ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda yine kök elemanı silmemiz gerekiyor (54) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (14). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 54 ile 14 ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda yine kök elemanı silmemiz gerekiyor (22) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (on bir). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 22 ile on bir ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda yine kök elemanı silmemiz gerekiyor (14) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (9). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra 14 ile 9 ve yığını maksimum yığına dönüştürdüğümüzde dizinin elemanları -
Bir sonraki adımda yine kök elemanı silmemiz gerekiyor (on bir) maksimum yığından. Bu düğümü silmek için onu son düğümle değiştirmeliyiz; (9). Kök elemanı sildikten sonra, onu maksimum yığına dönüştürmek için tekrar yığınlaştırmamız gerekir.
Dizi öğesini değiştirdikten sonra on bir ile 9, dizinin elemanları -
Artık yığının yalnızca bir öğesi kaldı. Sildikten sonra yığın boş olacaktır.
Sıralama tamamlandıktan sonra dizi elemanları -
Artık dizi tamamen sıralanmıştır.
Yığın sıralama karmaşıklığı
Şimdi Heap sıralamasının zaman karmaşıklığını en iyi durumda, ortalama durumda ve en kötü durumda görelim. Ayrıca Heapsort'un uzay karmaşıklığını da göreceğiz.
1. Zaman Karmaşıklığı
| Dava | Zaman Karmaşıklığı |
|---|---|
| En iyi senaryo | O(n log) |
| Ortalama Durum | O(n log n) |
| En kötü durumda | O(n log n) |
Yığın sıralamanın zaman karmaşıklığı O(n log) her üç durumda da (en iyi durum, ortalama durum ve en kötü durum). N elemanlı tam bir ikili ağacın yüksekliği sakinlik.
java lambda
2. Uzayın Karmaşıklığı
| Uzay Karmaşıklığı | Ç(1) |
| Stabil | Hayır |
- Heap sıralamasının uzay karmaşıklığı O(1)'dir.
Yığın sıralamasının uygulanması
Şimdi farklı programlama dillerinde Heap sort programlarını görelim.
Program: C dilinde yığın sıralamayı uygulayan bir program yazın.
#include /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int arr[], int n) { for (int i = 0; i <n; ++i) { printf('%d', arr[i]); printf(' '); } int main() a[]="{48," 10, 23, 43, 28, 26, 1}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are -
'); printarr(a, n); heapsort(a, printf('
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-20.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C++.</p> <pre> #include using namespace std; /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ void printArr(int a[], int n) { for (int i = 0; i <n; ++i) { cout< <a[i]<<' '; } int main() a[]="{47," 9, 22, 42, 27, 25, 0}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are -
'; printarr(a, n); heapsort(a, cout<<'
after return 0; < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-21.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in C#.</p> <pre> using System; class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int[] a, int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int[] a, int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{46," 8, 21, 41, 26, 24, -1}; int n="a.Length;" console.write('before sorting array elements are -
'); printarr(a, n); heapsort(a, console.write('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-22.webp" alt="Heap Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement heap sort in Java.</p> <pre> class HeapSort { /* function to heapify a subtree. Here 'i' is the index of root node in array a[], and 'n' is the size of heap. */ static void heapify(int a[], int n, int i) { int largest = i; // Initialize largest as root int left = 2 * i + 1; // left child int right = 2 * i + 2; // right child // If left child is larger than root if (left a[largest]) largest = left; // If right child is larger than root if (right a[largest]) largest = right; // If root is not largest if (largest != i) { // swap a[i] with a[largest] int temp = a[i]; a[i] = a[largest]; a[largest] = temp; heapify(a, n, largest); } } /*Function to implement the heap sort*/ static void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i); // One by one extract an element from heap for (int i = n - 1; i >= 0; i--) { /* Move current root element to end*/ // swap a[0] with a[i] int temp = a[0]; a[0] = a[i]; a[i] = temp; heapify(a, i, 0); } } /* function to print the array elements */ static void printArr(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{45," 7, 20, 40, 25, 23, -2}; n="a.length;" system.out.print('before sorting array elements are -
'); printarr(a, n); heapsort(a, system.out.print('
after < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/50/heap-sort-algorithm-23.webp" alt="Heap Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></pre></n;></pre></n;></pre></n;>