A C implementation of Binary Heap

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
 
M

Mark Bluemel

Everything is explained in beginning comments:

WANTED:  To print the elements in the tree

That's what it does.
GOT:     printing an extra line with empty values

Hint: How many elements do you think you have? Why do you think that?
Have you stepped through your code with a pad of paper and a pencil?
If not, why not?

....
int main(void)
{
  struct BH_node* root = BH_init();

How many nodes here?
  BH_insert(root, "A1", 'A');

How many nodes here?
  BH_print(root);

How many nodes do you print?
  free(root);

This is pointless. If you want to do this properly, you need to have a
decent cleanup mechanism - free()ing the root isn't that.
  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
 
U

user923005

In



Yes, you are (slightly) confused. A heap is a tree, but a tree isn't
/necessarily/ a heap.

I was just trying to get a handle on the objection.
Put more succinctly:
A heap is a kind of {specialization of} a tree.
A tree is a kind of {specialization of} a graph.
A heap has to be a tree, but a tree does not have to be a heap (in
fact, most of them aren't).
 
B

Ben Pfaff

user923005 said:
Put more succinctly:
A heap is a kind of {specialization of} a tree.
A tree is a kind of {specialization of} a graph.
A heap has to be a tree, but a tree does not have to be a heap (in
fact, most of them aren't).

There is a missing distinction here, in my opinion. A binary
tree is not a tree, because a binary tree distinguishes between
left and right children but a tree does not.

In other words,

A
/
B

and

A
\
B

are the same tree, but different binary trees.

Maybe that's just another kind of specialization.
 
U

user923005

There is a missing distinction here, in my opinion.  A binary
tree is not a tree, because a binary tree distinguishes between
left and right children but a tree does not.

In other words,

     A
    /
   B

and

   A
    \
     B

are the same tree, but different binary trees.

Maybe that's just another kind of specialization.

To me, every connected graph with a root is a tree.
B
\
A
And:
B
/
A
are two more trees.

That doesn't mean a binary tree is not a tree.
 
B

Ben Pfaff

user923005 said:
To me, every connected graph with a root is a tree.
B
\
A
And:
B
/
A
are two more trees.

If these are different trees, what distinguishes them? They both
consist of a root B with a single child A.
That doesn't mean a binary tree is not a tree.

This is true, I think. But a tree with at most 2 children per
node is not a binary tree unless you label the children as left
or right children.
 
U

user923005

If these are different trees, what distinguishes them?  They both
consist of a root B with a single child A.

It depends on what kind of tree they are (if there is any
specialization).
On the one hand, if we are considering B as the root, they both have
child A.
So in that sense, they are the same tree.
But they might be some specialized kind of tree, in which case they
are different.
For instance, one of them might be a binary tree with reverse ordering
(IOW a greater than tree instead of a less than tree).
So they are the same in one sense, but they can also be different.
 
P

Phil Carmody

Richard Heathfield said:
In


Yes, you are (slightly) confused. A heap is a tree, but a tree isn't
/necessarily/ a heap.

True, but I presume he wants his trees to be ordered given the
context he's using in (a binary search tree):
"""
struct BH_node* BH_insert(struct BH_node* s, char p[], char g)
....
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);
"""

The heap
1
3 2
is not a binary search tree. (Nor can any heap with more than 2 distinct
values, PLaaEFtR.)

Phil
 
P

Phil Carmody

You've got to have an 'acyclic' in there too. Else a rho would be a tree.
If these are different trees, what distinguishes them? They both
consist of a root B with a single child A.


This is true, I think. But a tree with at most 2 children per
node is not a binary tree unless you label the children as left
or right children.

This is a very important distinction to draw, certainly, but I don't
know if the terminology exists to make just that distinction. 'binary'
implies restrictions on the in-order and out-order of the nodes,
but doesn't imply that siblings are indexed.

Phil
 
B

Ben Pfaff

Phil Carmody said:
You've got to have an 'acyclic' in there too. Else a rho would be a tree.


This is a very important distinction to draw, certainly, but I don't
know if the terminology exists to make just that distinction. 'binary'
implies restrictions on the in-order and out-order of the nodes,
but doesn't imply that siblings are indexed.

Certainly terminology exists; see e.g. page 308 of _The Art of
Computer Programming, Vol. 1 (3rd edition):

If the relative order of the subtrees T1, ..., Tm... is
important, we say that the tree is an /ordered tree/. ...
Ordered trees are also called "plane trees" by some
authors... The very nature of computer representation
defines an implicit ordering for any tree, so in most cases
ordered trees are of greatest interest to us. We will
therefore tacitly assume that /all trees we discuss are
ordered, unless explicitly stated otherwise/.
 
P

Phil Carmody

Ben Pfaff said:
Certainly terminology exists; see e.g. page 308 of _The Art of
Computer Programming, Vol. 1 (3rd edition):

If the relative order of the subtrees T1, ..., Tm... is
important, we say that the tree is an /ordered tree/. ...
Ordered trees are also called "plane trees" by some
authors...

Thanks for sniffing that out. If I had to randomly pick a word
from thin air, I'd have chosen 'ordered', so obviously some Knuth
has crept in by osmisis.
The very nature of computer representation
defines an implicit ordering for any tree, so in most cases
ordered trees are of greatest interest to us. We will
therefore tacitly assume that /all trees we discuss are
ordered, unless explicitly stated otherwise/.

That might be why the distinction wasn't so blatant - we're not
distinguishing ordered ones at all, we're distinguishing non-ordered
ones instead!

Phil
 
A

arnuld

There is a missing distinction here, in my opinion. A binary tree is
not a tree, because a binary tree distinguishes between left and right
children but a tree does not.

In other words,

A
/
B

and

A
\
B

are the same tree, but different binary trees.

I think I saw that in Knuth, don't remember which volume.
 
A

arnuld

True, but I presume he wants his trees to be ordered given the context
he's using in (a binary search tree): """
struct BH_node* BH_insert(struct BH_node* s, char p[], char g) ...
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);
"""

The heap
1
3 2
is not a binary search tree. (Nor can any heap with more than 2 distinct
values, PLaaEFtR.)

1
3 2

Its not a binary heap I know. In a binary heap, ever child's value is
less as compared to its parent and root node has the largest value. But
that 1-3-2 tree is a Binary Tree. Anything wrong in saying that ?
 
A

arnuld

Hint: How many elements do you think you have? Why do you think that?
Have you stepped through your code with a pad of paper and a pencil?
If not, why not?

...SNIP..

I have corrected it and it prints only the existing elements. See down
for the new code.
This is pointless. If you want to do this properly, you need to have a
decent cleanup mechanism - free()ing the root isn't that.


Actually, this was just a dummy thing, the real idea is to create a
heap_free() function which will recursively free() the whole heap. It
does not work as desired, has some memory leak and also it added 2
values and they are inside the heap but it does not print the
statement I added but I am trying figure out the problems. I
theoretically know what a heap is and what a binary tree is. I am
*not* confused. Its that reading theory, understanding it and writing
code are skills 2 worlds apart from each other:



/* 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 O(log(n))
* - delete the element with the highest priority (which of course is
the root node in a Binary Heap) O(log(n))
* - find the maximum element without removing it (again it will be
root node, but will take only O(1) time)
*
* The struct will contain a character string (as priority) and a char
as (his grade). We will use the 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 and then heapify the Binary-tree to make a
* Binary-heap. So we will first add entries to a Binary-Tree and then
heapify it to get a Binary Heap.
*
*
* VERSION 0.1
*
*/


#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* );
void BH_free(struct BH_node* s);



int main(void)
{
struct BH_node* root = NULL;

root = BH_insert(root, "A1", 'A');
root = BH_insert(root, "A2", 'B');

BH_print(root);

BH_free(root);
root = NULL;

return 0;
}




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;
}
}
else
{
cmp = strcmp(s->prio, p);

if( 0 == cmp )
{
printf("Duplicate entry, will not add\n");
}
else if( cmp < 0 )
{
printf("value added to LEFT\n");
s->left = BH_insert(s->left, p, g);
}
else
{
printf("value added to RIGHT\n");
s->right = BH_insert(s->right, p, g);
}
}


return s;
}



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;
}


void BH_free(struct BH_node* s)
{
/* Don't have any idea on how to recursively free the Binary Heap */
if(s)
{
if( (NULL == s->left) && (NULL == s->right) )
{
free(s);
s = NULL;
}
else
{
BH_free(s->left);
BH_free(s->right);
}
}
}


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
value added to LEFT
priority: A2, grade: B
 
B

Ben Bacarisse

arnuld said:
I
theoretically know what a heap is and what a binary tree is. I am
*not* confused. Its that reading theory, understanding it and writing
code are skills 2 worlds apart from each other:

That mean you know that the code you wrote for "insert" is for a
binary search tree. Do you want someone to re-write it to be a heap?
I am not sure what you are asking about anymore.

<snip code>
 
P

Phil Carmody

arnuld said:
On Sun, 11 Oct 2009 14:56:55 +0300, Phil Carmody wrote:
True, but I presume he wants his trees to be ordered given the context
he's using in (a binary search tree): """
struct BH_node* BH_insert(struct BH_node* s, char p[], char g) ...
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);
"""

The heap
1
3 2
is not a binary search tree. (Nor can any heap with more than 2 distinct
values, PLaaEFtR.)

1
3 2

Its not a binary heap I know. In a binary heap, ever child's value is
less as compared to its parent and root node has the largest value.

It is a binary heap. In a binary heap, every child's relates to its
parent in the same way. In some heaps that's comparing less than, in
some heaps it's comparing more than.
But
that 1-3-2 tree is a Binary Tree. Anything wrong in saying that ?

Yes. One child subtree must contain all the elements which compare one
way relative to the parent node, and the other child subtree must contain
all the elements which compare the other way.

This is basic stuff. Get a book, or even look at wackypedia.

Phil
 
C

chad

Hint: How many elements do you think you have? Why do you think that?
Have you stepped through your code with a pad of paper and a pencil?
If not, why not?
...SNIP..

I have corrected it and it prints only the existing elements. See down
for the new code.
This is pointless. If you want to do this properly, you need to have a
decent cleanup mechanism - free()ing the root isn't that.

Actually, this was just a dummy thing, the real idea is to create a
heap_free() function which will recursively free() the whole heap. It
does not work as desired, has some memory leak and also it added 2
values and they are inside the heap but it does not print the
statement I added but I am trying figure out the problems. I
theoretically know what a heap is and what a binary tree is. I am
*not* confused. Its that reading theory, understanding it and writing
code are skills 2 worlds apart from each other:

/* 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 O(log(n))
 * - delete the element with the highest priority (which of course is
the root node in a Binary Heap) O(log(n))
 * - find the maximum element without removing it (again it will be
root node, but will take only O(1) time)
 *
 * The struct will contain a character string (as priority) and a char
as  (his grade). We will use the 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 and then heapify the Binary-tree to make a
 * Binary-heap. So we will first add entries to a Binary-Tree and then
heapify it to get a Binary Heap.
 *
 *
 * VERSION 0.1
 *
 */

#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* );
void BH_free(struct BH_node* s);

int main(void)
{
  struct BH_node* root = NULL;

  root = BH_insert(root, "A1", 'A');
  root = BH_insert(root, "A2", 'B');

  BH_print(root);

  BH_free(root);
  root = NULL;

  return 0;

}

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;
        }
    }
  else
    {
      cmp = strcmp(s->prio, p);

      if( 0 == cmp )
        {
          printf("Duplicate entry, will not add\n");
        }
      else if( cmp < 0 )
        {
          printf("value added to LEFT\n");
          s->left  = BH_insert(s->left,  p, g);
        }
      else
        {
          printf("value added to RIGHT\n");
          s->right = BH_insert(s->right, p, g);
        }
    }

  return s;

}

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;

}

void BH_free(struct BH_node* s)
{
  /* Don't have any idea on how to recursively free the Binary Heap */
  if(s)
    {
      if( (NULL == s->left) && (NULL == s->right) )
        {
          free(s);
          s = NULL;
        }
      else
        {
          BH_free(s->left);
          BH_free(s->right);
        }
    }

}

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
value added to LEFT
priority: A2, grade: B

Wouldn't you free a tree by doing a post order traversal?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads


Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top