c++ - 如何在最小堆中实现downHeap()函数？

Question

我正在尝试为min-heap编写downHeap()函数，在该函数中，我将检查根节点的子节点是否小于rootnode，如果是，我将交换其值。 Node类已经为我定义，并且具有“left”和“right”子ptrs以及“value”。下面是我到目前为止的代码:

void downHeap(Node *n) {

    if (!n) {return;}

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

    if (n->left && 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]

如您所见，rootNode是6，而root应该是4。然后4和5应该再次交换位置。我的函数现在似乎只交换一次rootNode，并且一直关闭，但从头开始没有进行检查。我试图在if条件的末尾再次添加 downHeap(n)，但是如果我这样做，则没有任何输出。请帮忙!

Answer 1

您首先需要深入了解，然后检查要交换的条件。
我会做这样的事情:

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 && root->right == NULL) return;

    if(root->left != NULL && 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);
}

完成左右子树的检查后，检查当前节点的子代。
如果当前节点是叶子(即没有子节点)，则无需执行任何操作。
如果当前节点有两个子节点，则在两个子节点之间获得最小值。
如果当前节点只有一个 child ，那就是您要检查的 tmp。
最后检查交换条件。