Implementing Correct Node Partnership in a Doubly-Ended Array-Based Priority Queue (DEAP)

Question

I'm working on implementing a Double-Ended Priority Queue (DEAP) data structure in C++. I'm having trouble with establishing the correct implementation of node partnerships between the min and max heaps. The paragraph below shows properties of a DEAP:

1. The root contains no element.
2. The left subtree is a minimum heap.
3. The right subtree is a maximum heap.
4. If the right subtree is not empty, then let i be any node in the left subtree. Let j be the corresponding node in the right subtree. If such a j does not exist, then j is the node in the right subtree that corresponds to the parent of i. The key in node i is less than or equal to that in j.

The exercise/assignment asks me by using a two-array representation for a DEAP, consisting of arrays A and B, write a function that initializes the arrays A (for minimum heap) and B (for maximum heap) with elements containing their corresponding keys. Assume that nA be the number of elements in A and nB the number of elements in B, so the number of elements n in the DEAP is nA + nB.

Expected Output:

Here's an example of the correct structure I'm trying to achieve:

=========================================================== Expected behavior: Test 2-1: Initialization of two-array deap with 11 elements. Data set: Level 1: 5, 45 Level 2: 10, 8, 25, 40 Level 3: 15, 19, 9, 30, 20

Min heap: root: 5 10(under 5), 8(under 5) 15(under 10), 19(under 10), 15(under 8), 19(under 8)

Max heap: root: 45 25(under 45), 40(under 45) 20(under 25)

=========================================================== Current (Actual) behavior: Test 2-1: Initialization of two-array deap with 11 elements. Data set: Level 1: 5, 45 Level 2: 8, 9, 25, 40 Level 3: 10, 15, 19, 20, 30

Min heap: root: 5 8(under 5), 9(under 5) 10(under 8), 15(under 8), 19(under 9), 20(under 9)

Max heap: root: 45 25(under 45), 40(under 45) 30(under 25)

===========================================================

Minimal Reproducible Example: Below is my attempt at the implementation which populates nodes with their keys in the minimum heap (left subtree) and maximum heap (right subtree).

#include <iostream>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <cmath>

// Element structure template
template <typename KeyType>
struct Element {
    KeyType key;
};

// Constants
namespace constants {
    static const int DefaultHeapSize = 10000;
};

// TwoArrayDeap class template
template <typename KeyType>
class TwoArrayDeap {
private:
    Element<KeyType> *A; // Min heap array
    Element<KeyType> *B; // Max heap array
    int nA;              // Number of elements in min heap
    int nB;              // Number of elements in max heap
    int n;               // Total number of elements
    int MaxSize;         // Maximum allowable size

public:
    // Constructor
    TwoArrayDeap(const int sz = constants::DefaultHeapSize) : MaxSize(sz), n(0) {
        A = new Element<KeyType>[MaxSize/2 + 2];
        B = new Element<KeyType>[MaxSize/2 + 2];
        nA = nB = 0;
    }

    // Destructor
    ~TwoArrayDeap() {
        delete[] A;
        delete[] B;
    }

    void Initialize(const Element<KeyType>* input, int size) {
        if (size > MaxSize) {
            throw std::overflow_error("Input size exceeds maximum deap size");
        }
    
        // Setting the size of the heaps
    
        n = size;
        // Calculate the size of the min heap (A)
        // it should be the largest perfect binary tree that fits the height of the
        // binary tree.
        nA = (1 << static_cast<int>(floor(log2(size + 1)))) - 1;
        nB = n - nA;
    
        // First, copy all elements to arrays A and B
        for (int i = 0; i < nA; i++) {
            A[i + 1] = input[i];
        }
        for (int i = 0; i < nB; i++) {
            B[i + 1] = input[nA + i];
        }
    
        // Step 1: Establish min-max partnerships
        // For each node in A, ensure its partner in B (if it exists) is larger
        for (int i = 1; i <= nA; i++) {
            int partner = MinPartner(i);
            if (partner <= nB && A[i].key > B[partner].key) {
                std::swap(A[i], B[partner]);
            }
        }
    
        // Step 2: Heapify both trees while maintaining partnerships
        // Start from the bottom-most level and work up
        
        // Step 3: Heapify min heap (A)
        for (int i = nA; i >= 1; i--) {
            int current = i;
            Element<KeyType> temp = A[current];
            
            // Bubble up in min heap
            while (current > 1) {
                int parent = current / 2;
                if (A[parent].key <= temp.key) break;
                A[current] = A[parent];
                current = parent;
            }
            A[current] = temp;
            
            // Check and fix partnership after each swap
            int partner = MinPartner(current);
            if (partner <= nB && A[current].key > B[partner].key) {
                std::swap(A[current], B[partner]);
            }
        }
    
        // Step 4: Heapify max heap (B)
        for (int i = nB; i >= 1; i--) {
            int current = i;
            Element<KeyType> temp = B[current];
            
            // Bubble up in max heap
            while (current > 1) {
                int parent = current / 2;
                if (B[parent].key >= temp.key) break;
                B[current] = B[parent];
                current = parent;
            }
            B[current] = temp;
            
            // Check and fix partnership after each swap
            int partner = MaxPartner(current);
            if (partner <= nA && B[current].key < A[partner].key) {
                std::swap(B[current], A[partner]);
            }
        }
    }
    
    // For a node in array A (min heap), returns its partner index in array B (max heap)
    int MaxPartner(int i) {
        if (i <= 0) return 0;
        // Get the level and position in level
        int level = static_cast<int>(floor(log2(i)));
        int posInLevel = i - (1 << level);
        // Partner is in the same relative position in its level
        return (1 << level) + posInLevel;
    }
    
    // For a node in array B (max heap), returns its partner index in array A (min heap)
    int MinPartner(int i) {
        if (i <= 0) return 0;
        // Get the level and position in level
        int level = static_cast<int>(floor(log2(i)));
        int posInLevel = i - (1 << level);
        // Partner is in the same level but earlier position
        return (1 << level) + posInLevel;
    }

    // Print function to validate correctness
    void printTwoArrayDeap() {
        if (n == 0) {
            std::cout << "Empty deap" << std::endl;
            return;
        }

        int totalElements = nA + nB;
        int levels = static_cast<int>(std::ceil(std::log2(totalElements + 1)));

        std::cout << "Data set:" << std::endl;
        int elementsPrinted = 0;
        for (int level = 1; level < levels + 1; level++) {
            std::cout << "Level " << level << ": ";
            int start = 1 << (level - 1);
            int end = 1 << level;
            bool firstInLevel = true;

            for (int i = start; i < end && i <= nA; i++) {
                if (!firstInLevel) std::cout << ", ";
                std::cout << A[i].key;
                firstInLevel = false;
                elementsPrinted++;
            }

            for (int i = start; i < end && i <= nB; i++) {
                if (!firstInLevel) std::cout << ", ";
                std::cout << B[i].key;
                firstInLevel = false;
                elementsPrinted++;
            }

            std::cout << std::endl;
            if (elementsPrinted >= totalElements) break;
        }
        std::cout << std::endl;

        // Print Min heap
        std::cout << "Min heap:" << std::endl;
        if (nA > 0) {
            std::cout << "root: " << A[1].key << std::endl;
            for (int level = 1; level < levels; level++) {
                int start = 1 << level;
                int end = 1 << (level + 1);
                bool firstInLevel = true;
                bool hasElementsInLevel = false;

                for (int i = start; i < end && i <= nA; i++) {
                    if (!firstInLevel) std::cout << ", ";
                    if (!hasElementsInLevel) hasElementsInLevel = true;
                    int parent = i / 2;
                    std::cout << A[i].key << "(under " << A[parent].key << ")";
                    firstInLevel = false;
                }
                if (hasElementsInLevel) std::cout << std::endl;
            }
        }
        std::cout << std::endl;

        // Print Max heap
        std::cout << "Max heap:" << std::endl;
        if (nB > 0) {
            std::cout << "root: " << B[1].key << std::endl;
            for (int level = 1; level < levels; level++) {
                int start = 1 << level;
                int end = 1 << (level + 1);
                bool firstInLevel = true;
                bool hasElementsInLevel = false;

                for (int i = start; i < end && i <= nB; i++) {
                    if (!firstInLevel) std::cout << ", ";
                    if (!hasElementsInLevel) hasElementsInLevel = true;
                    int parent = i / 2;
                    std::cout << B[i].key << "(under " << B[parent].key << ")";
                    firstInLevel = false;
                }
                if (hasElementsInLevel) std::cout << std::endl;
            }
        }
        std::cout << std::endl;
    }
};

int main() {
    std::cout << "TEST 2: Testing Correctness of Two-Array Deap.\n" << std::endl;
    
    TwoArrayDeap<int> twoArrayDeap(20); 
 
    Element<int> twoArrayInput[] = {
        {5}, {8},
        {9}, {10}, {15}, {19},
        {20}, {25}, {30}, {40}, {45}
    };

    std::cout << "Test 2-1: Initialization of two-array deap with 11 elements.\n";
    twoArrayDeap.Initialize(twoArrayInput, 11);
    twoArrayDeap.printTwoArrayDeap();

    return 0;
}

The Problem: I was able to establish the upper and lower bound for nA as a function of nB, which was nB <= nA <= 2nB + 1. However, I have a hard time determining which node of maximum heap B corresponds to the node of minimum heap A. In my MinPartner and MaxPartner functions, I attempted to write the partnership functions using level-based calculations. When initializing the DEAP, I'm noticing that the partnerships between nodes aren't being established correctly. For example, in the image, node 5 should partner with 45, node 10 with 25, and node 8 with 40, but my current implementation isn't achieving this.

How can I modify the Initialize function, the MinPartner and the MaxPartner functions to correctly establish partnerships between nodes at the same level in the min and max heaps?