Question

数据结构：关于大根堆的插入问题，如图所示

如图所示题目该咋做啊，能不能参考王道c语言堆的算法给出答案，求教





Answer 1

假设大根堆数组元素为a[1],a[2],...,a[n]，下标从1开始，a[0]可用来临时保存数据

尾部增加的元素一定是叶子节点，这里为a[n+1]，假设其下标为k

则其父节点下标为k/2，大根堆中父节点的值一定要大于等于子节点

所以将a[k]向上调整，不断与其父节点比较，大于父节点就要将父节点向下复制

直到a[k]小于等于其父节点停止，然后将a[n+1]的值插入到当前的a[k]位置即可

参考代码如下：

可见插入过程与图2中的HeapAdjust()方向正好相反，一个向上调整，一个向下调整

源码为：

// 将大根堆中的叶子节点a[k]向上调整

void MaxHeapFixup(int a[], int k) {

    a[0] = a[k]; // a[0]临时保存a[k]的值

    int i; // a[i]为a[k]的父节点

    for (i = k/2; i >= 1; i = i/2) {

        if (a[i] >= a[k]) // 满足父节点不小于其子节点，即找到插入位置

            break;

        else {

            a[k] = a[i]; // 否则将更小的父节点的值向下复制给其子节点

            k = i;

        }

    }

    a[k] = a[0]; // 将叶子节点插入到当前满足大根堆条件的位置

}

// 在大根堆中插入新元素num，默认插入到最后一个位置

void MaxHeapAddNum(int a[], int n, int num) {

    a[n + 1] = num;

    MaxHeapFixup(a, n + 1);

}