Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Heap sort
//Rextester.Program.Main is the entry point for your code. Don't change it. //Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5 using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace Rextester { public class Program { public static void Main(string[] args) { /* Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining elementS. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array. */ int [] nums = { 12, 19, 15, 8, 4, 6, 3, 29, 9, 2, 22, 44, 20, 25 }; int n = nums.Length; HeapSort ob = new HeapSort(); Console.WriteLine("Before heap sort, the array is"); ob.Display(nums); ob.sort(nums); Console.WriteLine("Sorted array is"); ob.Display(nums); } } public class HeapSort { public void sort(int[] arr) { int size = arr.Length; // Build max heap (rearrange array) for (int i = size / 2 - 1; i >= 0; i--) { heapify(arr, size, i); } Console.WriteLine("Max heap is"); Display(arr); // One by one extract an element from heap for (int i = size-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); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap public void heapify(int[] arr, int n, int i) { int largest = i; // Initialize largest as root int left = 2*i + 1; // left = 2*i + 1 int right = 2*i + 2; // right = 2*i + 2 // If left child is larger than root if (left < n && arr[left] > arr[largest]) largest = left; // If right child is larger than largest so far if (right < n && arr[right] > arr[largest]) largest = right; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } // Display the array public void Display(int []arr) { int size = arr.Length; for (int indx=0; indx < size; ++indx) Console.Write(arr[indx] + " "); Console.WriteLine(); } } }
run
|
edit
|
history
|
help
0
teste
EX8 For_Loop & While_loop
Contravariance
deqnq the random sentence generator
4
Calculator
Found many section of times intersect (Question version)
Random name switch
Simple Selection Sort
Collatz Conjecture, using Pi