已知(k1，k2，…，kn)是堆，试写一个算法将(k1，k2，…，kn，kn+1)调整为堆。按此思想写一个从率堆开始一个一个添人元素的建堆算法(提示：增加一个kn+1后应从叶子向根的方向调整)。
已知(k1，k2，…，kn)是堆，试写一个算法将(k1，k2，…，kn，kn+1)调整为堆。按此思想写一个从率堆开始一个一个添人元素的建堆算法(提示：增加一个kn+1后应从叶子向根的方向调整)。
【正确答案】：此问题分为两个算法，第一个算法是sift，假设a[1]，a[2]，…，a[k]为堆，增加一个元素a[k+1]，把数组a[1]，a[2]，…，a[k+1]iN,t整N堆。第二个算法是heap，它从1开始调用算法sift将整个数组调整为堆。 void sift(DataType A[]，int k) { int x，i； x=A[k+1]．key； i=k+1； while((i／2>0)＆＆(A[i／2]．key>x)) ／／从下往上插入位置 ｛ A[i]．key=A[i／2]．key； i=i／2； ｝ A[i]．key=x； ｝ void heap(datatype A[]，int n) ／／从1开始调用算法sift，将整个数组调整为堆 { int k： for(k=1；k
Top
×
×