堆优化的方法：
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’）次。