# Heap Sort in C#

by anonymous

• 0
• 0
• 0
82 views
```Orignal Source:http://codingvilla.com/heap-sort-in-csharp-single-article-625.aspx
Before proceeding towards heap sort, we must be familiar with the process “Heap”.

Heap

Heap is a binary tree that is implemented as an array. To perform heap Sort We go through from left to right across each row, however last row may not be completely filled. In heap sort one condition must be satisfied that the parent node must be greater or equal than its child node.

For Example, we have an array

100      90        80        30        60        50        70

Then its heap will be

This procedure works on the basis of the following properties

The index of its parent = i / 2

Index of left child = 2 * i

Index of right child = 2 * i + 1

Heap Sort

Heap sort is the fastest sorting algorithm just as quick sort. It’s complexity is also O(n log n).

How heap Sort works

Heap sort takes an unsorted array and first convert it into heap from the given data. It takes another array to place sorted elements. Then it removes the largest element and places it in sorted array. It then reconstructs the heap according to its properties and remove the next largest element and places it in sorted array. This process continues until all the items transfer from heap into sorted array.

Algorithm for Heap Sort

public static void HeapSort(int[] array, int arr_ubound)
{
int i, j;
intLChild, RChild, Pnode, root, temp;
root = (arr_ubound-1)/2;
for(j = root; j >= 0; j--){
for(i=root;i>=0;i--){
LChild = (2*i)+1;
RChild = (2*i)+2;
if((LChild<= arr_ubound) && (RChild<= arr_ubound)){
if(array[RChild] >= array[LChild])
Pnode = RChild;
else
Pnode = LChild;
}
else{
if(RChild>arr_ubound)
Pnode = LChild;
else
Pnode = RChild;
}

if (array[i] < array[Pnode])
{
temp = array[i];
array[i] = array[Pnode];
array[Pnode] = temp;
}
}
}
temp = array[0];
array[0] = array[arr_ubound];
array[arr_ubound] = temp;
return;
}

First we have selected the root node by the formula then left and right child are selected. If condition that if the value of child is greater than its parent node than it swaps the parent node with child. After creating heap condition it removes the largest element and places in the newly created array for sorted elements.

The complete example of Heap sort is illustrated with the user input in the following sample code.

Code

class Program
{
static void Main(string[] args)
{
int i;
int[] unsortedarray = {100,90,80,30,60,50,70};

Console.WriteLine("\n  Unsorted Array\n\n");
for (i = 0; i <unsortedarray.Length; i++)
Console.WriteLine(" " + unsortedarray[i]);

for (i = unsortedarray.Length; i > 1; i--)
{
Program.HeapSort(unsortedarray, i - 1);
}
Console.WriteLine("\n  Sorted array\n");
for (i = 0; i <unsortedarray.Length; i++)
Console.WriteLine(" " + unsortedarray[i]);
}

public static void HeapSort(int[] array, int arr_ubound)
{
int i, j;
intLChild, RChild, Pnode, root, temp;
root = (arr_ubound-1)/2;
for(j = root; j >= 0; j--){
for(i=root;i>=0;i--){
LChild = (2*i)+1;
RChild = (2*i)+2;
if((LChild<= arr_ubound) && (RChild<= arr_ubound)){
if(array[RChild] >= array[LChild])
Pnode = RChild;
else
Pnode = LChild;
}
else{
if(RChild>arr_ubound)
Pnode = LChild;
else
Pnode = RChild;
}

if (array[i] < array[Pnode])
{
temp = array[i];
array[i] = array[Pnode];
array[Pnode] = temp;
}
}
}
temp = array[0];
array[0] = array[arr_ubound];
array[arr_ubound] = temp;
return;
}
}
```