Реализация правильного партнерства узлов в двойной стойке приоритетной очереди на основе массива (DEAP) ⇐ C++

[Anonymous]

Я работаю над реализацией структуры данных с двойной приоритетной очередью (DEAP) в C ++. У меня проблемы с установлением правильной реализации партнерских отношений узлов между Min и Max Heaps. Приведенный ниже параграф показывает свойства Deap: < /p>

• Корень не содержит элемента. Heap.
• Правая поддерево представляет собой максимальную кучу. в левой поддерево. Пусть j будет соответствующим узлом в правом поддерете. Если такого j не существует, то j является узлом в правом поддере, который соответствует родителю i . Ключ в узле I меньше или равен ключке в j .

Упражнение/назначение спросит меня, используя Представление с двумя агрегатами для DEAP, состоящее из массивов A и b , напишите функцию, которая инициализирует массивы A (для минимальной кучи) и B (для максимума куча) с элементами, содержащими их соответствующие ключи. Предположим, что na - количество элементов в и nb Количество элементов в b , поэтому количество элементов n в Deap - NA + nb .
ожидаемый выход:
Вот пример правильной структуры, которую я пытаюсь Для достижения:
< /p>
================================================================== ================ = > Набор данных:
Уровень 1: 5, 45
Уровень 2: 10, 8, 25, 40
Уровень 3: 15, 19, 9, 30, 20 < /p>
Мин. Куча:
root: 5
10 (до 5), 8 (до 5)
15 (до 10), 19 (до 10), 15 (до 8 ), 19 (до 8) < /p>
max heap:
root: 45
25 (до 45), 40 (до 45)
20 (под 25) < /p>
================================================================== ================= = .
Набор данных:
Уровень 1: 5, 45
Уровень 2: 8, 9, 25, 40
Уровень 3: 10, 15, 19, 20, 30 < / p>
min Heap:
root: 5
8 (до 5), 9 (до 5)
10 (до 8), 15 (до 8), 19 (до 9), 20 (до 9) < /p>
max heap:
root: 45
25 (до 45), 40 (до 45)
30 (до 25) < /p>
=============================================================== =================== = /> Ниже приведена моя попытка реализации, которая заполняет узлы своими ключами в минимальной куче (левой поддерево) и максимальной куче (правая поддерево). < /P>

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 

// Element structure template
template 
struct Element {
KeyType key;
};

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

// TwoArrayDeap class template
template 
class TwoArrayDeap {
private:
Element *A; // Min heap array
Element *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[MaxSize/2 + 2];
B = new Element[MaxSize/2 + 2];
nA = nB = 0;
}

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

void Initialize(const Element* 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  1) {
int parent = current / 2;
if (A[parent].key = 1; i--) {
int current = i;
Element 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 

Подробнее здесь: [url]https://stackoverflow.com/questions/79441283/implementing-correct-node-partnership-in-a-doubly-ended-array-based-priority-que[/url]