heap arrainging question..

This is a discussion on heap arrainging question.. within the C Programming forums, part of the General Programming Boards category; a heap is a binary tree in which the root is bigger then both its sons. i need to write ...

  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 04: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
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    run your code in the debugger.

    Also think - what will happen to the father after you free the son
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  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 06:09 AM.

  5. #5
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21