using System;
using System.Collections.Generic;
public static class Program
{
public static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
public static void DownHeap<T>(T[] a, Int32 left, Int32 right, Comparison<T> comparison)
{
T temp = a[left];
Int32 child;
Int32 parent;
//(right + 1 / 2) は、a[right]の親の次の要素
//a[(right + 1) / 2] は、Heapのはじめから数えて初めて子を持たない要素になる
//つまり parent < (right + 1) / 2 までがヒープ化の対象となる
for (parent = left; parent < (right + 1) / 2; parent = child)
{
Int32 leftChild = parent * 2 + 1;
Int32 rightChild = parent * 2 + 2;
child = (rightChild <= right && comparison(a[rightChild], a[leftChild]) > 0)
? rightChild
: leftChild;
if (comparison(temp, a[child]) >= 0)
{
break;
}
a[parent] = a[child];
}
a[parent] = temp;
}
public static void HeapSort<T>(T[] a, Comparison<T> comparison)
{
//配列のヒープ化
for (Int32 i = (a.Length - 1) / 2; i >= 0; i--)
{
DownHeap(a, i, a.Length - 1, comparison);
}
//ヒープソート
for (Int32 i = a.Length - 1; i > 0; i--)
{
Swap(ref a[0], ref a[i]);
DownHeap(a, 0, i - 1, comparison);
}
}
static void Main()
{
Random random = new Random();
Int32[] arr = new Int32[1000];
for (Int32 i = 0; i < arr.Length; i++)
{
arr[i] = random.Next() % arr.Length;
}
HeapSort(arr, (x, y) => { return x.CompareTo(y); });
Array.ForEach(arr, (n) => Console.WriteLine(n));
}
}