A C implementation of Binary Heap

[arnuld]

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.

Yep, I made that very clear in the beginning comments. I am going to
create a Binary Search Tree and then will heapify it make it a Binary
Heap (Wikipedia says that this method is more efficient).

 

[arnuld]

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.

Yes, I forgot to mention that I will be making a max Binary Heap.

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.

Well, I don't understand your definition of tree but from section 6.5 of
K&R2 , I can easily deduce that in Binary Search Tree, all kids
(children with lesser value than root node go to one side (usually
left) while all with values greater than root node go the other side
(usually right). This is what I did and I don't understand why you call
it wrong.

 

[arnuld]

Here is the new code, with 2 functions to add elements and print them. It
does not print anything even though when I have added 2 elements :-\



/* A simple program using a struct to implement a max 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.3
*
*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>


enum { VAL_SUCC = 0,
VAL_ERR = -1
};

enum { PRIORITY_SIZE = 20 };


struct BH_node
{
char priority[PRIORITY_SIZE];
char grade;
struct BH_node* left;
struct BH_node* right;
};


struct BH_node* BH_node_create(char [], char);
struct BH_node* BH_insert(struct BH_node*, struct BH_node* );

void BH_print(struct BH_node*);


int main(void)
{
struct BH_node* root = NULL;
struct BH_node* a1 = BH_node_create("First Class", 'A');
struct BH_node* a2 = BH_node_create("Second Class", 'B');

BH_insert(root, a1);
BH_insert(root, a2);

BH_print(root);

/*
BH_free(root);
root = NULL;
*/

return 0;
}



struct BH_node* BH_insert(struct BH_node* s, struct BH_node* n)
{
if(NULL == n)
{
fprintf(stderr, "IN: %s : Can not add NULL node\n", __func__);
}

if(NULL == s)
{
s = n;
}
else
{
int cmp = strcmp(n->priority, s->priority);

if(cmp == 0)
{
/* fprintf(stderr, "IN: %s : Duplicate entry, will not add
\n", __func__); */
}
else if(cmp < 0)
{
BH_insert(s->left, n);
}
else
{
BH_insert(s->right, n);
}
}

return s;
}




struct BH_node* BH_node_create(char priority[], char grade)
{
struct BH_node* p = malloc(1 * sizeof *p);

if(NULL == p)
{
/* fprintf(stderr,"IN: %s :, Out of Memory\n", __func__); */
}
else
{
strcpy(p->priority, priority);
p->grade = grade;
p->left = p->right = NULL;
}

return p; /* Make sure calling function checks for NULL */
}



/* print tree in-order */
void BH_print(struct BH_node* s)
{
if(s)
{
BH_print(s->left);
printf("Student's Priority: %s\n", s->priority);
printf("Student's Grade: %c\n", s->grade);
BH_print(s->right);
}
}


========================== OUTPUT ================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-heap.c
[arnuld@dune programs]$ ./a.out
[arnuld@dune programs]$

 

[arnuld]

I was thinking of keeping root node and other nodes separate for this
Binary Heap, like I did for a queue:


struct my_struct
{
int num;
struct my_struct* next;
};

struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};



But because of recursive nature of Trees I am unable to do that:

 

[arnuld]

Here is the 4th verison of the program. It works fine, it adds and prints
the tree elements and free() also works fine. The only thing that has
remained is how to heapify it. Any ideas on that ?

(Thanks to Chad for telling me the idea of using post-order to free() the
tree)



/* A simple program using a struct to implement a max 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.4
*
*/


#include <stdio.h>
#include <string.h>
#include <stdlib.h>


enum { VAL_SUCC = 0,
VAL_ERR = -1
};

enum { PRIORITY_SIZE = 20 };


struct BH_node
{
char priority[PRIORITY_SIZE];
char grade;
struct BH_node* left;
struct BH_node* right;
};


struct BH_node* BH_node_create(char [], char);
void BH_free(struct BH_node* s);
struct BH_node* BH_insert(struct BH_node**, struct BH_node* );


void BH_print(struct BH_node*);


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

struct BH_node* a1 = BH_node_create("First Class", 'A');
struct BH_node* a2 = BH_node_create("Second Class", 'B');

if(a1) BH_insert(&root, a1);
if(a1) BH_insert(&root, a2);

BH_print(root);

BH_free(root);
root = NULL;


return 0;
}



struct BH_node* BH_insert(struct BH_node** s, struct BH_node* n)
{
if(NULL == n)
{
/* fprintf(stderr, "IN: %s : Can not add NULL node\n",
__func__); */
}
else if(NULL == s)
{
/* fprintf(stderr, "IN: %s, NULL address of root node ?? \n",
__func__); */
}
else if(NULL == *s)
{
*s = n;
}
else
{
struct BH_node* r = *s;
int cmp = strcmp(n->priority, r->priority);

if(cmp == 0)
{
/* fprintf(stderr, "IN: %s : Duplicate entry, will not add\n",
__func__); */
}
else if(cmp < 0)
{
BH_insert( &(r->left), n);
}
else
{
BH_insert( &(r->right), n);
}
}

return *s;
}


struct BH_node* BH_node_create(char priority[], char grade)
{
struct BH_node* p = malloc(1 * sizeof *p);

if(NULL == p)
{
/* fprintf(stderr,"IN: %s :, Out of Memory\n", __func__); */
}
else
{
strcpy(p->priority, priority);
p->grade = grade;
p->left = p->right = NULL;
}

return p; /* Make sure calling function checks for NULL */
}



/* print tree in-order */
void BH_print(struct BH_node* s)
{
if(s)
{
BH_print(s->left);
printf("Student's Priority: %s\n", s->priority);
printf("Student's Grade: %c\n", s->grade);
BH_print(s->right);
}
}

/* free() the tree using post-order */
void BH_free(struct BH_node* s)
{
if(s)
{
BH_free(s->left);
BH_free(s->right);
free(s);
}
}


============================== OUTPUT =================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-heap.c
[arnuld@dune programs]$ ./a.out
Student's Priority: First Class
Student's Grade: A
Student's Priority: Second Class
Student's Grade: B
[arnuld@dune programs]$

 

[Phil Carmody]

Yep, I made that very clear in the beginning comments. I am going to
create a Binary Search Tree and then will heapify it make it a Binary
Heap (Wikipedia says that this method is more efficient).

_What_ is more efficient than _what_?

(Is that explicit enough?)

Phil

 

[arnuld]

_What_ is more efficient than _what_?

(Is that explicit enough?)

Perhaps you can read the beginning comments of any version of program I
posted and that will tell you what is more efficient than what.

 

[Phil Carmody]

Yes, I forgot to mention that I will be making a max Binary Heap.



Well, I don't understand your definition of tree but from section 6.5 of
K&R2 , I can easily deduce that in Binary Search Tree, all kids
(children with lesser value than root node go to one side (usually
left) while all with values greater than root node go the other side
(usually right). This is what I did and I don't understand why you call
it wrong.

The tree in quesion being:
So, is 3 less than 1, or is 2 less than 1?

Phil

 

[arnuld]

The tree in quesion being:
1
3 2

So, is 3 less than 1, or is 2 less than 1?

Oh... holy cow.....

 

[Phil Carmody]

Here is the new code, with 2 functions to add elements and print them. It
does not print anything even though when I have added 2 elements :-\

You haven't added 2 new elements, that's why.

int main(void)
{
struct BH_node* root = NULL;
struct BH_node* a1 = BH_node_create("First Class", 'A');
struct BH_node* a2 = BH_node_create("Second Class", 'B');

BH_insert(root, a1); //...

struct BH_node* BH_insert(struct BH_node* s, struct BH_node* n)
{ //...
if(NULL == s)
{
s = n;
}
else
{ //...
}

return s;
}

root is still NULL after that call, isn't it?


And note that you're not building a heap, you're still building
(or failing to build) a binary search tree:

int cmp = strcmp(n->priority, s->priority);

if(cmp == 0)
{
/* fprintf(stderr, "IN: %s : Duplicate entry, will not add
\n", __func__); */
}
else if(cmp < 0)
{
BH_insert(s->left, n);
}
else
{
BH_insert(s->right, n);
}

I've told you this already.

Phil

 

[Phil Carmody]

Perhaps you can read the beginning comments of any version of program I
posted and that will tell you what is more efficient than what.

Given that your comments talk about heaps whilst you perform
binary search tree insertions, I do not expect to be able to
learn much from your comments.

Version 4 has the _same_ mistake, for reference.

Phil

 

[Phil Carmody]

Here is the 4th verison of the program. It works fine, it adds and prints
the tree elements and free() also works fine. The only thing that has
remained is how to heapify it. Any ideas on that ?

Just scan through the tree in order, placing the elements in their known
positions in the heap. However, creating a heap _loses_ information, as
you've effectively got all the nodes completely sorted once you've got a
BST. Also note that it's odd to have a tree-like structure for a heap,
heaps are more often implemented using contiguous blocks of memory.

Phil

 

[arnuld]

Just scan through the tree in order, placing the elements in their known
positions in the heap.

Wikipedia and Sedgewick said that you use heapify up or down to build a
heap out of a binary search tree.

However, creating a heap _loses_ information, as
you've effectively got all the nodes completely sorted once you've got a
BST. Also note that it's odd to have a tree-like structure for a heap,
heaps are more often implemented using contiguous blocks of memory.

You mean a doubly linked list ?

 

[arnuld]

Given that your comments talk about heaps whilst you perform binary
search tree insertions, I do not expect to be able to learn much from
your comments.

Where did I say I am building a heap (at this point of time) ?


As per Wikiepdia: http://en.wikipedia.org/wiki/
Binary_heap#Building_a_heap , directly adding 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.4
*
*/


I am saying that, at current moment of time, I am building a Binary
Tree. Hence insertions will go like they go with binary trees.

 

[user923005]

Wikipedia and Sedgewick said that you use heapify up or down to build a
heap out of a binary search tree.


You mean a doubly linked list ?

No, he means an array

 

[arnuld]

No, he means an array

An array of structures ?

Will it be as efficient as a double linked list ?

2nd I don't know the number of elements in advance, so using array is
out of question. I can use 1000 elements array in the beginning but
then I have to realloc (if I need) 100 more elements. I don't think
its will be as efficient as building a dynamic binary search tree.

 

[Ben Bacarisse]

Wikipedia and Sedgewick said that you use heapify up or down to build a
heap out of a binary search tree.

I doubt that Sedgewick says this but I don't have the book to check.
Wikipedia does not say this unless I've missed it.

You have confused "binary tree" with "binary search tree". Adding to
a BST is O(log n) so building and then "heapifying" is at least O(n
log n). Heapifying an almost complete binary tree is O(n). It is
possible that heapifying a BST is even more expense the O(n log n)
(hence my "at least") because a BST won't have the almost complete
property to start with. I haven't checked the analysis to see if that
matters.

The array representation has lots of advantages. You need a good
reason not to use it.

<snip>

 

[Ben Bacarisse]

An array of structures ?

You get to choose. You can use pointers if you prefer.

Will it be as efficient as a double linked list ?

Eh? I don't see that as an alternative.

2nd I don't know the number of elements in advance, so using array is
out of question. I can use 1000 elements array in the beginning but
then I have to realloc (if I need) 100 more elements. I don't think
its will be as efficient as building a dynamic binary search tree.

It will be more efficient because a BST is wrong. If you mean "will
it be as efficient as building a dynamic binary tree" then I think
you'd have to measure it. If I had to guess, I'd say the array will
pay off because there will be fewer allocations and the algorithms
are simpler.

 

[arnuld]

You have confused "binary tree" with "binary search tree". Adding to a
BST is O(log n) so building and then "heapifying" is at least O(n log
n). Heapifying an almost complete binary tree is O(n). It is possible
that heapifying a BST is even more expense the O(n log n) (hence my "at
least") because a BST won't have the almost complete property to start
with. I haven't checked the analysis to see if that matters.

The array representation has lots of advantages. You need a good reason
not to use it.

These are the main points I am focusing on:

1) Millions of elements to process, with no idea of how many to begin
with.
2) Insertion with priority
3) delete with max priority
4) find the element with max priority
5) only 1 priority queue. No joining of different queues. (that is where
I rejected the possibility of using a Binomial Queue)


2nd it has to run on some embedded platform where 64 MB of RAM will be
available definitely, more can be available too. I will use arrays of
pointers to structures if you tell me they will be good for me. I am not
as experienced as you are.

Sedgewick used the arrays to demonstrate binary heap in his book and at
the same time in section 9.1 he has this table:

Insert Del Max Find Max Delete
Ordered array: N 1 1 1
Unordered array: 1 N N N
Ordered list: N 1 1 1
Unordered list: 1 N N N
heap: LogN LogN 1 LogN


So I thought with the requirements I mentioned Heap fits good.

 

[Ben Bacarisse]

These are the main points I am focusing on:

1) Millions of elements to process, with no idea of how many to begin
with.
2) Insertion with priority
3) delete with max priority
4) find the element with max priority
5) only 1 priority queue. No joining of different queues. (that is where
I rejected the possibility of using a Binomial Queue)


2nd it has to run on some embedded platform where 64 MB of RAM will be
available definitely, more can be available too. I will use arrays of
pointers to structures if you tell me they will be good for me. I am not
as experienced as you are.

Sedgewick used the arrays to demonstrate binary heap in his book and at
the same time in section 9.1 he has this table:

Insert Del Max Find Max Delete
Ordered array: N 1 1 1

Insert is surely Log N for an ordered array? Mind you, I am not sure
what is being measured here, so who knows. Maybe data moves are being
measured and some technique is used to reduce moves on delete. I
don't know.

Unordered array: 1 N N N
Ordered list: N 1 1 1
Unordered list: 1 N N N
heap: LogN LogN 1 LogN

So I thought with the requirements I mentioned Heap fits good.

It does. I don't see a problem. I'd use an array-based heap with a
clean interface so I could change it later if the large block
allocations became a problem (I am told they can be in embedded
systems). In fact, I'd probably use a sorted linked list or an
ordered array to prototype the code and plug in a heap later if
inserts were getting too slow. I am very fond of rapid prototyping.