куча — Minheap, когда значения одинаковы Переполнение стека

Так что я сделал кучи бинарных деревьев. Чтобы проверить это, я создаю группу узлов с 2 разными значениями.

Сказать

struct node
{
int frequency;
int data;
}

Скажем, частота — это то, по чему в первую очередь сортируется куча, но если частота узлов одинакова, она должна затем сортировать по данным узлов.

Когда я делаю кучу узлов, загружаю кучу, выскакиваю и печатаю их, я получаю
(Размер — это количество узлов в дереве, а min — минимальное количество данных, хранящихся в каждом дереве).

Data    Freq    Size    Min
10      1       1       10
84      1       1       84
115     1       1       115
66      1       1       66
114     1       1       114
100     1       1       100
121     2       1       121
111     2       1       111
104     3       1       104
97      3       1       97
101     5       1       101
108     5       1       108
83      6       1       83
32      9       1       32

Если вы не заметили, третья запись неверна, и, следовательно, куча неверна.

Моя ошибка лежит где-то в minheap upheap, удалить или вставить.

Я пытался в течение нескольких дней, мой мозг просто не может справиться с этим, со многими другими забавными вещами, такими как сим-сити. (не совсем, я должен закончить это)

Вот моя куча

class MinHeap
{
public:
int length;
MinHeap(int mVal );

~MinHeap();

int size();  // returns N, the size of the heap
void insert(node* e);
node* remove();
void printheap();

private:

node **a;  // Array of pointers

int MaxSize;
int N;      // current size of heap
int itemMin;
void upheap(int k);
void downheap(int k);

};MinHeap::MinHeap(int mVal)
{
a = new node*[mVal+1]();  //  a**  is an array of pointers;
N=0;  // Sets heap size to zero
a[0]= new node();
length = mVal+1;
MaxSize = mVal;
itemMin = -32767; // Minimum Heap
a[0]->frequency= itemMin ;
}

MinHeap::~MinHeap()
{ delete [] a;}

void MinHeap::upheap(int k)
{
node *e = a[k]  ;
while( e->frequency < a[k/2]->frequency  )
{
a[k] = a[k/2] ;    //move parent down
k = k/2 ;
}
while(e->frequency == a[k/2]->frequency && e->minkey < a[k/2]->minkey)
{
a[k] = a[k/2] ;    //move parent down
k = k/2 ;
}
a[k] = e ;

}void MinHeap::downheap(int k)
{
int j = 2 * k ;
node *e = a[k] ;

while (j <= N) {

if ((j < N) && (a[j+1]->frequency < a[j]->frequency)) j++ ;

if((j<N) && (a[j+1]->frequency == a[j]->frequency) && (a[j+1]->minkey > a[j]->minkey ))j++;

if (( e->frequency <= a[j]->frequency) ) break;

a[j/2] = a[j];  // move child up
j *= 2;         // move child down a level
}
a[j/2] = e;
}void MinHeap::insert(node* e)
{
a[++N] = e ;
upheap(N) ;
}node* MinHeap::remove()
{
node *e = a[1];

a[1] = a[N--]; downheap(1) ;
return &(*e);
}

Я должен упомянуть, что я обязан создавать свои собственные классы STL, и куча предполагает также выбор приоритета с минимальным значением, хранящимся в дереве, если частоты одинаковы, так что именно таков указатель minkey в коде. Просто нужно выяснить, почему это не в правильном порядке.

Моя программа для кодера Хаффмана, вот она:
Мои файлы

Он имеет файл make, который компилируется в системах Ubuntu 64.
Используйте перенаправление для ввода.

Куча сверху исходит от
эхо «Салли продал морские раковины на берегу моря»> вход

./ фуканье < вход