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){
}