forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Heap_Sort.cs
71 lines (61 loc) · 1.78 KB
/
Heap_Sort.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using System;
namespace Heap_Sort
{
class Program
{
// Conquer
public static void Heapify(int[] array, int root, int size)
{
int left = 2 * root + 1, largest;
int right = left + 1, temp;
if(left < size && array[left] > array[root])
largest = left;
else
largest = root;
if(right < size && array[right] > array[largest])
largest = right;
if(largest != root)
{
temp = array[root];
array[root] = array[largest];
array[largest] = temp;
Heapify(array, largest, size);
}
}
// Divide array into halves
public static void Build_Heap(int[] array, int size)
{
for(int i = (size - 1) / 2; i >= 0; i--)
Heapify(array, i, size);
}
public static void HeapSort(int[] array, int size)
{
Build_Heap(array, size);
int temp, i;
for(i = size - 1; i > 0; i--)
{
temp = array[0];
array[0] = array[i];
array[i] = temp;
Heapify(array, 0, i);
}
}
// Function ro print array
public static void Print_Array(int[] array, int size)
{
for(int i = 0; i < size; i++)
Console.Write(Convert.ToString(array[i]) + " ");
Console.WriteLine();
}
public static void Main(String[] args)
{
int[] array = {2, 4, 3, 1, 6, 8, 4};
HeapSort(array, 7);
Print_Array(array, 7);
Console.WriteLine();
Console.ReadLine();
}
}
}
// Output
// 1 2 3 4 4 6 8