堆排序

static void Main(string[] args)
{
    //产生随机序列
    var rand = new Random();
    List<int> sequence = new List<int>();
    int length = 50;int count = 0;

    //以堆的形状输出数值
    int level = (int)(Math.Log(length) / Math.Log(2))+1;
    for (int i = 0; i < level; i++)
    {
        string pre = new string(‘ ‘, (int)Math.Pow(2, level - i-1)-1);
        string inter = new string(‘ ‘, (int)Math.Pow(2, level-i)-1);
        Console.Write(pre);
        for (int k = 0; k <Math.Pow(2, i)&& count <length; k++,count++)
        {
            sequence.Add(rand.Next() % 10);
            Console.Write("{0}"+inter, sequence[count]);
        }
        Console.WriteLine();
    }
    //使用堆排序
    HeapSort(sequence);

    //以堆的形状输出数值
    Console.WriteLine();
    length = sequence.Count;
    count = 0;
    for (int i = 0; i < level; i++)
    {
        string pre = new string(‘ ‘, (int)Math.Pow(2, level - i - 1) - 1);
        string inter = new string(‘ ‘, (int)Math.Pow(2, level - i) - 1);
        Console.Write(pre);
        for (int k = 0; k < Math.Pow(2, i) && count < length; k++, count++)
        {
            Console.Write("{0}" + inter, sequence[count]);
        }
        Console.WriteLine();
    }
    Console.Read();
}
//堆排序,时间复杂度O(nlg(n))
static void HeapSort(List<int> sq)
{
    //创建最大堆（节点上的值大于叶子节点的值）
    //时间复杂度O(n)
    BuildMaxHeap(sq);
    //最大堆的根节点为最大值,将最大值放在数组最后,同时将未维护的堆大小-1
    //然后重新维护最大堆
    for (int i = sq.Count - 1; i > 0; i--)
    {
        sq[i] = sq[0] ^ sq[i];
        sq[0] = sq[0] ^ sq[i];
        sq[i] = sq[0] ^ sq[i];
        heapSize--;
        MaxHeapify(sq, 0);
    }
}
//当前堆需要维护的大小
static int heapSize = 0;
//构建最大堆
static void BuildMaxHeap(List<int> sq)
{
    heapSize = sq.Count;
    //对每一个非叶子节点进行维护，从最后一个非叶子节点开始
    for (int i = heapSize / 2; i >= 0; i--)
    {
        MaxHeapify(sq, i);
    }
}
//在假定叶子节点为最大堆的情况下,维护最大堆,时间复杂度O(lg(n))
static void MaxHeapify(List<int> sq, int i)
{
    int l = (i + 1) << 1 - 1;
    int r = (i + 1) << 1;
    int large = 0;
    if (l < heapSize && sq[l] > sq[i])
        large = l;
    else
        large = i;
    if (r < heapSize && sq[r] > sq[large])
        large = r;
    if (large != i)
    {
        sq[i] = sq[large] ^ sq[i];
        sq[large] = sq[large] ^ sq[i];
        sq[i] = sq[large] ^ sq[i];
        MaxHeapify(sq, large);
    }
}

//sq为最大堆
static void MaxHeapInsert(List<int> sq, int key)
{
    heapSize++;
    sq.Add(int.MinValue);
    HeapIncreaseKey(sq, heapSize - 1, key);
}

//sq为最大堆
static int HeapMaximum(List<int> sq)
{
    return sq[0];
}

//sq为最大堆
static int HeapExtractMax(List<int> sq)
{
    if (heapSize < 1)
        throw new Exception("heap underflow");
    int max = sq[0];
    sq[0] = sq[heapSize];
    heapSize--;
    //移除最后一个元素
    sq.RemoveAt(heapSize);
    //重新维护最大堆
    MaxHeapify(sq, 0);
    return max;
}

//sq为最大堆
static void HeapIncreaseKey(List<int> sq, int i, int key)
{
    if (key < sq[i])
        throw new Exception("new key must greater than current");
    sq[i] = key;
    // 父节点为(i+1)>>1-1
    //逐一与父节点比较
    while (i > 1 && sq[(i + 1) >> 1 - 1] < sq[i])
    {
        sq[i] = sq[i] ^ sq[(i + 1) >> 1 - 1];
        sq[(i + 1) >> 1 - 1] = sq[i] ^ sq[(i + 1) >> 1 - 1];
        sq[i] = sq[i] ^ sq[(i + 1) >> 1 - 1];
        i = (i + 1) >> 1 - 1;
    }
}