A C implementation of Binary Heap
arnuld
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
--------------------------
priority: , grade:
--------------------------
[arnuld@dune programs]$
--
www.lispmachine.wordpress.com
my email is @ the above blog.
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.
Phil Carmody
> Everything is explained in beginning comments:
>
> WANTED: To print the elements in the tree
You're confusing a tree with a heap.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
user923005
wrote:
> arnuld <sunr...@invalid.address> writes:
> > Everything is explained in beginning comments:
>
> > WANTED: To print the elements in the tree
>
> You're confusing a tree with a heap.
A heap is a tree, but a tree isn't a heap.
Or am I confused too?
Richard Heathfield
<2ee2d688-e9d8-4106...@r24g2000prf.googlegroups.com>,
user923005 wrote:
Yes, you are (slightly) confused. A heap is a tree, but a tree isn't
/necessarily/ a heap.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
user923005
> In
> <2ee2d688-e9d8-4106-80aa-66c9921e3...@r24g2000prf.googlegroups.com>,
>
> user923005 wrote:
> > On Oct 9, 9:31 am, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
> > wrote:
> >> arnuld <sunr...@invalid.address> writes:
> >> > Everything is explained in beginning comments:
>
> >> > WANTED: To print the elements in the tree
>
> >> You're confusing a tree with a heap.
>
> > A heap is a tree, but a tree isn't a heap.
> > Or am I confused too?
>
> 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).
Ben Pfaff
> 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.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
user923005
> user923005 <dcor...@connx.com> writes:
> > 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.
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.
Ben Pfaff
> 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.
user923005
> user923005 <dcor...@connx.com> writes:
> > 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.
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.
Phil Carmody
> In
> <2ee2d688-e9d8-4106...@r24g2000prf.googlegroups.com>,
> user923005 wrote:
>
>> On Oct 9, 9:31 am, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
>> wrote:
>>> arnuld <sunr...@invalid.address> writes:
>>> > Everything is explained in beginning comments:
>>>
>>> > WANTED: To print the elements in the tree
>>>
>>> You're confusing a tree with a heap.
>>
>> A heap is a tree, but a tree isn't a heap.
>> Or am I confused too?
>
> 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 Carmody
> user923005 <dco...@connx.com> writes:
>
>> To me, every connected graph with a root is a tree.
You've got to have an 'acyclic' in there too. Else a rho would be 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.
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.
Ben Pfaff
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/.
Phil Carmody
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!
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.
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 ?
arnuld
>> On 9 Oct, 11:18, arnuld <sunr...@invalid.address> wrote:
> 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.
> > 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.
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
--------------------------
priority: A1, grade: A
--------------------------
[arnuld@dune programs]$
Ben Bacarisse
> 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>
--
Ben.
Ben Pfaff
>> On Fri, 09 Oct 2009 12:19:35 -0700, Ben Pfaff wrote:
>
>> 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.
I included the relevant quote elsewhere in the thread.
Phil Carmody
>> 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.
chad
Wouldn't you free a tree by doing a post order traversal?
arnuld
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
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
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
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
Phil Carmody
_What_ is more efficient than _what_?
(Is that explicit enough?)
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
The tree in quesion being:
> > 1
> > 3 2
So, is 3 less than 1, or is 2 less than 1?
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 Carmody
>> On Thu, 15 Oct 2009 10:58:27 +0300, Phil Carmody wrote:
>
>> _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.
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 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.
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
No, he means an array
arnuld
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
>> On Thu, 15 Oct 2009 11:25:24 +0300, Phil Carmody wrote:
>
>> 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.
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.
Ben Bacarisse
>> On Oct 15, 2:31 pm, user923005 <dcor...@connx.com> wrote:
>>> On Oct 15, 2:29 am, arnuld <sunr...@invalid.address> wrote:
>>> You mean a doubly linked list ?
>
>> No, he means an array
>
> 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.
--
Ben.
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
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.
--
Ben.
arnuld
>> arnuld <sun...@invalid.address> writes:
>> 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.
If by Ordered array he means that, all elements are inserted with
ascending or descending order of priority, then of course it will take N,
because you have to do N comparisons to find the proper place to insert.
> 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.
I am writing a queue implementation of doubly linked list where elements
are added in descending order of priority. That way delete max will
always be 1 but insertion will be N in worst case.
or you think I should use a general queue, adding anywhere and then
insert will be 1 but delete max will be N ?
arnuld
> 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).
I don't think my seniors is going to agree with using an array with
1000 of heap data structures as elements, no not even 200.
Ben Bacarisse
>> On Thu, 15 Oct 2009 15:35:33 +0100, Ben Bacarisse wrote:
>
>>> arnuld <sun...@invalid.address> writes:
>
>>> 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.
>
> If by Ordered array he means that, all elements are inserted with
> ascending or descending order of priority, then of course it will take N,
> because you have to do N comparisons to find the proper place to
> insert.
Binary search takes log N comparisons to find the insertion point.
The table may be summarising a particular, less the optimal,
implementation, of course.
>> 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.
>
> I am writing a queue implementation of doubly linked list where elements
> are added in descending order of priority. That way delete max will
> always be 1 but insertion will be N in worst case.
Why waste the space with a double link? Do you have space to spare?
> or you think I should use a general queue, adding anywhere and then
> insert will be 1 but delete max will be N ?
It depends on the application. In many real-world cases, insert and
delete-max operations occur with roughly equal frequency so the
overall cost that matters is that of insert+delete-max.
If you can tolerate O(n) for this combined cost then an ordered list
will be fine. This n in is the length of the queue, of course. Do
you know the expected value of n over time?
--
Ben.
arnuld
> Why waste the space with a double link? Do you have space to spare?
no.
> It depends on the application. In many real-world cases, insert and
> delete-max operations occur with roughly equal frequency so the overall
> cost that matters is that of insert+delete-max.
>
> If you can tolerate O(n) for this combined cost then an ordered list
> will be fine. This n in is the length of the queue, of course. Do you
> know the expected value of n over time?
Not much, except that if I got a million elements and 1 million more were
added after 30 minutes then half of total will be deleted at the same
time. Except that no idea.
Giorgos Keramidas
>> On Thu, 15 Oct 2009 15:35:33 +0100, Ben Bacarisse wrote:
>>> arnuld <sun...@invalid.address> writes:
>>
>>> 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.
>
> If by Ordered array he means that, all elements are inserted with
> ascending or descending order of priority, then of course it will take
> N, because you have to do N comparisons to find the proper place to
> insert.
Unless one uses smarter ways of searching an array that is known to be
sorted by virtue of its construction method, i.e. binary search for the
appropriate location. Then finding the "right" spot for the insert
operation is indeed log2(k), where 'k' is the current array size.
Ben Pfaff
> 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)
There are papers that compare the performance of priority queue
implementations. Have you read them?
--
Ben Pfaff
http://benpfaff.org
Keith Thompson
> arnuld <sun...@invalid.address> writes:
[...]
>> 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.
Finding out where to do the insertion can be done by a binary search,
and is O(log N). Actually doing the insertion requires, on average,
shifting half the existing elements, which is O(N).
But I do question the 1 for "Delete". Deleting an arbitrary element
is O(N). The table, as arnuld posted it, has the same values for
"Del Max" and "Delete" for all 5 methods. arnuld, are you sure
you transcribed it correctly?
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
user923005
> Ben Bacarisse <ben.use...@bsb.me.uk> writes:
> > arnuld <sunr...@invalid.address> writes:
> [...]
> >> 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.
>
> [...]
>
> Finding out where to do the insertion can be done by a binary search,
> and is O(log N). Actually doing the insertion requires, on average,
> shifting half the existing elements, which is O(N).
>
> But I do question the 1 for "Delete". Deleting an arbitrary element
> is O(N). The table, as arnuld posted it, has the same values for
> "Del Max" and "Delete" for all 5 methods. arnuld, are you sure
> you transcribed it correctly?
He did not, I have it here in front of me (3rd edition, page 367).
Ordered Array: Insert=N, DeleteMax=1, Delete=N, FindMax=1,
ChangePriority=N, Join=N
For Binomial queue, all operations are log(N)
Optimal: Insert=1, DeleteMax=log(N), Delete=log(N), FindMax=1,
ChangePriority=1, Join=1
Phil Carmody
>> On Oct 15, 2:31 pm, user923005 <dcor...@connx.com> wrote:
>>> On Oct 15, 2:29 am, arnuld <sunr...@invalid.address> wrote:
>>> You mean a doubly linked list ?
>
>> No, he means an array
>
> An array of structures ?
Or an array of pointers.
> Will it be as efficient as a double linked list ?
As efficient at doing _what_? You really need to learn to ask
meaningful questions, or you'll never learn anything.
> 2nd I don't know the number of elements in advance,
But you do after you've build a binary search tree. Which is
what you're claiming you want to do before you create the heap.
> 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.
Put the elements into the tree in order - what shape does your
tree have? How many comparisons were performed? Compare that to a
heap.
Phil Carmody
> arnuld <sun...@invalid.address> writes:
>
>>> On Thu, 15 Oct 2009 11:25:24 +0300, Phil Carmody wrote:
>>
>>> 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.
>
> 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)
No it's not. That's why one self-balances, as if you don't you can
end up with a linked list and Theta(n).
Phil Carmody
Well, that's wrong. Delete is O(N).
> Unordered array: 1 N N N
> Ordered list: N 1 1 1
That's wrong too, delete again is O(N), as it requires finding the element.
> Unordered list: 1 N N N
And if the finding of the element isn't part of the delete, then that's
wrong for the opposite reason.
> heap: LogN LogN 1 LogN
>
> So I thought with the requirements I mentioned Heap fits good.
Given your 5 points above, heap is perfect. Due to the perference
for contiguous memory in implementing heaps, a heap of pointers probably
makes most sense, which can be realloc()ed as needed.
Ben Bacarisse
Quite right. I should have said O(log n) "at beast" (when the insert
is a re-balancing insert). However, the reason this distinction does
not matter is that even the best implementation of a BST is not good
enough for his argument. He has seen the argument that, when
inserting a bunch of item into a heap, it is more efficient to insert
them all and the "heapify" the tree; but this is true only when insert
is O(1). The advantage of the usual array implementation is that
insert if O(1) and it maintains the shape part of the heap property
for free.
--
Ben.
arnuld
If I Google for "priority queue I get 62,800 hits. Same way, if you
search for C programming notes you get 2,380,000 hits, first one being C-
FAQ home page of Steve Summit. Now how can I trust all those notes:
Answer is I do *not*.
My colleagues and friends learn both C from these Google searches and
they hate CLC, I learn from CLC, CLC is the only place I trust, if I get
a link or recommendations from my friends I search the archives of CLC
and see what are the reviews. Everyone knows here that what kind of
teaching is done in those online materials.
I am not a master of either C or Algorithms, so I can not select which
articles to read and which ones not to. Some regular poster do post some
links and I do read them most of the time.
arnuld
> Quite right. I should have said O(log n) "at beast" (when the insert is
> a re-balancing insert). However, the reason this distinction does not
> matter is that even the best implementation of a BST is not good enough
> for his argument. He has seen the argument that, when inserting a bunch
> of item into a heap, it is more efficient to insert them all and the
> "heapify" the tree; but this is true only when insert is O(1). The
> advantage of the usual array implementation is that insert if O(1) and
> it maintains the shape part of the heap property for free.
Okay, since you have emphasized an array implementation, I will give it a
try. Actually, I had felt a lot of difficulty understanding a heap built
into an array, where first element is the root and 2nd and 3rd elements
of the array are its children and then 4th and 5th elements are the
children of left child of the root (Sedgewick section 9.2, page 369). For
me, an array is just a collection of elements. I will try to understand
how to build a Binary Heap into a array.
Ben Pfaff
>> On Thu, 15 Oct 2009 09:19:05 -0700, Ben Pfaff wrote:
>> There are papers that compare the performance of priority queue
>> implementations. Have you read them?
>
> If I Google for "priority queue I get 62,800 hits. Same way, if you
> search for C programming notes you get 2,380,000 hits, first one being C-
> FAQ home page of Steve Summit. Now how can I trust all those notes:
> Answer is I do *not*.
Here's one paper that looks worthwhile:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8515
I've seen others, too.
--
"Programmers have the right to be ignorant of many details of your code
and still make reasonable changes."
--Kernighan and Plauger, _Software Tools_
Richard Heathfield
<snip>
> Same way, if you
> search for C programming notes you get 2,380,000 hits, first one
> being C- FAQ home page of Steve Summit. Now how can I trust all
> those notes: Answer is I do *not*.
>
> My colleagues and friends learn both C from these Google searches
> and they hate CLC, I learn from CLC, CLC is the only place I trust,
If you trust CLC, and CLC trusts Steve Summit's FAQ, it is not
unreasonable for you to trust Steve Summit's FAQ.
<snip>
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
arnuld
> In <pan.2009.10...@invalid.address>, arnuld wrote:
>
> <snip>
>
>> Same way, if you
>> search for C programming notes you get 2,380,000 hits, first one being
>> C- FAQ home page of Steve Summit. Now how can I trust all those notes:
>> Answer is I do *not*.
>>
>> My colleagues and friends learn both C from these Google searches and
>> they hate CLC, I learn from CLC, CLC is the only place I trust,
> If you trust CLC, and CLC trusts Steve Summit's FAQ, it is not
> unreasonable for you to trust Steve Summit's FAQ.
Oh.. holy cow.... that is not what I meant, I should have been more
clear. Here is the complete sentence:
Same way, if you search for C programming notes you get 2,380,000 hits,
first one being C- FAQ home page of Steve Summit, which is the only place
I think has "right things about C". Now how can I trust all that other
material: Answer is I do *not*.
C FAQs are the primary place I refer to my friends whenever they have a
question and its already answered in FAQs e.g. Arrays and Pointers are
same, why not cast malloc() etc. Its a different case they don't read it
and if they do, 50% of the times they are not satisfied. Like last month
when I referred my friend to not to cast to malloc() and read FAQ and
firts reaction after reading was "I will never forget including stdlib.h,
who forgets including stdlib.h"