Implementierung der korrekten Knotenpartnerschaft in einer doppelt geendeten Array-basierten Priority-Warteschlange (DEA ⇐ C++

[Anonymous]

Ich arbeite an der Implementierung einer DEAP-Datenstruktur (Doppel-Priority Queue) in C ++. Ich habe Probleme, die korrekte Implementierung von Knotenpartnerschaften zwischen Min und Max Heaps zu schaffen. Der folgende Absatz zeigt Eigenschaften eines TEAP: < /p>

[*] Das Stamm enthält kein Element. < /Li>
Der linke Subtree ist ein Minimum heap.
Der rechte Unterbaum ist ein maximaler Heap. im linken Subtree. Sei J der entsprechende Knoten im rechten Subtree. Wenn ein solcher j nicht existiert, ist J der Knoten im rechten Teilbaum, der dem übergeordneten I entspricht. Der Schlüssel im Knoten I ist weniger oder gleich dem in j . Eine Zwei-Array-Darstellung für einen Deap, das aus Arrays A und b besteht, schreiben Haufen) mit Elementen, die ihre entsprechenden Schlüssel enthalten. Angenommen, Na ist die Anzahl der Elemente in a und nb der Anzahl der Elemente in B , sodass die Anzahl der Elemente n im Deap na ist + nb . Um zu erreichen:
< /p>
========================================== =================ieben > Datensatz:
Stufe 1: 5, 45
Stufe 2: 10, 8, 25, 40
Stufe 3: 15, 19, 9, 30, 20 < /p>
/> min Heap:
Wurzel: 5
10 (unter 5), 8 (unter 5)
15 (unter 10), 19 (unter 10), 15 (unter 8 ), 19 (unter 8) < /p>
maximaler Heap:
root: 45
25 (unter 45), 40 (unter 45)
20 (unter 25) < /p>
========================================== =======================
Strom (tatsächliche) Verhalten:
Test 2-1: Initialisierung von zwei Array-Deaps mit 11 Elementen . p>
min Heap:
Wurzel: 5
8 (unter 5), 9 (unter 5)
10 (unter 8), 15 (unter 8), 19 (unter 9), 20 (unter 9) < /p>
max. MAX HEAP:
Wurzel: 45
25 (unter 45), 40 (unter 45)
30 (unter 25) < /p>
==================================== ===========================
Minimal reproduzierbar Beispiel:
Nachfolgend ist mein Versuch bei der Implementierung, die Knoten mit ihren Schlüssel im minimalen Heap (linker Teilbaum) und maximaler Heap (rechter Subtree) bevölkert. < /P>

Code: Select all

#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