-
Notifications
You must be signed in to change notification settings - Fork 0
/
finalMinHeap.c
160 lines (125 loc) · 2.9 KB
/
finalMinHeap.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct Node
{
int nodeValue;
struct Node *left;
struct Node *right;
};
int NumberOfNodes = 1;
int binaryArray[10];
int NumberToBinary(int c){
int i = 0;
while(c!=0){
binaryArray[i] = c%2;
c = c/2;
i++;
}
return (i-2);
}
void heapify(struct Node* root){
int temp;
if((root->left != NULL) && (root->right != NULL) && (root->left->nodeValue < root->nodeValue) && (root->left->nodeValue < root->right->nodeValue)){
temp = root->nodeValue;
root->nodeValue = root->left->nodeValue;
root->left->nodeValue = temp;
heapify(root->left);
}else if((root->right != NULL) && (root->left != NULL) && (root->right->nodeValue < root->nodeValue)){
temp = root->nodeValue;
root->nodeValue = root->right->nodeValue;
root->right->nodeValue = temp;
heapify(root->right);
}
return;
}
struct Node* extractMin(struct Node* root)
{
if(NumberOfNodes == 2)
{
printf("\nMinimum is %d\n",root->nodeValue);
NumberOfNodes--;
return NULL;
}
else if(NumberOfNodes > 2)
{
printf("\nMinimum is %d\n",root->nodeValue);
struct Node* temp = root;
int i = NumberToBinary(NumberOfNodes-1);
while(i > 0)
{
if(binaryArray[i] == 0)
{
temp = temp -> left;
}
else
{
temp = temp -> right;
}
i--;
}
if(binaryArray[i] == 0)
{
root -> nodeValue = temp -> left -> nodeValue;
temp -> left = NULL;
}
else
{
root -> nodeValue = temp -> right -> nodeValue;
temp -> right = NULL;
}
NumberOfNodes--;
heapify(root);
return root;
}
else
{
return root;
}
}
struct Node* insert(struct Node *root,int key,int ind){
if(root == NULL){
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->nodeValue = key;
newNode->left = newNode->right = NULL;
NumberOfNodes++;
return newNode;
}
int temp;
if(binaryArray[ind]==0){
if(root->nodeValue>key){
temp = root->nodeValue;
root->nodeValue = key;
key = temp;
}
ind--;
root->left = insert(root->left,key,ind);
}else{
if(root->nodeValue>key){
temp = root->nodeValue;
root->nodeValue = key;
key = temp;
}
ind--;
root->right = insert(root->right,key,ind);
}
return root;
}
void isEmpty(struct Node* root){
if(root == NULL){
printf("Is Empty\n");
}else{
printf("Is Not Empty\n");
}
}
int main(){
struct Node *heaproot = NULL;
heaproot = insert(heaproot,5,NumberToBinary(NumberOfNodes));
heaproot = insert(heaproot,14,NumberToBinary(NumberOfNodes));
heaproot = insert(heaproot,31,NumberToBinary(NumberOfNodes));
heaproot = insert(heaproot,26,NumberToBinary(NumberOfNodes));
heaproot = insert(heaproot,14,NumberToBinary(NumberOfNodes));
heaproot = extractMin(heaproot);
printf("press ENTER to close.");
getchar();
}