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

Question

我正在尝试为最小堆编写 downHeap() 函数，我将在其中检查根节点的子节点是否小于根节点，如果是，我将交换它们的值。 class 节点已经为我定义，并且有一个 'left' 和 'right' 子指针以及 '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]

如您所见，6 是根节点，而 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);
}

完成左右子树后，检查当前节点的 children.

如果当前节点是叶节点（即没有children）则无事可做

如果当前节点有两个children则取两者之间的最小值

如果当前节点只有一个 child，那就是你要检查的 tmp。

最后检查交换条件。

Answer 2

不确定这是否是自上而下的方法，但这种情况下的时间复杂度会比另一种好。

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

How can I implement downHeap() function in a min-heap?

c++

data-structures

min-heap