Thread: Heaps!

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    103

    Heaps!

    Hello!
    Today we discussed in class heaps, the professor talked about how to insert data into a heap, which may be useful in sorting them using heapsort.
    I wanted to use rather another approach in building a heap!rather than keeping the heap property each time we insert in element, I want to insert all the elements in a binary tree (I should make sure it is (almost) complete), then heapify the whole tree.
    I know the algorithm to do so, we should go first to the bottomost, rightmost subtree, heapify it by doing some swapping, then go up to the bigger subtree till we reach the whole tree. I don't know how to do that in C.
    So far the code I wrote just makes sure I entered data into a almost complete binary tree. (is it done properly by the way??, I couldn't check for that, even when using the display function!)
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string>
    typedef struct _node{
            int data;
            _node* left;
            _node* right;
            }node;
    void add(int , node** );
    void display(node *);
    void heapify(root**);
    int main(){
               char answer;
               int x;
               printf("The following program sorts a set of numbers.\n");
               printf("It does so by:\n");
               printf("Inserting the data in a binary tree (randomly).\n");
               printf("Then it heapifies the tree.\n");
               do{
                  node* root = NULL;
                  printf("Enter the set of numbers.\n");
                  printf("0 to stop:");
                  while(1){
                                           scanf("%d",&x);
                                           if(x == 0)
                                                break;
                                           add(x,&root);
                                           }
                  display(root);
                  printf("\nRun the program again?\n");
                  printf("1 for yes, any other key to exit:");  
                  scanf(" %c",&answer);          
               }while(answer == '1');
               printf("\n\t\t\tEnd of Program.");
               printf("\n\t\t\t");
               system("PAUSE");
        }
    void add(int x, node** root){
                                node* new_node = (node*) malloc(sizeof(node));
                                if (*root == NULL){
                                   *root = new_node;
                                   (*root)->data = x;
                                   (*root)->left = NULL;
                                   (*root)->right = NULL;
                                   }
                                else{
                                     if((*root)->left != NULL && (*root)->left == NULL)
                                                         add(x,&((*root)->right));
                                     else
                                                         add(x,&(*root)->left);
                                     }
         }
    void display(node* root){
                       if (root == NULL)return;
                       else{
                               printf("%d ",root->data);
                               display(root->left);
                               display(root->right);
                               }
         }
    void heapify(node **root){
                      
         }

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Interesting, and I have some points on how you are making a cat into a dog. But I will let iMalc field this one.

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Lovely, where is Imalc?

  4. #4
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    So no ideas!!?

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So, if the point is to build a heap, and you don't know how to turn a tree into a heap, why not just build a heap?

    I suppose your approach could work, if you never have to change the heap after you build it. I don't remember the running times of each bit so I can't say whether it makes sense to do so or not.

  6. #6
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    There is no point actually, I created a programming exercise for my self (Ironically, I came across some Harvard slides that talked about this approach, but they suggest it as an exercise!), so it is not only me who thinks it's a good programming exercise.
    Let's be more specific, how can I get to the bottomost, rightmost subtree, because in some cases the bottommost subtree can be in the left. That is the problem for me, nothing else!

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Leojeen View Post
    Let's be more specific, how can I get to the bottomost, rightmost subtree, because in some cases the bottommost subtree can be in the left. That is the problem for me, nothing else!
    Keep following ->right links until you get to NULL?

  8. #8
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    That could work in the case where you have a complete binary tree, but if the tree is almost complete in the sun that it goes one level more in the left side, what you suggested would not work.

  9. #9
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    What the hell di I wrote? it is "in the sense" not "in the sun", I just finished reading "Men in the sun"..that explains it!

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    If I needed the rightmost node at the bottom level of the tree, I would store things in an array so that I always knew where the end of the tree is. Of course, that's not entirely practical.
    Since you don't know where it is, the only way to find it is to search for it, or perhaps store a chain of links for level-order traversal. Edit: Actually, that last may not be a bad idea -- you can do that once right before you heapify, I guess, if this whole process doesn't come crashing down first.

  11. #11
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    You mean like, adding an int to the structure where I store the level?

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You could do that, but that wouldn't help you find it later, and you'd have to change everything if you rebalanced your tree. I'm thinking of adding another _node* field, like prev_in_level or something; each node would point to the node before it on the same level or, if it is the first on the level, the last node on the previous level. You wouldn't bother keeping these current as you build your tree; you'd make one pass after it's finished to set them all and keep a pointer to the current "bottom right" node. I am compilerless right this minute, but it seems like a fairly straightforward modification of level-order traversal.

  13. #13
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Rebalanced tree? Nothing will change when you heapify a tree but the values, it is just a matter of swapping nothing else, I mean I should not add any pointer!
    Or so I thought!

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by Leojeen View Post
    Rebalanced tree? Nothing will change when you heapify a tree but the values, it is just a matter of swapping nothing else, I mean I should not add any pointer!
    Or so I thought!
    Yes you're right; I'm not sure, now, what I had in mind (if anything).

  15. #15
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Ok, no problem!! I will just go with adding a level! it may work! who knows!?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Buffers , heaps , stacks ...
    By BlaX in forum Tech Board
    Replies: 9
    Last Post: 02-17-2009, 03:09 PM
  2. Buffers , heaps , stacks ...
    By BlaX in forum C Programming
    Replies: 1
    Last Post: 02-17-2009, 01:11 PM
  3. Using Shared Heaps
    By drwho in forum C Programming
    Replies: 4
    Last Post: 12-30-2005, 04:25 PM
  4. Help with heaps?
    By Nornny in forum C++ Programming
    Replies: 4
    Last Post: 03-22-2004, 12:19 PM
  5. FAQ heaps
    By face_master in forum FAQ Board
    Replies: 2
    Last Post: 10-06-2001, 11:21 AM