數據結構示例——堆排序過程

數據結構示例——堆排序過程

完整算法見[例程]，本文用一個例子，演示堆排序的過程。

例：對{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7}進行堆排序的過程。

算法如下:

void HeapSort(RecType R[],int n)
{
    int i;
    RecType temp;
    //（1）循環建立初始堆
    for (i=n/2; i>=1; i--) 
        sift(R,i,n);
    //(2)進行n-1次循環,完成推排序
    for (i=n; i>=2; i--) 
    {
        temp=R[1];       //將第一個元素同當前區間內R[1]對換
        R[1]=R[i];
        R[i]=temp;
        sift(R,1,i-1);   //篩選R[1]結點,得到i-1個結點的堆
    }
}

（1）循環建立初始堆

    for (i=n/2; i>=1; i--) 
        sift(R,i,n);

用給出的序列構造堆的初始狀態如下：

在此基礎上，根據上述代碼，從最後一個分支節點開始調整，目標是得到大根堆。過程如下圖：

這個堆的存儲結構是：

(2)進行n-1次循環,完成推排序

    for (i=n; i>=2; i--) 
    {
        temp=R[1];       //最大值交換到最後
        R[1]=R[i];
        R[i]=temp;
        sift(R,1,i-1);   //前面的無序區調整為堆
    }

過程圖示如下：

請繼續補充畫完。