算法-堆排序-最小堆

发表于 更新于 分类于 ， 阅读次数： 
堆排序算法复杂度为【O(nlgn)】,分最大堆排序和最小堆排序：最大堆定义为所有父节点比左右子节点大。反之亦反，就是最小堆了！
这里我用最小堆来阐述算法。首先需要了解下完全二叉数结构，可以把一个数组看出一个完全二叉树。数组第1个元素看做为根节点，
可定义：
1、 左子树Left(i) = i * 2
2、 右子树Right(i) = i * 2 + 1
3、 父节点Parent(i) = i / 2 

关键的子程序:
a、最小堆操作:堆下降，递归使得父节点小于自己的两个子节点
b、建堆操作（循环调用最小堆操作，获得数组a中n个数据的最小值）

算法思想主要分为2个步骤：
(1)构建堆，使得a[0]（第一个数为最小值）
(2)交换a[0]<=>a[n-1]（a[n-1] 不计入堆中，只有a[0]是不满足最小堆的，其他元素都不变）
(3)a[0]执行最小堆操作，回到(2)步骤直到数组长度为0
*C#的数组是从0开始的，二叉树映射数组是从1开始的。于是所有访问数组的时候都-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static class SortingSupport
{
    public delegate bool CompareLess<T>(T t1, T t2);

    static void Swap<T>(T[] a, int i, int j)
    {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    #region 堆排序
    public static void HeapSort<T>(T[] a, CompareLess<T> cp)
    {
        int heapsize = a.Length;
        BuildMinHeap(a, cp);
        for (int i = a.Length; i > 1; i--)
        {
            Swap(a, 0, i - 1);
            heapsize--;
            MinHeapify(a, 1, heapsize, cp);
        }
    }

    //建堆
    static void BuildMinHeap<T>(T[] a, CompareLess<T> cp)
    {
        int heapSize = a.Length;
        for (int i = a.Length / 2; i > 0; i--)
            MinHeapify(a, i, heapSize, cp);
    }

    //堆下降
    static void MinHeapify<T>(T[] a, int i, int heapSize, CompareLess<T> cp)
    {
        int l = i << 1;
        int r = (i << 1) + 1;
        int min_pos = -1;
        if (l <= heapSize && cp(a[l - 1], a[i - 1]))
            min_pos = l;
        else
            min_pos = i;
        if (r <= heapSize && cp(a[r - 1], a[min_pos - 1]))
            min_pos = r;
        if (min_pos != i)
        {
            Swap(a, min_pos - 1, i - 1);
            MinHeapify(a, min_pos, heapSize, cp);
        }
    }
    #endregion
}