Minheap, когда значения одинаковы C++

Question

Так что я сделал кучи бинарных деревьев. Чтобы проверить это, я создаю группу узлов с 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. Используйте перенаправление для ввода.

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

Answer 1

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

В моей функции minheap downheap

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 < N) && (a[j+1]->frequency == a[j]->frequency) && a[j+1]->minkey < a[j]->minkey )     ) j++ ;
   //((a[j+1]->frequency == a[j]->frequency) && (a[j+1]->minkey > a[j]->minkey ))j++;

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


    a[j/2] = a[j];  // move child up
    j *= 2;         // move child down a level
}
a[j/2] = e;
}