|
都是用完全二叉树的静态存储方式，下标从1开始。
No.1 先按照数组的次序填入完全二叉树，再从倒数第一个非叶子节点开始，一个个地看是不是要向下调整，一直下调到不能再调。
void downAdjust(int low,int high){
int i = low;
int j = i*2;
while(j<=n){
if(j+1<=n&&heap[j+1]>heap[j]){
j = j+1;
}
if(heap[i]<heap[j]){
swap(heap[i],heap[j]);
i = j;
j = i*2;
}else break;
}
}
void createHeap(){
for(int i=n/2;i>=1;i--){
downAdjust(i,n);
}
}
No.2 可以先按照数组的次序填入完全二叉树，也可以边读入边调整，从第一个读入的元素开始，看要不要向上调整，一直上调到不能再调。
void newCreateHeap(){
for(int i=1;i<=n;i++){
for(int j=i;j>1&&heap[j]>heap[j/2];j/=2){
swap(heap[j],heap[j/2]);
}
}
}
感悟：书上介绍的是方法1，但是方法2真的简洁多了，虽然时间复杂度可能增大了，因为上调只有一个交换对象，就是自己的父亲，而下调还要考虑是和左孩子还是右孩子。
最要命的是，今天下午做了21年春季PAT甲级，默认第二种建堆方式是对的。想想也是，为啥舍简就繁呢？
|