Array based Binary Heap in C

After discussing in my other thread titled "A C implementation of Binary
Heap", I have done this attempt of coding and came with this code makes a
proper Binary Heap inside the array without any problems so far.

I am posting the code for verification of my assumptions and of course as
usual for any advice on improvements. Does anyone see a hidden bug inside
the program before I go on extending it to completion. Any advice will be
appreciated

If array has five elements then this should be the Binary-Heap, correct
me if I am wrong:

P5
/ \
P4 P3
/ \
P2 P1

(section 9.2, Algorithms in C - Robert Sedgewick)


NOTE: one strange thing though, I am using -ansi flgg rather than -
std=c99 with gcc but then why it does not report any warning/error if I
am using __func__ , a C99 facility, not present in C90


/* A simple implementation of Priority Queue using a heap-based array. We
will be using it for 3 operations:
*
* (1) Insert an element with some priority in the PQ. No duplicate
elements.
* (2) Delete the element with highest priority.
* (3) find the element with highest priority.
*
*
* VERSION 0.0
*
*/




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


/* we are going to use an array of pointers, a pointer takes 4 bytes, so
using an array of 100,000 elements = 400 KB, which is an amount
of memory too small to be concerned about when we 64 MB of RAM at our
disposal. 10,000 is the minimum number of elements we will
be needing. In an average case we will need to use 100,000 elements,
hence the number of element in the array */
enum { SIZE_ARR = 100000 };


enum { SIZE_PRIO = 20,
SIZE_GRADE = 20
};


enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


struct pq_element
{
char priority[SIZE_PRIO];
char grade[SIZE_GRADE];
};


struct pq_element* PQ_arr[SIZE_ARR] = {0};
static long int N = -1;


struct pq_element* PQ_create_element(char [], char []);
void PQ_insert(struct pq_element* );


void PQ_remove(struct pq_element* [], long, long);
void PQ_heapify_up(long int );

enum BOOL PQ_element_exists(struct pq_element* );
enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
void PQ_swap_elements(struct pq_element**, struct pq_element** );

void PQ_print(struct pq_element** );
void PQ_print_single_element(struct pq_element* );

int main(void)
{
struct pq_element* a1 = PQ_create_element("P1", "G-Average");
struct pq_element* a2 = PQ_create_element("P2", "G-First");
struct pq_element* a3 = PQ_create_element("P3", "G-First");
struct pq_element* a4 = PQ_create_element("P4", "G-First");
struct pq_element* a5 = PQ_create_element("P5", "G-First");


if(NULL == a1)
{
fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
}


PQ_insert(a1);
PQ_insert(a2);
PQ_insert(a3);
PQ_insert(a4);
PQ_insert(a5);
PQ_insert(a1);

PQ_print(PQ_arr);

return 0;
}



struct pq_element* PQ_create_element(char prio[], char grd[])
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
strcpy(p->priority, prio);
strcpy(p->grade, grd);
}

return p;
}


void PQ_insert(struct pq_element* p)
{
if(NULL == p)
{
printf("IN: %s, Can not add NULL element to PQ\n", __func__);
return;
}

if(PQ_element_exists(p))
{
/* printf("IN: %s:, An element with same priority is already
present in the queue\n", __func__); */
return;
}


PQ_arr[++N] = p;
PQ_heapify_up(N);
}




enum BOOL PQ_element_exists(struct pq_element* p)
{
int i;
struct pq_element* c;

for(i = 0; i <= N; ++i)
{
c = PQ_arr[i];

if(0 == strcmp(c->priority, p->priority))
{
return YES;
}
}

return NO;
}




void PQ_heapify_up(long int n)
{
for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
{
PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
}
}


/* chekc if first argument has lesser priority than second */
enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
{
int comp;

/*
printf("going to compare, N = %ld\n", N);
printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
*/

if( (comp = strcmp( b1->priority, b2->priority)) < 0 )
{
/* printf("comp YES\n\n"); */
return YES;
}

/* printf("comp NO\n\n"); */
return NO;
}


void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
{
struct pq_element* temp = *p;
*p = *q;
*q = temp;
}




void PQ_print(struct pq_element** p)
{
for( ; p && *p; ++p)
{
PQ_print_single_element(*p);
}
}




void PQ_print_single_element(struct pq_element* p)
{
if(p)
{
printf("priority: %s\n", p->priority);
printf("grade: %s\n\n", p->grade);
}
}


======================== OUTPUT ===========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ-array.c
[arnuld@dune programs]$ ./a.out
priority: P5
grade: G-First

priority: P4
grade: G-First

priority: P3
grade: G-First

priority: P2
grade: G-First

priority: P1
grade: G-Average

[arnuld@dune programs]$







--
www.lispmachine.wordpress.com
my email is @ the above blog.

arnuld

arnuld <> writes:
> After discussing in my other thread titled "A C implementation of Binary
> Heap", I have done this attempt of coding and came with this code makes a
> proper Binary Heap inside the array without any problems so far.
>
> I am posting the code for verification of my assumptions and of course as
> usual for any advice on improvements. Does anyone see a hidden bug inside
> the program before I go on extending it to completion. Any advice will be
> appreciated
>
> If array has five elements then this should be the Binary-Heap, correct
> me if I am wrong:
>
> P5
> / \
> P4 P3
> / \
> P2 P1

Assuming the digits imply order, that indeed is a binary heap.

> (section 9.2, Algorithms in C - Robert Sedgewick)
>
>
> NOTE: one strange thing though, I am using -ansi flgg rather than -
> std=c99 with gcc but then why it does not report any warning/error if I
> am using __func__ , a C99 facility, not present in C90
>
>
> /* A simple implementation of Priority Queue using a heap-based array. We
> will be using it for 3 operations:
> *
> * (1) Insert an element with some priority in the PQ. No duplicate
> elements.
> * (2) Delete the element with highest priority.
> * (3) find the element with highest priority.
> *
> *
> * VERSION 0.0
> *
> */
>
>
>
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
>
> /* we are going to use an array of pointers, a pointer takes 4 bytes, so
> using an array of 100,000 elements = 400 KB, which is an amount
> of memory too small to be concerned about when we 64 MB of RAM at our
> disposal. 10,000 is the minimum number of elements we will
> be needing. In an average case we will need to use 100,000 elements,
> hence the number of element in the array */
> enum { SIZE_ARR = 100000 };
>
>
> enum { SIZE_PRIO = 20,
> SIZE_GRADE = 20
> };
>
>
> enum BOOL { NO = 0,
> YES = 1,
> VAL_FAIL = NO,
> VAL_SUCC = YES};
>
>
> struct pq_element
> {
> char priority[SIZE_PRIO];
> char grade[SIZE_GRADE];
> };
>
> struct pq_element* PQ_arr[SIZE_ARR] = {0};
> static long int N = -1;

Beware!!!!!
Heaps indexed from [1] upwards are far easier to deal with, IMHO.
I bet that there are indexing issues later....

> struct pq_element* PQ_create_element(char [], char []);
> void PQ_insert(struct pq_element* );
>
>
> void PQ_remove(struct pq_element* [], long, long);
> void PQ_heapify_up(long int );
>
> enum BOOL PQ_element_exists(struct pq_element* );
> enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
> void PQ_swap_elements(struct pq_element**, struct pq_element** );
>
> void PQ_print(struct pq_element** );
> void PQ_print_single_element(struct pq_element* );
>
> int main(void)
> {
> struct pq_element* a1 = PQ_create_element("P1", "G-Average");
> struct pq_element* a2 = PQ_create_element("P2", "G-First");
> struct pq_element* a3 = PQ_create_element("P3", "G-First");
> struct pq_element* a4 = PQ_create_element("P4", "G-First");
> struct pq_element* a5 = PQ_create_element("P5", "G-First");
>
>
> if(NULL == a1)

In theory they could all succeed or fail intependently of each other.

> {
> fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
> }
>
>
> PQ_insert(a1);
> PQ_insert(a2);
> PQ_insert(a3);
> PQ_insert(a4);
> PQ_insert(a5);

OK, you've got all 5 elements in your structure, if those functions are
correct.

> PQ_insert(a1);

From reading below, I see that this is to check error conditions.

To check error conditions, you want to test a whole load of examples,
not just one. Randomise the values.

> PQ_print(PQ_arr);
>
> return 0;
> }
>
>
>
> struct pq_element* PQ_create_element(char prio[], char grd[])
> {
> struct pq_element* p = malloc(1 * sizeof*p);
>
> if(p)
> {
> strcpy(p->priority, prio);
> strcpy(p->grade, grd);

Beware untrusted callers - they may give you long strings that you
hang yourself with. Find or write a 'strlcpy' for such purposes.

> }
>
> return p;
> }
>
>
> void PQ_insert(struct pq_element* p)

I notice you're assuming only one heap exists, rather than
passing a pointer to it and its size as a parameter. The latter
would be more re-usable.

> {
> if(NULL == p)
> {
> printf("IN: %s, Can not add NULL element to PQ\n", __func__);
> return;
> }

If you trust your callers to obey a no-NULL interface, then you
could convert that to an assert. But if you don't trust your callers,
that can stay.

> if(PQ_element_exists(p))
> {
> /* printf("IN: %s:, An element with same priority is already
> present in the queue\n", __func__); */
> return;
> }
>
> PQ_arr[++N] = p;
> PQ_heapify_up(N);
> }

Looks OK from here.

> enum BOOL PQ_element_exists(struct pq_element* p)
> {
> int i;
> struct pq_element* c;
>
> for(i = 0; i <= N; ++i)
> {
> c = PQ_arr[i];
> if(0 == strcmp(c->priority, p->priority))
> {
> return YES;

So priority is your unique key? That's OK.

> }
> }
>
> return NO;
> }

A rather expensive operation, but while developing and debugging
it can be useful to have expensive sanity checks.

A good sanity check is one that verifies the heap condition. Implement
one, and verify that every time you add an element it still satisfies
the heap condition.

> void PQ_heapify_up(long int n)
> {
> for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )

You don't want to be comparing PQ_arr[0] with PQ_arr[0].
You want to be comparing [1] with [0], and later, you want
to be comparing [2] with [0]. However, you'll be comparing
[2] with [1].

That's the indexing issue I mentioned above.

> {
> PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
> }
> }
>
>
> /* chekc if first argument has lesser priority than second */
> enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
> {
> int comp;
>
> /*
> printf("going to compare, N = %ld\n", N);
> printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
> printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
> */
>
> if( (comp = strcmp( b1->priority, b2->priority)) < 0 )
> {
> /* printf("comp YES\n\n"); */
> return YES;
> }
>
> /* printf("comp NO\n\n"); */
> return NO;
> }

Seems OK.

> void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
> {
> struct pq_element* temp = *p;
> *p = *q;
> *q = temp;
> }

Yup.

> void PQ_print(struct pq_element** p)
> {
> for( ; p && *p; ++p)

You could run off the end of the array and not know it. You have
N for a reason - use it.

> {
> PQ_print_single_element(*p);
> }
> }
>
> void PQ_print_single_element(struct pq_element* p)
> {
> if(p)
> {
> printf("priority: %s\n", p->priority);
> printf("grade: %s\n\n", p->grade);
> }
> }
>
>
> ======================== OUTPUT ===========================
> [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ-array.c
> [arnuld@dune programs]$ ./a.out
> priority: P5
> grade: G-First
>
> priority: P4
> grade: G-First
>
> priority: P3
> grade: G-First
>
> priority: P2
> grade: G-First
>
> priority: P1
> grade: G-Average
>
> [arnuld@dune programs]$

Given the indexing issues, I'd say that's luck. However, you're
close, so should be able to hone in on a correct implementation
pretty soon.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody

> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:

>> arnuld <> writes:
>> struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;

> Beware!!!!!
> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
> that there are indexing issues later....

If I start from [1] then n/2 and n in PQ_heapify_up() no longer apply.
IMHO, I felt lot of difficulty in finding a proper way n/2, n/3, n-1, n-2
etc but none works.


BTW, if n/2 and n no longer apply then it will not be binary heap (as per
definition)




>> void PQ_insert(struct pq_element* p)
>
> I notice you're assuming only one heap exists, rather than passing a
> pointer to it and its size as a parameter. The latter would be more
> re-usable.


Its actually because of the part of the software I am working on where
the PQ is available at a global level.




> So priority is your unique key? That's OK.

yes, and that makes insertions N + N, N for lookup and another N for
insert, so Sedewick's worst case does not fit in here (Algorithms n C -
section 9.1)


> A good sanity check is one that verifies the heap condition. Implement
> one, and verify that every time you add an element it still satisfies
> the heap condition.

What do you mean a /verifying the heap condition/ . PQ_heapify_up()
already does this for insertion. Later, PQ_heapify_down() will do this
for deletion. What else if left ?




>> void PQ_heapify_up(long int n)
>> {
>> for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
>
> You don't want to be comparing PQ_arr[0] with PQ_arr[0]. You want to be
> comparing [1] with [0], and later, you want to be comparing [2] with
> [0]. However, you'll be comparing [2] with [1].

> That's the indexing issue I mentioned above.


for n = 0 the comparison is between 0,0
for n = 1 the comparison is between 0,1
for n = 2 the comparison is between 1,2
for n = 3 the comparison is between 1,3
for n = 4 the comparison is between 2,4
for n = 5 the comparison is between 2,5

You are right that for n=2, it should compare with 0, not 1 but then I
have to change that n/2 and n and it will break the requirement for
Binary Heap. See:


http://mathworld.wolfram.com/Heap.html

Also, Section 9.2, Algorithms in C , Sedgewick









> Given the indexing issues, I'd say that's luck.

You mean the program is buggy and will not make binary heap every time ?





--
www.lispmachine.wordpress.com
my email is @ the above blog.

arnuld

> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:


> Beware!!!!!
> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
> that there are indexing issues later....


How about this implementation:


/* A simple implementation of Priority Queue using a heap-based array. We
will be using it for 3 operations:
*
* (1) Insert an element with some priority in the PQ. No duplicate
elements.
* (2) Delete the element with highest priority.
* (3) find the element with highest priority.
*
*
* VERSION 0.1
*
*/




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


/* we are going to use an array of pointers, a pointer takes 4 bytes, so
using an array of 100,000 elements = 400 KB, which is an amount
of memory too small to be concerned about when we 64 MB of RAM at our
disposal. 10,000 is the minimum number of elements we will
be needing. In an average case we will need to use 100,000 elements,
hence the number of element in the array */
enum { SIZE_ARR = 100000 };


enum { SIZE_GRADE = 20 };


enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


struct pq_element
{
long int priority;
char grade[SIZE_GRADE];
};


struct pq_element* PQ_arr[SIZE_ARR] = {0};
static long int N = 1;


struct pq_element* PQ_create_element(long int, char []);
void PQ_insert(struct pq_element* );


void PQ_remove(struct pq_element* [], long, long);
void PQ_heapify_up(long int );

enum BOOL PQ_element_exists(struct pq_element* );
enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
void PQ_swap_elements(struct pq_element**, struct pq_element** );

void PQ_print(struct pq_element**, long int );
void PQ_print_single_element(struct pq_element* );

int main(void)
{
struct pq_element* a1 = PQ_create_element(1, "G-Average");
struct pq_element* a2 = PQ_create_element(2, "G-First");
struct pq_element* a3 = PQ_create_element(3, "G-First");
struct pq_element* a4 = PQ_create_element(4, "G-First");
struct pq_element* a5 = PQ_create_element(5, "G-First");
struct pq_element* a6 = PQ_create_element(6, "G-First");
struct pq_element* a21 = PQ_create_element(21, "G-First");
struct pq_element* a20 = PQ_create_element(20, "G-First");

if(NULL == a1)
{
fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
}


PQ_insert(a2);
PQ_insert(a20);
PQ_insert(a1);
PQ_insert(a4);
PQ_insert(a3);
PQ_insert(a21);
PQ_insert(a6);
PQ_insert(a5);
PQ_insert(a21);
PQ_insert(a21);

PQ_print(PQ_arr, N);

return 0;
}



struct pq_element* PQ_create_element(long int d, char grd[])
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
strcpy(p->grade, grd);
}

return p;
}


/* Total instertion time will be N + N = 2N, N for instertion, N for
duplicacy check */
void PQ_insert(struct pq_element* p)
{
if(NULL == p)
{
printf("IN: %s, Can not add NULL element to PQ\n", __func__);
return;
}

if(PQ_element_exists(p))
{
/* printf("IN: %s:, An element with same priority is already
present in the queue\n", __func__); */
return;
}


PQ_arr[N] = p;
PQ_heapify_up(N++);
}




/* This is log(N) */
enum BOOL PQ_element_exists(struct pq_element* p)
{
int i;
struct pq_element* c;

for(i = 1; i <= N; ++i)
{
c = PQ_arr[i];

if( c && (c->priority == p->priority))
{
printf("element_EXISTS YES\n");
return YES;
}
}


printf("element_EXISTS NO\n");
return NO;
}




void PQ_heapify_up(long int n)
{
for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
{
PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
}
}


/* chekc if first argument has lesser priority than second */
enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
{
/*
printf("going to compare, N = %ld\n", N);
printf("b1->priority: %s\nb1->grade: %s\n", b1->priority, b1->grade);
printf("b2->priority: %s\nb2->grade: %s\n", b2->priority, b2->grade);
*/

if((b1->priority < b2->priority))
{
/* printf("comp YES\n\n"); */
return YES;
}

/* printf("comp NO\n\n"); */
return NO;
}


void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
{
struct pq_element* temp = *p;
*p = *q;
*q = temp;
}




/* ---------------------------- General Printing Functions
-------------------------------- */
void PQ_print(struct pq_element** p, long int n)
{
for(int i=0; i <= n; ++i)
{
PQ_print_single_element(p[i]);
}
}


void PQ_print_single_element(struct pq_element* p)
{
if(p) printf("%ld --> %s \n", p->priority, p->grade);
}


====================== OUTPUT =================================
[arnuld@dune programs]$ gcc -std=c99 -pedantic -Wall -Wextra PQ-array.c
[arnuld@dune programs]$ ./a.out
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS NO
element_EXISTS YES
element_EXISTS YES
21 --> G-First
5 --> G-First
20 --> G-First
4 --> G-First
3 --> G-First
1 --> G-Average
6 --> G-First
2 --> G-First
[arnuld@dune programs]$




--
www.lispmachine.wordpress.com
my email is @ the above blog.

arnuld

Full fledged version of Array based Binary Heap. Any suggestions ?




/* A simple implementation of Priority Queue using a heap-based array. We
will be using it for 3 operations:
*
* (1) Insert an element with some priority in the PQ. No duplicate
elements.
* (2) Delete the element with highest priority.
* (3) find the element with highest priority.
*
*
* VERSION 0.2
*
*/




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


/* we are going to use an array of pointers, a pointer takes 4 bytes, so
using an array of 100,000 elements = 400 KB, which is an amount
of memory too small to be concerned about when we 64 MB of RAM at our
disposal. 10,000 is the minimum number of elements we will
be needing. In an average case we will need to use 100,000 elements,
hence the number of element in the array */
enum { SIZE_ARR = 100000,
SIZE_GRADE = 20 };

enum { POSITION_MAX = 1 };

enum BOOL { NO = 0,
YES = 1,
VAL_FAIL = NO,
VAL_SUCC = YES};


struct pq_element
{
long int priority;
char grade[SIZE_GRADE];
};


struct pq_element* PQ_arr[SIZE_ARR] = {0};
static long int N = 0;


struct pq_element* PQ_create_element(long int, char []);
void PQ_insert(struct pq_element* );



void PQ_heapify_up(long int );
struct pq_element* PQ_find_max(struct pq_element** );
void PQ_heapify_down(long int nd);
void PQ_remove_max(void);
void PQ_remove(long int);


enum BOOL PQ_element_exists(struct pq_element* );
enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
void PQ_swap_elements(struct pq_element**, struct pq_element** );
void PQ_free_single_element(struct pq_element** );

void PQ_print(struct pq_element**, long int );
void PQ_print_single_element(struct pq_element* );


int main(void)
{
struct pq_element* a1 = PQ_create_element(1, "G-Average");
struct pq_element* a2 = PQ_create_element(2, "G-First");
struct pq_element* a3 = PQ_create_element(3, "G-First");
struct pq_element* a4 = PQ_create_element(4, "G-First");
struct pq_element* a5 = PQ_create_element(5, "G-First");
struct pq_element* a6 = PQ_create_element(6, "G-First");
struct pq_element* a21 = PQ_create_element(21, "G-First");
struct pq_element* a20 = PQ_create_element(20, "G-First");


PQ_insert(a2);
PQ_insert(a20);
PQ_insert(a1);
PQ_insert(a4);

PQ_insert(a3);
PQ_insert(a21);

PQ_insert(a6);
PQ_insert(a5);
PQ_insert(a21);
PQ_insert(a21);


PQ_print(PQ_arr, N);
PQ_remove_max();
printf("\n\n --------------- Array after MAX removed ------------------
\n\n");
PQ_print(PQ_arr, N);


return 0;
}



struct pq_element* PQ_create_element(long int d, char grd[])
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
strcpy(p->grade, grd);
}

return p;
}


/* Total instertion time will be N + N = 2N, N for instertion, N for
duplicacy check */
void PQ_insert(struct pq_element* p)
{
if(NULL == p)
{
return;
}

if(PQ_element_exists(p))
{
return;
}


PQ_arr[++N] = p;
PQ_heapify_up(N);
}



/* (1) Swap the last element of the right subtree with the element with
max priority (root)
(2) delete the root
(3) heapify-down the new root till we get a heap ordered tree.

Requires 2N comparisons in worst case.
*/
void PQ_remove_max(void)
{
PQ_remove(POSITION_MAX);
}

void PQ_remove(long int pos)
{
if(N > 0 )
{
PQ_swap_elements(&PQ_arr[pos], &PQ_arr[N]);

PQ_free_single_element(&PQ_arr[N]);
PQ_arr[N--] = NULL;

PQ_heapify_down(pos);
}
}


void PQ_heapify_up(long int n)
{
for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
{
PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
}
}



void PQ_heapify_down(long int nd)
{
long node_left, node_right, node_comp;

node_left = 2 * nd;
node_right = (2 * nd) + 1;

while(node_left <= N)
{
node_left = 2 * nd;
node_right = (2 * nd) + 1;


if( node_left < N && PQ_comp_less(PQ_arr[node_left], PQ_arr
[node_right]))
{
node_comp = node_right;
}
else
{
node_comp = node_left;
}


if( YES == PQ_comp_less(PQ_arr[node_comp], PQ_arr[nd]) )
{
break;
}

PQ_swap_elements(&PQ_arr[node_comp], &PQ_arr[nd]);
nd = node_comp;
}
}





struct pq_element* PQ_find_max(struct pq_element** arr)
{
if(arr)
{
return arr[POSITION_MAX];
}

return NULL;
}


/* ------------------ Small Helper Functions ------------------------ */

/* This is log(N) */
enum BOOL PQ_element_exists(struct pq_element* p)
{
int i;
struct pq_element* c;

for(i = 1; i <= N; ++i)
{
c = PQ_arr[i];

if( c && (c->priority == p->priority))
{
return YES;
}
}

return NO;
}



/* chekc if first argument has lesser priority than second */
enum BOOL PQ_comp_less(struct pq_element* b1, struct pq_element* b2)
{
if((NULL == b1) || (NULL == b2))
{
return YES;
}


if((b1->priority < b2->priority))
{
return YES;
}

return NO;
}


void PQ_swap_elements(struct pq_element** p, struct pq_element** q)
{
struct pq_element* temp = *p;
*p = *q;
*q = temp;
}


void PQ_free_single_element(struct pq_element** p)
{
free(*p);
*p = NULL;
}


/* ---------------------------- General Printing Functions
-------------------------------- */
void PQ_print(struct pq_element** p, long int n)
{
int i;

printf("N = %ld\n", n);
for(i = 0; i <= n; ++i)
{
PQ_print_single_element(p[i]);
}

printf("+++++++\n\n");
}


void PQ_print_single_element(struct pq_element* p)
{
if(p) printf("%ld --> %s \n", p->priority, p->grade);
}


===================== OUTPUT ============================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra PQ.c
[arnuld@dune programs]$ ./a.out
N = 8
21 --> G-First
5 --> G-First
20 --> G-First
4 --> G-First
3 --> G-First
1 --> G-Average
6 --> G-First
2 --> G-First
+++++++



--------------- Array after MAX removed ------------------

N = 7
20 --> G-First
5 --> G-First
6 --> G-First
4 --> G-First
3 --> G-First
1 --> G-Average
2 --> G-First
+++++++

[arnuld@dune programs]$



--
www.lispmachine.wordpress.com
my email is @ the above blog.

arnuld

arnuld <> writes:
>> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:
>
>>> arnuld <> writes:
>>> struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;
>
>> Beware!!!!!
>> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
>> that there are indexing issues later....
>
> If I start from [1] then n/2 and n in PQ_heapify_up() no longer apply.

Wrong. Try again. Aim for correctness this time.

> IMHO, I felt lot of difficulty in finding a proper way n/2, n/3, n-1, n-2
> etc but none works.

Did you try my previous suggestion?

> BTW, if n/2 and n no longer apply then it will not be binary heap (as per
> definition)

Wrong. You are confusing the indexes in an array and the indexes within
the heap. The fact that you are confused is because you have ignored
the advice which I gave which reduces the amount of confusion. If you
prefer confusing yourself, just say so, and I'll not waste time trying
to help you any more, it's no skin off my nose.

>> A good sanity check is one that verifies the heap condition. Implement
>> one, and verify that every time you add an element it still satisfies
>> the heap condition.
>
> What do you mean a /verifying the heap condition/ .

Checking that the heap condition holds for all nodes in the heap.

> PQ_heapify_up()
> already does this for insertion. Later, PQ_heapify_down() will do this
> for deletion. What else if left ?

They don't check the whole heap. They only modify (and break currently)
a subset of the tree.

>>> void PQ_heapify_up(long int n)
>>> {
>>> for( ; (n >= 0) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )
>>
>> You don't want to be comparing PQ_arr[0] with PQ_arr[0]. You want to be
>> comparing [1] with [0], and later, you want to be comparing [2] with
>> [0]. However, you'll be comparing [2] with [1].
>
>> That's the indexing issue I mentioned above.
>
>
> for n = 0 the comparison is between 0,0

which is pointless

> for n = 1 the comparison is between 0,1

which is correct

> for n = 2 the comparison is between 1,2

which is wrong

> for n = 3 the comparison is between 1,3

which is correct

> for n = 4 the comparison is between 2,4

which is wrong

> for n = 5 the comparison is between 2,5

which is correct

> You are right that for n=2, it should compare with 0, not 1 but then I
> have to change that n/2 and n and it will break the requirement for
> Binary Heap.

Wrong. Not if you do it correctly. That's the bit *you* are failing
to do currently, not me.

> See:

I don't need references, I can already do this with my eyes closed.

>> Given the indexing issues, I'd say that's luck.
>
> You mean the program is buggy and will not make binary heap every time ?

Yes.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody

arnuld <> writes:
>> On Wed, 28 Oct 2009 22:49:52 +0200, Phil Carmody wrote:
>
>
>> Beware!!!!!
>> Heaps indexed from [1] upwards are far easier to deal with, IMHO. I bet
>> that there are indexing issues later....
>
>
> How about this implementation:

> static long int N = 1;

> /* Total instertion time will be N + N = 2N, N for instertion, N for
> duplicacy check */

It's not necessary to have uniquely keyed elements in a heap,
so you don't need the uniqueness test in order to be a heap.
And insertion's not N operations, it's O(lg(N)) operations.

> void PQ_insert(struct pq_element* p)
> {
> if(NULL == p)
> {
> printf("IN: %s, Can not add NULL element to PQ\n", __func__);
> return;
> }
>
> if(PQ_element_exists(p))
> {
> /* printf("IN: %s:, An element with same priority is already
> present in the queue\n", __func__); */
> return;
> }
>
>
> PQ_arr[N] = p;

So the first insertion goes into slot [1], good.

> PQ_heapify_up(N++);

I prefer to keep the side-effects on global variables out of the
function calls, for readability. (The function called might depend
on that global variable, and the "post-"increment is actually done
before the function call, not after it.

However, subsequent items will be temprorarily placed in [2], [3], ...
good.

> }
>
> void PQ_heapify_up(long int n)

Here n = N-1, and represents the actual number of elements in the
heap.

> {
> for( ; (n > 1) && PQ_comp_less(PQ_arr[n/2], PQ_arr[n]); n = n/2 )

Looks good.

> {
> PQ_swap_elements(&PQ_arr[n/2], &PQ_arr[n]);
> }
> }

> ====================== OUTPUT =================================
> [arnuld@dune programs]$ gcc -std=c99 -pedantic -Wall -Wextra PQ-array.c
> [arnuld@dune programs]$ ./a.out
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS NO
> element_EXISTS YES
> element_EXISTS YES
> 21 --> G-First
> 5 --> G-First
> 20 --> G-First
> 4 --> G-First
> 3 --> G-First
> 1 --> G-Average
> 6 --> G-First
> 2 --> G-First
> [arnuld@dune programs]$

Which looks like a heap. Congratulations.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody

arnuld <> writes:
> Full fledged version of Array based Binary Heap. Any suggestions ?

> static long int N = 0;

> PQ_arr[++N] = p;
> PQ_heapify_up(N);

Not read the rest, but that's much better maintainability-wise.

Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1

Phil Carmody

On Oct 28, 1:49*pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk>
wrote:
> arnuld <sunr...@invalid.address> writes:
> > After discussing in my other thread titled "A C implementation of Binary
> > Heap", I have done this attempt of coding and came with this code makes a
> > proper Binary Heap inside the array without any problems so far.
>
> > I am posting the code for verification of my assumptions and of course as
> > usual for any advice on improvements. Does anyone see a hidden bug inside
> > the program before I go on extending it to completion. Any advice will be
> > appreciated *
>
> > If array has five elements then this should be the Binary-Heap, correct
> > me if I am wrong:
>
> > * * * * * * *P5
> > * * * * * */ * *\
> > * * * * * P4 * * P3
> > * * * * / * \
> > * * * * P2 * P1
>
> Assuming the digits imply order, that indeed is a binary heap.
>
>
>
> > (section 9.2, Algorithms in C - Robert Sedgewick)
>
> > NOTE: *one strange thing though, I am using -ansi flgg rather than -
> > std=c99 with gcc but then why it does not report any warning/error if I
> > am using __func__ , a C99 facility, not present in C90
>
> > /* A simple implementation of Priority Queue using a heap-based array. We
> > will be using it for 3 operations:
> > **
> > ** (1) Insert an element with some priority in the PQ. No duplicate
> > elements.
> > ** (2) Delete the element with highest priority.
> > ** (3) find the element with highest priority.
> > **
> > **
> > ** VERSION 0.0
> > **
> > **/
>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
>
> > /* we are going to use an array of pointers, a pointer takes 4 bytes, so
> > using an array of 100,000 elements = 400 KB, which is an amount
> > * *of memory too small to be concerned about when we 64 MB of RAM at our
> > disposal. 10,000 is the minimum number of elements we will
> > * *be needing. In an average case we will need to use 100,000 elements,
> > hence the number of element in the array */
> > enum { SIZE_ARR = 100000 };
>
> > enum { SIZE_PRIO *= 20,
> > * * * *SIZE_GRADE = 20
> > };
>
> > enum BOOL { NO = 0,
> > * * * *YES = 1,
> > * * * *VAL_FAIL = NO,
> > * * * *VAL_SUCC = YES};
>
> > struct pq_element
> > {
> > * char priority[SIZE_PRIO];
> > * char grade[SIZE_GRADE];
> > };
>
> > struct pq_element* PQ_arr[SIZE_ARR] = {0};
> > static long int N = -1;
>
> Beware!!!!!
> Heaps indexed from [1] upwards are far easier to deal with, IMHO.
> I bet that there are indexing issues later....
>
>
>
> > struct pq_element* PQ_create_element(char [], char []);
> > void PQ_insert(struct pq_element* );
>
> > void PQ_remove(struct pq_element* [], long, long);
> > void PQ_heapify_up(long int );
>
> > enum BOOL PQ_element_exists(struct pq_element* );
> > enum BOOL PQ_comp_less(struct pq_element*, struct pq_element*);
> > void PQ_swap_elements(struct pq_element**, struct pq_element** );
>
> > void PQ_print(struct pq_element** );
> > void PQ_print_single_element(struct pq_element* );
>
> > int main(void)
> > {
> > * struct pq_element* a1 = PQ_create_element("P1", "G-Average");
> > * struct pq_element* a2 = PQ_create_element("P2", "G-First");
> > * struct pq_element* a3 = PQ_create_element("P3", "G-First");
> > * struct pq_element* a4 = PQ_create_element("P4", "G-First");
> > * struct pq_element* a5 = PQ_create_element("P5", "G-First");
>
> > * if(NULL == a1)
>
> In theory they could all succeed or fail intependently of each other.
>
> > * * {
> > * * * fprintf(stderr, "IN: %s : Memory Exhausted!\n", __func__);
> > * * }
>
> > * PQ_insert(a1);
> > * PQ_insert(a2);
> > * PQ_insert(a3);
> > * PQ_insert(a4);
> > * PQ_insert(a5);
>
> OK, you've got all 5 elements in your structure, if those functions are
> correct.
>
> > * PQ_insert(a1);
>
> From reading below, I see that this is to check error conditions.
>
> To check error conditions, you want to test a whole load of examples,
> not just one. Randomise the values.
>
> > * PQ_print(PQ_arr);
>
> > * return 0;
> > }
>
> > struct pq_element* PQ_create_element(char prio[], char grd[])
> > {
> > * struct pq_element* p = malloc(1 * sizeof*p);
>
> > * if(p)
> > * * {
> > * * * strcpy(p->priority, prio);
> > * * * strcpy(p->grade, grd);
>
> Beware untrusted callers - they may give you long strings that you
> hang yourself with. Find or write a 'strlcpy' for such purposes.
>

Couldn't he/she/it (by 'it', I mean a man posing as a woman, or a
woman posing as a man) do something like...

(void) strcpy(p->priority, prio);
(void) strcpy(p->grade, grd);

In this case? Just curious, because in some production level code I've
seen programmers do the following..

(void)strncpy(...);

Please note that this is strncpy() and not strcpy().

Chad

> On Fri, 30 Oct 2009 02:05:11 +0200, Phil Carmody wrote:

> It's not necessary to have uniquely keyed elements in a heap, so you
> don't need the uniqueness test in order to be a heap. And insertion's
> not N operations, it's O(lg(N)) operations.


And my Binary-Heap *does* need to have unique keys, If I don't then my
boss will find someone else to do the job.



> They don't check the whole heap. They only modify (and break currently)
> a subset of the tree.

Did you mean Heapsort ?




--
www.lispmachine.wordpress.com
my email is @ the above blog.

arnuld