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

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?