数组实现minmax heap（最小最大堆）时Heapify调整功能异常求助

最小最大堆实现问题解答 #

1. 能不能用递归实现该逻辑？ #

可以，最小最大堆的上浮、下沉操作都可以通过递归实现，你当前的问题是实现逻辑存在缺陷，和递归本身无关。

2. 现有代码的核心问题 #

• 交换后未递归校验上层节点：你在当前节点和父/祖父节点完成交换后，被移动到上层的节点可能违反上层的堆序属性，你没有对新位置的节点重新做堆化校验，堆高度超过3层时这个问题就会暴露。
• 堆化执行顺序不符合插入场景要求：插入元素是追加到数组末尾，正确的校验方向是从插入位置自底向上校验，你当前的Heapify是自顶向下的后序遍历，本身就不匹配插入后的平衡需求。
• 父节点存在性判断逻辑有隐患：你通过items[val] != NULL判断父节点是否存在，当堆允许存储0、空值时会出现误判，只需要判断父节点下标是否>=0即可，不需要判断数组对应位置的值。
• getLeftSubTree、getRightSubTree返回NULL作为无效下标是危险操作：如果你的数组下标0是合法位置，和NULL（通常定义为0）会产生歧义，建议返回-1作为无效下标标识。

3. 修正方案 #

你需要把插入后的平衡逻辑改为自底向上的上浮递归，示例实现如下：

// 插入新元素后调用该函数，入参为新元素的下标
void MinMaxHeap::bubbleUp(int ind) {
    if (ind == 0) return; // 根节点无需校验
    int parent_ind = (ind - 1) / 2;
    int level = getlevel(ind);
    if (level % 2 == 0) { // 偶数层：min层，当前节点要小于父节点
        if (items[ind] > items[parent_ind]) {
            swap(ind, parent_ind);
            bubbleUp(parent_ind);
            return;
        }
        // 校验祖父节点
        if (level >= 2) {
            int grandparent_ind = (ind - 3) / 4;
            if (items[ind] < items[grandparent_ind]) {
                swap(ind, grandparent_ind);
                bubbleUp(grandparent_ind);
                return;
            }
        }
    } else { // 奇数层：max层，当前节点要大于父节点
        if (items[ind] < items[parent_ind]) {
            swap(ind, parent_ind);
            bubbleUp(parent_ind);
            return;
        }
        // 校验祖父节点
        if (level >= 2) {
            int grandparent_ind = (ind - 3) / 4;
            if (items[ind] > items[grandparent_ind]) {
                swap(ind, grandparent_ind);
                bubbleUp(grandparent_ind);
                return;
            }
        }
    }
}

// 如果你需要做整体建堆（把无序数组直接转成最小最大堆），Heapify应该改为自底向上的下沉逻辑，每处理一个节点如果发生交换，递归校验子节点
void MinMaxHeap::Heapify(int ind) {
    int level = getlevel(ind);
    int target_ind = ind;
    // 先找当前节点、子节点、孙子节点里的极值（偶数层找最小，奇数层找最大）
    if (level % 2 == 0) {
        // 偶数层找最小值
        int left = 2*ind +1;
        int right = 2*ind +2;
        if (left <= index && items[left] < items[target_ind]) target_ind = left;
        if (right <= index && items[right] < items[target_ind]) target_ind = right;
        int grand_left_left = 2*left +1, grand_left_right = 2*left+2;
        int grand_right_left = 2*right +1, grand_right_right = 2*right+2;
        if (grand_left_left <= index && items[grand_left_left] < items[target_ind]) target_ind = grand_left_left;
        if (grand_left_right <= index && items[grand_left_right] < items[target_ind]) target_ind = grand_left_right;
        if (grand_right_left <= index && items[grand_right_left] < items[target_ind]) target_ind = grand_right_left;
        if (grand_right_right <= index && items[grand_right_right] < items[target_ind]) target_ind = grand_right_right;
    } else {
        // 奇数层找最大值
        int left = 2*ind +1;
        int right = 2*ind +2;
        if (left <= index && items[left] > items[target_ind]) target_ind = left;
        if (right <= index && items[right] > items[target_ind]) target_ind = right;
        int grand_left_left = 2*left +1, grand_left_right = 2*left+2;
        int grand_right_left = 2*right +1, grand_right_right = 2*right+2;
        if (grand_left_left <= index && items[grand_left_left] > items[target_ind]) target_ind = grand_left_left;
        if (grand_left_right <= index && items[grand_left_right] > items[target_ind]) target_ind = grand_left_right;
        if (grand_right_left <= index && items[grand_right_left] > items[target_ind]) target_ind = grand_right_left;
        if (grand_right_right <= index && items[grand_right_right] > items[target_ind]) target_ind = grand_right_right;
    }
    if (target_ind != ind) {
        swap(ind, target_ind);
        // 如果交换的是孙子节点，还要校验target_ind的父节点是否符合要求
        if (getlevel(target_ind) == getlevel(ind) + 2) {
            int parent = (target_ind -1)/2;
            if ((level%2 ==0 && items[target_ind] > items[parent]) || (level%2 ==1 && items[target_ind] < items[parent])) {
                swap(target_ind, parent);
            }
            Heapify(target_ind);
        }
    }
}

按照上面的逻辑修改后，你输入[7,4,2,9,6]逐个插入后就能得到预期的[2,9,4,7,6]结果。

内容的提问来源于stack exchange，提问作者Govt_employee