如何修正双数组DEAP的节点配对及初始化逻辑以满足规范？

配对函数（MinPartner/MaxPartner）修正逻辑 #

DEAP的配对节点核心是同层对应位置优先，无对应节点则继承父节点配对，以下是具体实现：

MinPartner函数（最小堆节点找最大堆配对节点） #

int MinPartner(int i, int nA, int nB) {
    if (i == 1) {
        return 1; // 最小堆根节点配对最大堆根节点
    }
    int p = i / 2; // 父节点索引
    int q = MinPartner(p, nA, nB); // 父节点的配对节点
    int j;
    if (i == 2 * p) {
        j = 2 * q; // 当前节点是左孩子，配对节点为父配对节点的左孩子
    } else {
        j = 2 * q + 1; // 当前节点是右孩子，配对节点为父配对节点的右孩子
    }
    // 如果计算出的配对节点超出最大堆元素范围，返回父节点的配对节点
    if (j > nB) {
        return q;
    }
    return j;
}

MaxPartner函数（最大堆节点找最小堆配对节点） #

int MaxPartner(int j, int nA, int nB) {
    if (j == 1) {
        return 1; // 最大堆根节点配对最小堆根节点
    }
    int p = j / 2; // 父节点索引
    int q = MaxPartner(p, nA, nB); // 父节点的配对节点
    int i;
    if (j == 2 * p) {
        i = 2 * q; // 当前节点是左孩子，配对节点为父配对节点的左孩子
    } else {
        i = 2 * q + 1; // 当前节点是右孩子，配对节点为父配对节点的右孩子
    }
    // 如果计算出的配对节点超出最小堆元素范围，返回父节点的配对节点
    if (i > nA) {
        return q;
    }
    return i;
}

Initialize函数修正逻辑 #

Initialize函数需要完成两步：先分别构建最小堆A和最大堆B，再遍历所有节点验证并修复配对关系（确保最小堆节点值 ≤ 对应最大堆配对节点值）。

void Initialize(vector<int>& A, vector<int>& B, int& nA, int& nB) {
    // 1. 构建最小堆A
    for (int i = nA / 2; i >= 1; --i) {
        MinHeapify(A, i, nA);
    }
    // 2. 构建最大堆B
    for (int i = nB / 2; i >= 1; --i) {
        MaxHeapify(B, i, nB);
    }
    // 3. 验证并修复所有配对关系
    for (int i = 1; i <= nA; ++i) {
        int j = MinPartner(i, nA, nB);
        if (A[i] > B[j]) {
            // 交换节点值
            swap(A[i], B[j]);
            // 交换后重新调整对应堆的结构
            MinHeapify(A, i, nA);
            MaxHeapify(B, j, nB);
            // 递归检查父节点的配对关系（交换可能影响上层）
            int p = i / 2;
            while (p >= 1) {
                int q = MinPartner(p, nA, nB);
                if (A[p] > B[q]) {
                    swap(A[p], B[q]);
                    MinHeapify(A, p, nA);
                    MaxHeapify(B, q, nB);
                }
                p /= 2;
            }
        }
    }
}

辅助堆调整函数 #

需要实现标准的最小堆和最大堆调整逻辑：

void MinHeapify(vector<int>& A, int i, int nA) {
    int smallest = i;
    int left = 2 * i;
    int right = 2 * i + 1;
    if (left <= nA && A[left] < A[smallest]) {
        smallest = left;
    }
    if (right <= nA && A[right] < A[smallest]) {
        smallest = right;
    }
    if (smallest != i) {
        swap(A[i], A[smallest]);
        MinHeapify(A, smallest, nA);
    }
}

void MaxHeapify(vector<int>& B, int j, int nB) {
    int largest = j;
    int left = 2 * j;
    int right = 2 * j + 1;
    if (left <= nB && B[left] > B[largest]) {
        largest = left;
    }
    if (right <= nB && B[right] > B[largest]) {
        largest = right;
    }
    if (largest != j) {
        swap(B[j], B[largest]);
        MaxHeapify(B, largest, nB);
    }
}

测试验证说明 #

针对你提到的测试场景（5与45、10与25、8与40配对）：

• 调用MinPartner(对应5的A索引, nA, nB)应返回45在B中的索引
• 调用MinPartner(对应10的A索引, nA, nB)应返回25在B中的索引
• 调用MinPartner(对应8的A索引, nA, nB)应返回40在B中的索引
  配对关系确认后，Initialize函数会自动确保A[i] ≤ B[j]，若初始值不满足则交换并调整堆结构。

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