堆排序

static void Main(string[] args){    //产生随机序列    var rand = new Random();    List
     
       sequence = new List
      
       ();    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
       
         sq){    //创建最大堆（节点上的值大于叶子节点的值）    //时间复杂度O(n)    BuildMaxHeap(sq);    //最大堆的根节点为最大值,将最大值放在数组最后,同时将未维护的堆大小-1    //然后重新维护最大堆    for (int i = sq.Count - 1; i > 0; i--)    {        var temp = sq[i];        sq[i] = sq[0];        sq[0] = temp;        heapSize--;        MaxHeapify(sq, 0);    }}//当前堆需要维护的大小static int heapSize = 0;//构建最大堆static void BuildMaxHeap(List
        
          sq){    heapSize = sq.Count;    //对每一个非叶子节点进行维护，从最后一个非叶子节点开始    for (int i = heapSize / 2; i >= 0; i--)    {        MaxHeapify(sq, i);    }}//在假定叶子节点为最大堆的情况下,维护最大堆,时间复杂度O(lg(n))static void MaxHeapify(List
         
           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)    {        var temp = sq[i];        sq[i] = sq[large];        sq[large] = temp;         MaxHeapify(sq, large);    }}
         
        
       
      
     

 

 优先队列与堆排序

优先队列用于维护一维元素构成的结合。其中，最大优先队列支持一下操作：

1. Insert(S, x)，将元素x插入S集合中
2. Maximum(S)，返回S集合中最大关键字
3. ExtractMax(S)，去掉S集合中最大关键字的项
4. IncreaseKey(S, x, k)，将x的值增加为到k，一般假设k>x

明显使用堆可以维护一个优先队列。在一个维护好的最大堆中（非排序后，而是在BuildMaxHeap后），各种操作可以有如下实现。

操作1：在最后插入一个极小值，然后使用操作4，则驾到x

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

操作2：直接返回S[0];

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

操作3：使用堆排序中的HeadSort变体，将第一个最大值取出

//sq为最大堆static int HeapExtractMax(List
     
       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;}
     

操作4：替换后，与父节点递归比较

//sq为最大堆static void HeapIncreaseKey(List
     
       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])    {        var temp = sq[i];        sq[i] = sq[(i + 1) >> 1 - 1];        sq[(i + 1) >> 1 - 1] = temp;    }}