void exch(int& a, int &b) { int tmp = a; a = b; b = tmp; } void fixup(int a[], int k) { while(k>1 && a[k/2]<a[k]) { exch(a[k/2], a[k]); k/=2; } } void fixdown(int a[], int k, int N) { while(2*k <= N) { int j=k*2; if(k<N && a[j]<a[j+1]) j++; if(!(a[k]<a[j])) break; exch(a[k], a[j]); k = j; } }
当一些节点的优先级提高了,(新节点加入到堆底部), 需要向上遍历堆来重构堆。(fixup)
当一些节点的优先级下降了,(新节点替换了根节点),需要向下遍历堆来重构堆。(fixdown)