Thread: heap arrainging question..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    heap arranging question..

    a heap is a binary tree in which the root is bigger then both its sons.

    i need to write a function which gets a node and a root of the heap where this node is located in the bottom level.

    i need to switch this nodes value with the roots and delete it
    and then rearrange the tree so ill get a heap again.

    the diagram is in this link

    i tried to implement it here
    but i dont know why i get all these errors??
    Code:
    #define false 0
    #define true 1
    
    
    typedef struct TreeNode
    {
    	struct TreeNode *father;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	double val;
    }TreeNode;
    
    TreeNode * maxson(TreeNode * root);
    void swap(TreeNode * root,TreeNode * node);
    double deletemax(treenode **heap,treenode *leaf);
    TreeNode * maxson(TreeNode * root);
    void arrange(TreeNode ** root);
    int main()
    {
       TreeNode* root;
       double t;
       root=(TreeNode*)malloc(sizeof(TreeNode));
       root->val=9;
       root->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->right->val=4;
       root->right->left=NULL;
       root->right->right=NULL;
       root->right->father=root;
    
       root->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->val=8;
       root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->left->val=7;
       root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->right->val=6;
       root->left->right->father=root->left;
       root->left->left->father=root->left;
    
       root->left->right->right=NULL;
       root->left->right->left=NULL;
    
       root->left->left->right=NULL;
       root->left->left->left=NULL;
    
       t=deletemax(&heap,root->left->right);
       return 0;
    }
    
    double deletemax(treenode **heap,treenode *leaf)//i have to use this signature
    {
    	double temp=*heap->val;
      swap(*heep,leaf);
      free(leaf);
       arrange(heap);
     return temp;
      
    }
    void swap(TreeNode * root,TreeNode * node)
    {
    	double temp;
        temp=root->val;
        root->val=node->val;
    	root->val=temp;
    
    }
    
    TreeNode * maxson(TreeNode * root)
    {
      if (root->left>root->right)
      {
            return root->left;
      }
      else
      {
            return root->right;
      }
    }
    
    void arrange(TreeNode ** root)
    {
       treenode* temp;
       temp=maxson(*root); 
       if ((*root->left==NULL)&&(*root->right==NULL))
       {
           return;
       }
       if (temp->val>*root->val)
       {
          swap(*root,node);
          
       }
       arrange(&(root->left));
       arrange(&(root->right));
    }
    Last edited by transgalactic2; 03-25-2009 at 03:42 AM.

  2. #2
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i fixed all the sintax errors but i get
    an error of accssesing null memory
    why?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define false 0
    #define true 1
    
    
    typedef struct TreeNode
    {
    	struct TreeNode *father;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	double val;
    }TreeNode;
    
    TreeNode * maxson(TreeNode * root);
    void swap(TreeNode * root,TreeNode * node);
    double deletemax(TreeNode **heap,TreeNode *leaf);
    TreeNode * maxson(TreeNode * root);
    void arrange(TreeNode ** root);
    int main()
    {
       TreeNode* root;
       double t;
       root=(TreeNode*)malloc(sizeof(TreeNode));
       root->val=9;
       root->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->right->val=4;
       root->right->left=NULL;
       root->right->right=NULL;
       root->right->father=root;
    
       root->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->val=8;
       root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->left->val=7;
       root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->right->val=6;
       root->left->right->father=root->left;
       root->left->left->father=root->left;
    
       root->left->right->right=NULL;
       root->left->right->left=NULL;
    
       root->left->left->right=NULL;
       root->left->left->left=NULL;
    
       t=deletemax(&root,root->left->right);
       return 0;
    }
    
    double deletemax(TreeNode **heap,TreeNode *leaf)//i have to use this signature
    {
    	double temp=(*heap)->val;
      swap(*heap,leaf);
      free(leaf);
       arrange(heap);
     return temp;
      
    }
    void swap(TreeNode * root,TreeNode * node)
    {
    	double temp;
        temp=root->val;
        root->val=node->val;
    	root->val=temp;
    
    }
    
    TreeNode * maxson(TreeNode * root)
    {
      if (root->left>root->right)
      {
            return root->left;
      }
      else
      {
            return root->right;
      }
    }
    
    void arrange(TreeNode ** root)
    {
       TreeNode* temp;
       temp=maxson(*root); 
       if (((*root)->left==NULL)&&((*root)->right==NULL))
       {
           return;
       }
       if (temp->val>(*root)->val)
       {
          swap(*root,temp);
          
       }
       arrange(&((*root)->left));
       arrange(&((*root)->right));
    }

  3. #3
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    run your code in the debugger.

    Also think - what will happen to the father after you free the son
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    acctually i am not using the father at all so i dont care
    i fixed the code a little more

    but my main problem is marked in a comment "here is the problem" in the code.
    the problem is when i free the memory
    of pointer "leaf"
    then when i want it to point to NULL
    it doesnt do it.
    the debuger shows some random memory instead of NULL
    ??
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define false 0
    #define true 1
    
    
    typedef struct TreeNode
    {
    	struct TreeNode *father;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	double val;
    }TreeNode;
    
    TreeNode * maxson(TreeNode * root);
    void swap(TreeNode * root,TreeNode * node);
    double deletemax(TreeNode **heap,TreeNode *leaf);
    TreeNode * maxson(TreeNode * root);
    void arrange(TreeNode ** root);
    int main()
    {
       TreeNode* root;
       double t;
       root=(TreeNode*)malloc(sizeof(TreeNode));
       root->val=9;
       root->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->right->val=4;
       root->right->left=NULL;
       root->right->right=NULL;
       root->right->father=root;
    
       root->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->val=8;
       root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->left->val=7;
       root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->right->val=6;
       root->left->right->father=root->left;
       root->left->left->father=root->left;
    
       root->left->right->right=NULL;
       root->left->right->left=NULL;
    
       root->left->left->right=NULL;
       root->left->left->left=NULL;
    
       t=deletemax(&root,root->left->right);
       return 0;
    }
    
    double deletemax(TreeNode **heap,TreeNode *leaf)//i have to use this signature
    {
    	double temp=(*heap)->val;
      swap(*heap,leaf);
      
      free(leaf);
      leaf=NULL;                                      //here is the problem
       arrange(heap);
     return temp;
      
    }
    void swap(TreeNode * root,TreeNode * node)
    {
    	double temp;
        temp=root->val;
        root->val=node->val;
    	node->val=temp;
    
    }
    
    TreeNode * maxson(TreeNode * root)
    {
    	if (root->left==NULL)
    	{
          return root->right;
    	}
    	
    	if (root->right==NULL)
    	{
          return root->left;
    	}
     
      if (root->left->val>root->right->val)
      {
            return root->left;
      }
      else
      {
            return root->right;
      }
    }
    
    void arrange(TreeNode ** root)
    {
       TreeNode* temp;
       temp=maxson(*root); 
       if (((*root)->left==NULL)&&((*root)->right==NULL))
       {
           return;
       }
       if (temp->val>(*root)->val)
       {
          swap(*root,temp);
          
       }
       arrange(&((*root)->left));
       arrange(&((*root)->right));
    }
    Last edited by transgalactic2; 03-25-2009 at 05:09 AM.

  5. #5
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,794
    Quote Originally Posted by transgalactic2 View Post
    acctually i am not using the father at all so i dont care
    If you do not care about your code - stop posting it here
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    my main problem is marked in a comment "here is the problem" in the code.
    the problem is when i free the memory
    of pointer "leaf"
    then when i want it to point to NULL
    it doesnt do it.
    the debuger shows some random memory instead of NULL
    ??

  7. #7
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i get run time error
    i put every where that if it stumbles on NULL
    then return;

    but it doesnt go in
    ??

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define false 0
    #define true 1
    
    
    typedef struct TreeNode
    {
    	struct TreeNode *father;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	double val;
    }TreeNode;
    
    TreeNode * maxson(TreeNode * root);
    void swap(TreeNode * root,TreeNode * node);
    double deletemax(TreeNode **heap,TreeNode *leaf);
    TreeNode * maxson(TreeNode * root);
    void arrange(TreeNode ** root);
    int main()
    {
       TreeNode* root;
       double t;
       root=(TreeNode*)malloc(sizeof(TreeNode));
       root->val=9;
       root->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->right->val=4;
       root->right->left=NULL;
       root->right->right=NULL;
       root->right->father=root;
    
       root->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->val=8;
       root->left->left=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->left->val=7;
       root->left->right=(TreeNode*)malloc(sizeof(TreeNode));
       root->left->right->val=6;
       root->left->right->father=root->left;
       root->left->left->father=root->left;
    
       root->left->right->right=NULL;
       root->left->right->left=NULL;
    
       root->left->left->right=NULL;
       root->left->left->left=NULL;
    
       t=deletemax(&root,root->left->right);
       return 0;
    }
    
    double deletemax(TreeNode **heap,TreeNode *leaf)//i have to use this signature
    {
    	double temp=(*heap)->val;
      swap(*heap,leaf);
      
      free(leaf);
      leaf=NULL;
       arrange(heap);
     return temp;
      
    }
    void swap(TreeNode * root,TreeNode * node)
    {
    	double temp;
        temp=root->val;
        root->val=node->val;
    	node->val=temp;
    
    }
    
    TreeNode * maxson(TreeNode * root)
    {
    	if (root==NULL)
    	{
           return NULL;
    	}
    	if ((root->left==NULL)&&(root->right==NULL))
    	{
          return NULL;
    	}
    	if (root->left==NULL)
    	{
          return root->right;
    	}
    	
    	if (root->right==NULL)
    	{
          return root->left;
    	}
     
      if (root->left->val>root->right->val)
      {
            return root->left;
      }
      else
      {
            return root->right;
      }
    }
    
    void arrange(TreeNode ** root)
    {
       TreeNode* temp;
        
       if (((*root)->left==NULL)&&((*root)->right==NULL))
       {
           return;
       }
       temp=maxson(*root);
       if (temp==NULL)
       {
    	   return;
       }
       if (temp->val>(*root)->val)
       {
          swap(*root,temp);
          
       }
       arrange(&((*root)->left));
       arrange(&((*root)->right));
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap vs stack memory question
    By donglee in forum C++ Programming
    Replies: 4
    Last Post: 01-23-2009, 04:34 PM
  2. Understanding the stack and heap
    By yougene in forum C Programming
    Replies: 4
    Last Post: 01-19-2009, 05:22 AM
  3. Basic Heap Question?
    By justConfused in forum C Programming
    Replies: 4
    Last Post: 12-02-2008, 12:26 PM
  4. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  5. I have a Question about memory usage for C.
    By bobthefish3 in forum C Programming
    Replies: 34
    Last Post: 12-24-2001, 04:37 PM