Блог

Я пытаюсь записать функцию downHeap () для минимальной кучи, где я проверю, является ли дочерний элемент корневого узла меньше корневого узла, и если да, я поменяю их значения местами. Узел класса уже определен для меня и имеет ‘левый’ и ‘правый’ дочерние ptr-файлы, а также ‘значение’. Ниже приведен мой код на данный момент:

 void downHeap(Node *n) {

    if (!n) {return;}

    if (!n->left amp;amp; !n->right) {return;}

    if (n->left amp;amp; n->right){
        if (n->left->value < n->right->value){
          if (n->left->value < n->value){
            std::swap(n->value, n->left->value);
            downHeap(n->left);
          }
      else if (n->right->value < n->left->value){
          if (n->right->value < n->value){
            std::swap(n->value, n->right->value);
            downHeap(n->right);
          }
        }
      }
    }
  

Это мой основной способ протестировать функцию:

 int main() {
  Node *n = new Node(7);
  n->left = new Node(6);
  n->right = new Node(9);
  n->left->left = new Node(4);
  n->left->right = new Node(5);
  downHeap(n);
  printTreeVertical(n);

  delete n;
  n = nullptr;
  return 0;
}
  

И мое результирующее дерево:

 ##6 (X) Greater than child value 4
#|
#|_ 4.  // 4 is left child and 9 is right child of 6 in this tree.
#|..|
#|..|_ 7 //7 and 5 are children of 4.
#|..|..|
#|..|..|_ [null]
#|..|..|
#|..|..|_ [null]
#|..|
#|..|_ 5
#|.....|
#|.....|_ [null]
#|.....|
#|.....|_ [null]
#|
#|_ 9
#...|
#...|_ [null]
#...|
#...|_ [null]
  

Как вы можете видеть, 6 — это корневой узел, тогда как должно быть 4. И затем 4 и 5 должны снова поменяться местами. Моя функция прямо сейчас, похоже, меняет корневой узел только один раз и продолжает снижаться, но не перепроверяет с самого начала. Я попытался добавить downHeap(n) еще раз в конце условий if, но если я это сделаю, ничего не выйдет. Пожалуйста, помогите!

Сначала вам нужно углубиться, а затем проверить условие для замены. Я бы сделал что-то вроде этого:

 void mySwap(Node* a, Node* b)
{
    int tmp = a->val;
    a->val = b->val;
    b->val = tmp;
}

void downHeap(Node* root)
{
    node_t* tmp = NULL;

    if(root == NULL) return;

    downHeap(root->left);
    downHeap(root->right);

    if(root->left == NULL amp;amp; root->right == NULL) return;

    if(root->left != NULL amp;amp; root->right != NULL)
    {
        if(root->left->val < root->right->val)
            tmp = root->left;
        else 
            tmp = root->right;
    }
    else
    {
        if(root->left != NULL)
            tmp = root->left;
        if(root->right != NULL)
            tmp = root->right;
    }

    if(tmp->val < root->val)
        mySwap(root, tmp);
}
  

Когда вы закончите с левым и правым поддеревьями, проверьте, нет ли дочерних элементов текущего узла.

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

Если текущий узел имеет двух дочерних узлов, то получите минимум между ними.

Если у текущего узла есть только один дочерний узел, это ваш tmp для проверки.

В конце проверьте условие подкачки.

Не уверен, что это будет подход сверху вниз, но временная сложность в этом случае была бы лучше, чем в другом.