演算法 - 堆積排序法 (heap sort )

堆積排序（Heapsort）是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法。堆積樹是一個近似完全二元樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

時間複雜度：O(n logn)
空間複雜度：O(1)

通常堆積樹(heap)是通過一維陣列來實現的。在起始陣列為 0 的情形中：

堆積樹的根節點（即堆積樹的最大值）存放在陣列位置 1 的地方;

　　注意：不使用位置 0，否則左子樹永遠為 0[2]

父節點i的左子節點在位置 (2*i);
父節點i的右子節點在位置 (2*i+1);
子節點i的父節點在位置 floor(i/2);

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

class Heap
{
    public int[] s;
    public int size;

    public Heap(int n, int[] s)
    {
        this.s = new int[n];
        for (int i = 0; i < n; i++)
            this.s[i] = s[i];
    }
}

class HeapSort
{
    public Heap h;

    public HeapSort(int n, int[] s)
    {
        h = new Heap(n, s);
    }

    public void sort(int n)
    {
        makeheap(n, h);
        removeKeys(n, h, h.s);
    }

    void siftdown(Heap tp, int i)
    {
        int parentIndex, lChildIndex, key;
        bool bFound;

        key = tp.s[i];
        parentIndex = i;

        bFound = false;
        
        while (leftNode(parentIndex) <= tp.size && !bFound)
        {
            if (leftNode(parentIndex) < tp.size &&
                tp.s[leftNode(parentIndex)] < tp.s[rightNode(parentIndex)])
                lChildIndex = rightNode(parentIndex);
            else
                lChildIndex = leftNode(parentIndex);

            if (key < tp.s[lChildIndex])
            {
                tp.s[parentIndex] = tp.s[lChildIndex];
                parentIndex = lChildIndex;
            }
            else
                bFound = true;
        }
        tp.s[parentIndex] = key;
    }

    int root(Heap tp)
    {
        int keyout;
        keyout = tp.s[0];
        tp.s[0] = tp.s[tp.size];
        tp.size = tp.size - 1;
        siftdown(tp ,0);
        return keyout;
    }

    void removeKeys(int n, Heap tp, int[] s)
    {
        int i;
        for (i = n - 1; i >= 0; i--)
            s[i] = root(tp);
    }

    void makeheap(int n, Heap tp)
    {
        int i;
        tp.size = (n - 1);
        for (i = (n - 1) / 2; i >= 0; i--)
            siftdown(tp, i);
    }

    int parentNode(int i)
    {
        return Convert.ToInt32(Math.Floor((i - 1) / 2.0));
    }

    int leftNode(int i)
    {
        return (2 * i + 1);
    }

    int rightNode(int i)
    {
        return (2 * i + 2);
    }
}

回首頁