Heap sort is a common sorting algorithm, but useful in case of hierarchical or tree kind of data structures.
public class HeapSort
{
private readonly List<int> _heapList;
private readonly int _heapsize;
public HeapSort(List<int> heapList, int heapsize)
{
this._heapsize = heapsize;
this._heapList = heapList;
}
private void Heapify(int i, int n)
{
var iPosition = _heapList[i];
var iChange = 2 * i;
while (iChange <= n)
{
if (iChange < n && _heapList[iChange] < _heapList[iChange + 1])
{
iChange++;
}
if (iPosition >= _heapList[iChange])
{
break;
}
_heapList[iChange / 2] = _heapList[iChange];
iChange *= 2;
}
_heapList[iChange / 2] = iPosition;
}
public void Sort()
{
for (var i = _heapsize / 2; i >= 0; i--)
{
Heapify(i, _heapsize - 1);
}
for (var i = _heapsize - 2; i >= 0; i--)
{
var iValue = _heapList[i + 1];
_heapList[i + 1] = _heapList[0];
_heapList[0] = iValue;
Heapify(0, i);
}
}
public string PrintList()
{
var myValue = "";
for (int i = 0; i < _heapsize; i++)
{
myValue += _heapList[i] + " ";
}
return myValue;
}
}