A
arnuld
Everything is explained in beginning comments:
WANTED: To print the elements in the tree
GOT: printing an extra line with empty values
/* A simple program using a struct to implement a Binary Heap in C. This
binary heap will support 3 operations:
*
* - insert an element to the heap.
* - delete the element with the highest priority (which of course is the
root node in a Binary Heap)
* - find the maximum element without removing it (again it will be root
node)
*
* The struct will contain a character string (as priority) and a char as
grade. We will use string to decide
* whether some student has higher priority than the other.
* As per Wikiepdia: http://en.wikipedia.org/wiki/
Binary_heap#Building_a_heap , directly inserting an element in a Binary
Heap
* is not as much efficient as compared to first adding all elements to a
Binary Tree (B-Tree) and then heapify the B-tree
* to make a B-heap. So we will first add entries to a B-Tree and then
heapify it.
*
*
* VERSION 0.0
*
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum { VAL_SUCC = 0,
VAL_ERR = -1
};
enum { PRIORITY_SIZE = 10 };
struct BH_node
{
char prio[PRIORITY_SIZE];
char grade;
struct BH_node* left;
struct BH_node* right;
};
struct BH_node* BH_init(void);
struct BH_node* BH_insert(struct BH_node*, char [], char );
void BH_print(struct BH_node* );
int main(void)
{
struct BH_node* root = BH_init();
BH_insert(root, "A1", 'A');
BH_print(root);
free(root);
return 0;
}
struct BH_node* BH_init(void)
{
struct BH_node* p = malloc(1 * sizeof *p);
if( NULL == p )
{
return NULL;
}
p->left = p->right = NULL;
return p;
}
struct BH_node* BH_insert(struct BH_node* s, char p[], char g)
{
int cmp = VAL_ERR;
if(NULL == s)
{
s = BH_init();
if( NULL == s)
{
fprintf(stderr, "IN: %s, LINE: %d, Out of memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(s->prio, p);
s->grade = g;
}
return s;
}
cmp = strcmp(s->prio, p);
if( 0 == cmp ) printf("Duplicate entry, will not add\n");
else if( cmp < 0 ) s->left = BH_insert(s->left, p, g);
else s->right = BH_insert(s->right, p, g);
return s;
}
void BH_print(struct BH_node* s)
{
if( NULL == s ) return;
BH_print(s->left);
printf("priority: %s, grade: %c\n", s->prio, s->grade);
printf("--------------------------\n");
BH_print(s->right);
}
==================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-heap.c
[arnuld@dune programs]$ ./a.out
priority: A1, grade: A
WANTED: To print the elements in the tree
GOT: printing an extra line with empty values
/* A simple program using a struct to implement a Binary Heap in C. This
binary heap will support 3 operations:
*
* - insert an element to the heap.
* - delete the element with the highest priority (which of course is the
root node in a Binary Heap)
* - find the maximum element without removing it (again it will be root
node)
*
* The struct will contain a character string (as priority) and a char as
grade. We will use string to decide
* whether some student has higher priority than the other.
* As per Wikiepdia: http://en.wikipedia.org/wiki/
Binary_heap#Building_a_heap , directly inserting an element in a Binary
Heap
* is not as much efficient as compared to first adding all elements to a
Binary Tree (B-Tree) and then heapify the B-tree
* to make a B-heap. So we will first add entries to a B-Tree and then
heapify it.
*
*
* VERSION 0.0
*
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum { VAL_SUCC = 0,
VAL_ERR = -1
};
enum { PRIORITY_SIZE = 10 };
struct BH_node
{
char prio[PRIORITY_SIZE];
char grade;
struct BH_node* left;
struct BH_node* right;
};
struct BH_node* BH_init(void);
struct BH_node* BH_insert(struct BH_node*, char [], char );
void BH_print(struct BH_node* );
int main(void)
{
struct BH_node* root = BH_init();
BH_insert(root, "A1", 'A');
BH_print(root);
free(root);
return 0;
}
struct BH_node* BH_init(void)
{
struct BH_node* p = malloc(1 * sizeof *p);
if( NULL == p )
{
return NULL;
}
p->left = p->right = NULL;
return p;
}
struct BH_node* BH_insert(struct BH_node* s, char p[], char g)
{
int cmp = VAL_ERR;
if(NULL == s)
{
s = BH_init();
if( NULL == s)
{
fprintf(stderr, "IN: %s, LINE: %d, Out of memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(s->prio, p);
s->grade = g;
}
return s;
}
cmp = strcmp(s->prio, p);
if( 0 == cmp ) printf("Duplicate entry, will not add\n");
else if( cmp < 0 ) s->left = BH_insert(s->left, p, g);
else s->right = BH_insert(s->right, p, g);
return s;
}
void BH_print(struct BH_node* s)
{
if( NULL == s ) return;
BH_print(s->left);
printf("priority: %s, grade: %c\n", s->prio, s->grade);
printf("--------------------------\n");
BH_print(s->right);
}
==================== OUTPUT =========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-heap.c
[arnuld@dune programs]$ ./a.out
priority: A1, grade: A