全国自考教材《数据结构导论》

对于P195 “筛选” 程序的注释

void Sift(int heap[], int root, int end) {
    int parent = root - 1;
    int child = 2 * root - 1;

    while (child <= end) {
        if ((child < end) && (heap[child] > heap[child + 1])) {
            child++; // 对比两个孩子节点，取较小
        }
        if (heap[parent] < heap[child]) {
            break;  // “三角”合理，不需要交换，筛选完毕
        } else {
            swap(&heap[parent], &heap[child]);
            parent = child;     // 交换后，孩子变为根，继续向下搜索
            child = 2 * parent; // 根据二叉树的性质，parent * 2 = left child
        }
    }
}