C-Sharp-Algorithms/Algorithms/Sorting/HeapSorter.cs at master · aalhour/C-Sharp-Algorithms · GitHub

Name: C-Sharp-Algorithms/Algorithms/Sorting/HeapSorter.cs at master · aalhour/C-Sharp-Algorithms · GitHub
Rating: 4.5 (314 reviews)
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
usingSystem.Collections.Generic;
usingAlgorithms.Common;

namespaceAlgorithms.Sorting
{
publicstaticclassHeapSorter
{
/// <summary>
/// Public API: Default functionality.
/// Sorts in ascending order. Uses Max-Heaps.
/// </summary>
publicstaticvoidHeapSort<T>(thisIList<T>collection,Comparer<T>comparer=null)
{
collection.HeapSortAscending(comparer);
}

/// <summary>
/// Public API: Sorts ascending
/// Uses Max-Heaps
/// </summary>
publicstaticvoidHeapSortAscending<T>(thisIList<T>collection,Comparer<T>comparer=null)
{
// Handle the comparer's default null value
comparer=comparer??Comparer<T>.Default;

intlastIndex=collection.Count-1;
collection.BuildMaxHeap(0,lastIndex,comparer);

while(lastIndex>=0)
{
collection.Swap(0,lastIndex);
lastIndex--;
collection.MaxHeapify(0,lastIndex,comparer);
}
}

/// <summary>
/// Public API: Sorts ascending
/// Uses Min-Heaps
/// </summary>
publicstaticvoidHeapSortDescending<T>(thisIList<T>collection,Comparer<T>comparer=null)
{
// Handle the comparer's default null value
comparer=comparer??Comparer<T>.Default;

intlastIndex=collection.Count-1;
collection.BuildMinHeap(0,lastIndex,comparer);

while(lastIndex>=0)
{
collection.Swap(0,lastIndex);
lastIndex--;
collection.MinHeapify(0,lastIndex,comparer);
}
}


/****************************************************************************/


/// <summary>
/// Private Max-Heap Builder.
/// Builds a max heap from an IList<T> collection.
/// </summary>
privatestaticvoidBuildMaxHeap<T>(thisIList<T>collection,intfirstIndex,intlastIndex,Comparer<T>comparer)
{
intlastNodeWithChildren=lastIndex/2;

for(intnode=lastNodeWithChildren;node>=0;--node)
{
collection.MaxHeapify(node,lastIndex,comparer);
}
}

/// <summary>
/// Private Max-Heapifier. Used in BuildMaxHeap.
/// Heapfies the elements between two indexes (inclusive), maintaining the maximum at the top.
/// </summary>
privatestaticvoidMaxHeapify<T>(thisIList<T>collection,intnodeIndex,intlastIndex,Comparer<T>comparer)
{
// assume left(i) and right(i) are max-heaps
intleft=(nodeIndex*2)+1;
intright=left+1;
intlargest=nodeIndex;

// If collection[left] > collection[nodeIndex]
if(left<=lastIndex&&comparer.Compare(collection[left],collection[nodeIndex])>0)
largest=left;

// If collection[right] > collection[largest]
if(right<=lastIndex&&comparer.Compare(collection[right],collection[largest])>0)
largest=right;

// Swap and heapify
if(largest!=nodeIndex)
{
collection.Swap(nodeIndex,largest);
collection.MaxHeapify(largest,lastIndex,comparer);
}
}

/// <summary>
/// Private Min-Heap Builder.
/// Builds a min heap from an IList<T> collection.
/// </summary>
privatestaticvoidBuildMinHeap<T>(thisIList<T>collection,intfirstIndex,intlastIndex,Comparer<T>comparer)
{
intlastNodeWithChildren=lastIndex/2;

for(intnode=lastNodeWithChildren;node>=0;--node)
{
collection.MinHeapify(node,lastIndex,comparer);
}
}

/// <summary>
/// Private Min-Heapifier. Used in BuildMinHeap.
/// Heapfies the elements between two indexes (inclusive), maintaining the minimum at the top.
/// </summary>
privatestaticvoidMinHeapify<T>(thisIList<T>collection,intnodeIndex,intlastIndex,Comparer<T>comparer)
{
// assume left(i) and right(i) are max-heaps
intleft=(nodeIndex*2)+1;
intright=left+1;
intsmallest=nodeIndex;

// If collection[left] > collection[nodeIndex]
if(left<=lastIndex&&comparer.Compare(collection[left],collection[nodeIndex])<0)
smallest=left;

// If collection[right] > collection[largest]
if(right<=lastIndex&&comparer.Compare(collection[right],collection[smallest])<0)
smallest=right;

// Swap and heapify
if(smallest!=nodeIndex)
{
collection.Swap(nodeIndex,smallest);
collection.MinHeapify(smallest,lastIndex,comparer);
}
}
}
}