堆優化的方法：
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;
    }
}
根據堆是個完全二叉樹，把除了葉節點以外的從下往上逐步排好。
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個數中最大的K個不同的數

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

進一步，可以用容量為K的最小堆來存儲最大的K個數。最小堆的堆頂元素就是最大K個數中最小的一個。每次新考慮一個數X，如果X比堆頂的元素Y小，則不需要改變原來的堆，因為這個元素比最大的K個數小。如果X比堆頂元素大，那么用X替換堆頂的元素Y。在X替換堆頂元素Y之后，X可能破壞最小堆的結構（每個結點都比它的父親結點大），需要更新堆來維持堆的性質。更新過程花費的時間復雜度為O（log₂K）。

圖2-1

圖2-1是一個堆，用一個數組h[]表示。每個元素h[i]，它的父親結點是h[i/2]，兒子結點是h[2 * i + 1]和h[2 * i + 2]。每新考慮一個數X，需要進行的更新操作偽代碼如下:

代碼清單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;

    }

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