算法 6.14.txt

来自「《数据结构及应用算法教程》一书的源代码。作者：严蔚敏」· 文本 代码 · 共 12 行

算法 6.14
void HeapAdjust (HeapType &H, int s, int m) {
    // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数依据
    // 关键字的大小对H.r[s]进行调整，使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)
      rc = H.r[s];                  // 暂存根结点的记录
      for ( j=2*s; j<=m; j*=2 ) {   // 沿key较大的孩子结点向下筛选
        if ( j<m && H.r[j].key<H.r[j+1].key )  ++j;     // j为key较大孩子记录的下标
        if ( rc.key >= H.r[j].key )  break;             // 不需要调整
        H.r[s] = H.r[j];  s = j;                        // 把大关键字记录往上调   
      }
      H.r[s] = rc;                                      // 回移筛选下来的记录
} // HeapAdjust