C++ - Min heap implementation and post order traversal

Question

So I have this small program that creates a min heap and insert values based on user input. If the users says change value 10 to 20, the program should change all occurrences of 10 to 20 and then heapify. When the user gives the print command the program should traverse the tree in postorder and print all the values. So I have written program but its giving me the incorrect output when I print. What am I doing wrong here:

int pArray[500]; 
int i = 0;

//Definition of Node for tree
struct TNode {
    int data; 
    TNode* left;
    TNode* right;
};

void Heapify(TNode* root, TNode* child);

// Function to create a new Node in heap
TNode* GetNewNode(int data) {
    TNode* newNode = new TNode();
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// To insert data in the tree, returns address of root node 
TNode* Insert(TNode* root,int data) {
    if(root == NULL) { // empty tree
        root = GetNewNode(data);
    }
    // if the left child is empty fill that in
    else if(root->left == NULL) {
        root->left = Insert(root->left,data);
    }

    // else, insert in right subtree. 
    else if(root->right == NULL){
        root->right = Insert(root->right,data);
    }

    else {
        root->left = Insert(root->left,data);
    }

    Heapify(root, root->left);
    Heapify(root, root->right);

    return root;
}

void Heapify(TNode* root, TNode* child){
   if(root != NULL && child != NULL){
        if(root->data > child->data){
            int temp = child->data;  
            child->data = root->data;
            root->data = temp;
        }
    } 
}

void Change(TNode* root,int from, int to) {

    if (root == NULL) 
        return;

    else if (root->data == from)
        root->data = to;

    Change(root->left, from, to);
    Change(root->right, from, to);

}

void postOrder(TNode* n){
  if ( n ) {
       postOrder(n->left);
       postOrder(n->right);
       pArray[i] = n->data;
       i++;
    }  
}

If I remember correctly, your heapify algorithm should be recursive. — Jonathan Howard
– Jonathan Howard, Commented Apr 22, 2014 at 23:48
What exactly do you expect to happen, and what happens instead? Also I think you mean "but its giving me the incorrect output when I print". — j_random_hacker
– j_random_hacker, Commented Apr 22, 2014 at 23:53
Why are you implementing a heap as a tree? Heaps are usually implemented as arrays. — user2030052
– user2030052, Commented Apr 23, 2014 at 2:04
@JonathanHoward That's just an implementation detail. Recursion and iteration are equally powerful — Niklas B.
– Niklas B., Commented Apr 23, 2014 at 2:59
@NiklasB. I realize that, however I don't see it as being implemented in iteration either. It's implicitly recursive through the insertion function in this implementation, but if I remember my data structures correctly, the heapify function needs to be called after the insertion–not during. — Jonathan Howard
– Jonathan Howard, Commented Apr 23, 2014 at 3:08

Jim Mischel · Accepted Answer · 2014-04-24 00:41:26Z

What am I doing wrong here?

I'm going to assume that you've verified the heap before you print it. Your tree implementation is a bit confusing, but it looks like it should work. I would suggest, however, that the first thing you do is print the tree before calling your Change method, just to make sure that you have a valid heap.

Assuming that you have a valid heap, your Change method has a problem: it never calls Heapify. You end up changing values in the heap and not rearranging. So of course it's going to be out of order when you output it.

When you change an item's value, you have to move that node (or the node's value) to its proper final position in the tree before you change any other value. You can probably make that work with your current model (by calling Heapify repeatedly until the node is in its proper position). Provided that you're increasing the value. If you're decreasing the value (i.e. changing 20 to 10), then you have a problem because your code has no way to move an item up the tree.

As @noobProgrammer pointed out in his comment, a binary heap typically is implemented as an array rather than as a tree. It's a whole lot easier to implement that way, uses less memory, and is much more efficient. If you're interested in how that's done, you should read my multi-part blog series on heaps and priority queues. The first entry, Priority queues, describes the problem. From there you can follow the links to learn about binary heaps and how they're implemented. The code samples are in C#, but if you read the first two introductory articles and understand the concepts, you'll be able to convert to C++ without trouble.

Collectives™ on Stack Overflow

C++ - Min heap implementation and post order traversal

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related