Удаление / удаление узлов из Minheap дерева Хаффмана

Question

У меня проблемы с корректным сованием с дерева Хаффмана. Сейчас я создаю дерево Хаффмана на основе мини-кучи и хочу сделать следующее:

Если мы предположим, что A и B являются двумя разными поддеревьями, я бы сказал, что A будет выталкиваться первым, если частота A меньше частоты B. Если они имеют одинаковую частоту, я бы нашел наименьший символ в значении ASCII в любом из листовых узлов А. Тогда я бы посмотрел, меньше ли этот самый маленький листовой узел символа в A, чем в любом из листовых узлов B. Если так, я бы соскочил с А до Б. Если нет, я бы соскочил с Б. <- вот с чем у меня проблемы

Например:

Давайте предположим, что я ввел:

eeffgghh\n (every letter except for \n's frequency which is 1 is 2)

в мое дерево Хаффмана. Тогда мое дерево будет выглядеть так:

        9      
       / \
    5        4    
   / \      / \
  3  h      g  f
 /\
e  \n

Ниже моя попытка выскочить из моей мини-кучи Хаффмана. У меня возникли проблемы с частью сравнения, если частоты двух букв одинаковы. Если бы кто-нибудь мог помочь, это было бы здорово. Спасибо!

void minHeap::heapDown(int index)
{
  HuffmanNode *t = new HuffmanNode();
  if(arr[index]->getFreq() == arr[left]->getFreq() || arr[index]->getFreq() == arr[right]->getFreq()) //arr is an array of HeapNodes
    {
      if(arr[left]->getLetter() < arr[right]->getLetter())
      {
        t = arr[index]; //equals operator is overloaded for swapping
        arr[index] = arr[left];
        arr[left] = t;
        heapDown(left);
      }
      else
      {
        t = arr[index];
        arr[index] = arr[right];
        arr[right] = t;
        heapDown(right);
      }
    }
    if(arr[index]->getFreq() > arr[left]->getFreq() || arr[index]->getFreq() > arr[right]->getFreq())
    {
      if(arr[left]->getFreq() < arr[right]->getFreq())
      {
        t = arr[index];
        arr[index] = arr[left];
        arr[left] = t;
        heapDown(left);
      }
      else
      {
        t = arr[index];
        arr[index] = arr[right];
        arr[right]  = t;
        heapDown(right);
      }//else
    }//if
}

Answer 1

Стандартная библиотека C++ содержит алгоритмы кучи. Если вам не разрешено использовать его, вы можете найти его проще.

Стандартная библиотека C++ также содержит swap(a, b), который был бы намного более читабельным, чем swap, который вы делаете. Однако обмен в heapDown неэффективен: вам нужно удерживать элемент, который будет помещен во временный объект, затем просеять дочерние элементы, пока не найдете место для размещения элемента, и затем поместить его туда.

Ваш код также был бы намного более читабельным, если бы вы реализовали operator<для HuffmanNode. В любом случае вы делаете еще одно сравнение, чем необходимо; то, что вы действительно хотите сделать, это (опуская много деталей):

heapDown(int index, Node* value) {
  int left = 2 * min - 1;  // (where do you do this in your code???)
  // It's not this simple because you have to check if left and right both exist
  min = *array[left] < *array[left + 1] ? left : left + 1;  // 1 comparison
  if (array[min] < to_place) {
    array[index] = array[min];
    heapDown(min, value);
  } else {
     array[index] = value;
  }

Ваше первое сравнение (третья строка) совершенно неверно. a == b || a == c не означает, что b==c, и даже не дает вам никакой информации о том, какой из b и c меньше. Выполнение только второго сравнения на b и c обычно дает вам неправильный ответ.

Наконец, вы делаете new без необходимости на каждом вызове, но никогда не делать delete, Так что у вас медленно, но неумолимо течет память.