# heap arrainging question..

• 03-25-2009
transgalactic2
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)); }```
• 03-25-2009
transgalactic2
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)); }```
• 03-25-2009
vart
run your code in the debugger.

Also think - what will happen to the father after you free the son
• 03-25-2009
transgalactic2
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)); }```
• 03-25-2009
vart
Quote:

Originally Posted by transgalactic2
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
• 03-25-2009
transgalactic2
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
??
• 03-25-2009
transgalactic2
i get run time error
i put every where that if it stumbles on NULL
then return;

but it doesnt go in
??
• 03-25-2009
transgalactic2
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)); }```