michael

堆優(yōu)化的方法：
1、自頂向下
template <class Item>
void fixDown(Item a[],int k,int N)
{
    Item temp;
    while(2*k <= N)
    {
        int j = 2*k;
        if (j<N&&a[j]<a[j+1]) j++;
        if (!(a[k]<a[j])) break;
        //cout<<"fixdown"<<j<<endl;
        exch(a[k],a[j]);
        k = j;
    }
}
根據(jù)堆是個(gè)完全二叉樹，把除了葉節(jié)點(diǎn)以外的從下往上逐步排好。
2、自底向上
template <class Item>
void fixUp(Item a[],int k)
{
    while(k>1 && a[k/2]<a[k])
    {
        exch(a[k],a[k/2]);
        k = k/2;
    }
}

堆排排序的步驟，
1、建立堆。
可以插入的方法或者采取修正堆的方法。
  for(k=N/2;k>=l;k--)
    {
        fixDown(pq,k,N);
    }
2、逐步排序。
   while(N>l)
    {
        exch(pq[l],pq[N]);
        fixDown(pq,l,--N);
    }

總算法：
template <class Item>
void heapsort(Item a[],int l,int r)
{
    int  k = l,N = r-l+1;
    Item *pq = a+l-1;
    for(k=N/2;k>=l;k--)
    {
        fixDown(pq,k,N);
    }
    while(N>l)
    {
        exch(pq[l],pq[N]);
        fixDown(pq,l,--N);
    }

}



堆排序引申的題目。
如果需要找出N個(gè)數(shù)中最大的K個(gè)不同的數(shù)

設(shè)N > K，前K個(gè)數(shù)中的最大K個(gè)數(shù)是一個(gè)退化的情況，所有K個(gè)數(shù)就是最大的K個(gè)數(shù)。如果考慮第K+1個(gè)數(shù)X呢？如果X比最大的K個(gè)數(shù)中的最小的數(shù)Y小，那么最大的K個(gè)數(shù)還是保持不變。如果X比Y大，那么最大的K個(gè)數(shù)應(yīng)該去掉Y，而包含X。如果用一個(gè)數(shù)組來存儲(chǔ)最大的K個(gè)數(shù)，每新加入一個(gè)數(shù)X，就掃描一遍數(shù)組，得到數(shù)組中最小的數(shù)Y。用X替代Y，或者保持原數(shù)組不變。這樣的方法，所耗費(fèi)的時(shí)間為O（N * K）。

進(jìn)一步，可以用容量為K的最小堆來存儲(chǔ)最大的K個(gè)數(shù)。最小堆的堆頂元素就是最大K個(gè)數(shù)中最小的一個(gè)。每次新考慮一個(gè)數(shù)X，如果X比堆頂?shù)脑?em>Y小，則不需要改變原來的堆，因?yàn)檫@個(gè)元素比最大的K個(gè)數(shù)小。如果X比堆頂元素大，那么用X替換堆頂?shù)脑?em>Y。在X替換堆頂元素Y之后，X可能破壞最小堆的結(jié)構(gòu)（每個(gè)結(jié)點(diǎn)都比它的父親結(jié)點(diǎn)大），需要更新堆來維持堆的性質(zhì)。更新過程花費(fèi)的時(shí)間復(fù)雜度為O（log₂K）。

圖2-1

圖2-1是一個(gè)堆，用一個(gè)數(shù)組h[]表示。每個(gè)元素h[i]，它的父親結(jié)點(diǎn)是h[i/2]，兒子結(jié)點(diǎn)是h[2 * i + 1]和h[2 * i + 2]。每新考慮一個(gè)數(shù)X，需要進(jìn)行的更新操作偽代碼如下:

代碼清單2-13

{

    h[0] = X;

    p = 0;

    while(p < K)

    {

        q = 2 * p + 1;

        if(q >= K)

            break;

        if((q < K – 1) && (h[q + 1] < h[q]))

            q = q + 1;

        if(h[q] < h[p])

        {

            t = h[p];

            h[p] = h[q];

            h[q] = t;

            p = q;

        }

        else

            break;

    }

因此，算法只需要掃描所有的數(shù)據(jù)一次，時(shí)間復(fù)雜度為O（N * log₂K）。這實(shí)際上是部分執(zhí)行了堆排序的算法。在空間方面，由于這個(gè)算法只掃描所有的數(shù)據(jù)一次，因此我們只需要存儲(chǔ)一個(gè)容量為K的堆。大多數(shù)情況下，堆可以全部載入內(nèi)存。如果K仍然很大，我們可以嘗試先找最大的K’個(gè)元素，然后找第K’+1個(gè)到第2 * K’個(gè)元素，如此類推（其中容量K’的堆可以完全載入內(nèi)存）。不過這樣，我們需要掃描所有數(shù)據(jù)ceil（K/K’）次。