备注
考虑到 Heap 的特性，很容易想到将其用作排序的用处，为了提高效率需要适当的改进一下，如：in place remove 和 in place move down。
代码
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks; namespace DataStuctureStudy.Sorts
{
class HeapSort<T>
where T : IComparable<T>
{
public static void Test()
{
var items = new int[] { , , , , , , , , , };
HeapSort<int>.Sort(items);
Console.WriteLine(String.Join(",", items));
} public static void Sort(T[] items)
{
for (int i = items.Length / - ; i >= ; i--)
{
MoveDown(items, i, items.Length - );
} for (var i = items.Length - ; i >= ; i--)
{
items[i] = Remove(items, i);
}
} private static T Remove(T[] items, int endIndex)
{
var result = items[];
items[] = items[endIndex]; MoveDown(items, , endIndex - ); return result;
} private static void MoveDown(T[] items, int startIndex, int endIndex)
{
var top = items[startIndex];
var current = startIndex; while (current <= endIndex)
{
var large = ;
var left = * current + ;
var right = left + ; if (left <= endIndex && right <= endIndex)
{
if (items[left].CompareTo(items[right]) >= )
{
large = left;
}
else
{
large = right;
}
}
else if (left <= endIndex)
{
large = left;
}
else
{
break;
} if (items[large].CompareTo(top) <= )
{
break;
} items[current] = items[large];
current = large;
} items[current] = top;
}
}
}
备注
代码的一部分将未排序数组变为堆，然后将对堆执行 in place remove。