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

Question

I'm trying to write downHeap() function for a min-heap where I will check to see if a root node's child is less than the rootnode and if so, I will swap their values. The class Node is already defined for me and has a 'left' and 'right' child ptrs as well as 'value'. Below is my code so far:

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);
          }
        }
      }
    }

This is my main to test the function:

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;
}

And my resulting tree:

##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]

As you can see 6 is the rootNode whereas 4 should be. And then 4 and 5 should swap places again. My function right now seems to swap the rootNode only once and keeps going down but does not recheck from the start. I've tried to add downHeap(n) again at the end of the if conditions but if I do that, nothing outputs. Please help!

Answer 1

You first need to go down in depth, then check for the condition to swap. I would do something like this:

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);
}

When you are done with left and right subtrees check for the current node's children.

If the current node is a leaf (i.e. no children) there's nothing to do.

If the current node has two children then get the minimum between the two.

If the current node has only one child, that is your tmp to check against.

At the end check for the swap condition.