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