Array based Binary Heap in C

[arnuld]

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;

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]$

 

[Phil Carmody]

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

 

[arnuld]

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)

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 ?

 

[arnuld]

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;

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


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]$

 

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

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

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]$

 

[Phil Carmody]

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.

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.

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

Yes.

Phil

 

[Phil Carmody]

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

 

[Phil Carmody]

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

 

[Chad]

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().

 

[arnuld]

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 ?

 

[Phil Carmody]

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.

In that case, you've probably chosen the wrong data structure.
Perhaps your boss should find someone else to do the job?

Did you mean Heapsort ?

I meant what I wrote, nothing more, and nothing less.

Phil

 

[user923005]

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.

Why write a heap from scratch? There are zillions of them laying
around, all over the planet. Two minutes with a web search beats 2
days in edit/compile/test any day.

And if you need a priority queue why not just pick up one of the
dozens and dozens of freely available, thoroughly tested priority
queues that are laying around all over the sidewalk?

Did you mean Heapsort ?

Turning a heap into heapsort is trivial. And if you write your own
heapsort, I'm going to be sick, unless it's just for fun or learning
in which case it is fine.

P.S.
Have a look at Lamont's heap.

 

[arnuld]

In that case, you've probably chosen the wrong data structure. Perhaps
your boss should find someone else to do the job?

I was told create a Binary-Heap with unique keys, inserting element with
priority, finding/deleting the element with max priority and I did it
(with CLC's help of course)

I meant what I wrote, nothing more, and nothing less.

That is I did not get, I did not understand what you asked of me to do.

 

[arnuld]

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

...SNIP....


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

What about reallocating the memory when array is full ? (it will be
full).

I can not reassign the array to some another realloc()ed pointer. Does
that mean I must not use array but a pointer ?

 

[user923005]

On Wed, 28 Oct 2009 10:33:44 +0000, arnuld wrote:
struct pq_element* PQ_arr[SIZE_ARR] = {0}; static long int N = -1;

...SNIP....
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);
}

What about reallocating the memory when array is full ?  (it will be
full).

I can not reassign the array to some another realloc()ed pointer. Does
that mean I must not use array but a pointer ?

If you do not know the maximum size at startup, then a fixed length
array is not a good choice.

 

[arnuld]

..SNIP...

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

.....SNIP.....

Since I can not realloc() an array, I am changing the whole program to
use a pointer rather than array, hence starting from scratch again.

 

[Keith Thompson]

..SNIP...

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

.....SNIP.....

Since I can not realloc() an array, I am changing the whole program to
use a pointer rather than array, hence starting from scratch again.

A quibble: If you're doing what i think you're doing, you'll still be
using an array. It will just be an array allocated via malloc and/or
realloc, not one declared as a named array object.

 

[arnuld]

A quibble: If you're doing what i think you're doing, you'll still be
using an array. It will just be an array allocated via malloc and/or
realloc, not one declared as a named array object.

But I will have to replace this call:


struct pq_element* p[];

with

struct pq_element**;


which going to cause trouble to functions like this:


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


Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
address of its element like &PQ_arr[2]. How am I supposed to do that for
a double-pointer: use a triple-level pointer indirection ?

 

[Barry Schwarz]

A quibble: If you're doing what i think you're doing, you'll still be
using an array. It will just be an array allocated via malloc and/or
realloc, not one declared as a named array object.

But I will have to replace this call:


struct pq_element* p[];

with

struct pq_element**;


which going to cause trouble to functions like this:


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


Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
address of its element like &PQ_arr[2]. How am I supposed to do that for
a double-pointer: use a triple-level pointer indirection ?

I can't keep track of the different names you are using and the one
object that has no name. The bottom line is - do not let the slight
difference in syntax confuse you. For sake of an example, lets assume
an object of type struct pq_element* is four bytes with four byte
alignment.

When you define the array p, it is located somewhere in
memory. Let's say 0x12345678. Each element of the array is a pointer
to struct. Element p[0] is located at that address, p[1] is located
at 0x1234567c, etc. The expression &p[1] will evaluate to 0x1234567c
with type pointer to struct pq_element* which is just struct
pq_element**.

If instead you define p as a pointer to pointer to struct and
allocate memory, then p will be assigned the value returned by malloc.
Let's say 0x12345678. The value at that address (denoted by p[0]) has
type struct pq_element* and is therefore four bytes wide.
Consequently, the object denoted by p[1] must be located at 0x1234567c
and is also of type struct pq_element*. The expression &p[1] will
evaluate to 0x1234567c with type struct pq_element**. Note this is
exactly the same as the paragraph above.

Regardless of whether you define the array to hold values or define a
pointer and allocate space to hold values, you refer to the i-th value
as p and you refer to the address of this value as &p.

 

[Ben Bacarisse]

A quibble: If you're doing what i think you're doing, you'll still be
using an array. It will just be an array allocated via malloc and/or
realloc, not one declared as a named array object.

But I will have to replace this call:

struct pq_element* p[];

with

struct pq_element**;

It's not a "call", but yes, you will.

which going to cause trouble to functions like this:


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

Here PQ_arr is an array: struct pq_element* PQ_arr[], I cna take the
address of its element like &PQ_arr[2]. How am I supposed to do that for
a double-pointer: use a triple-level pointer indirection ?

If PQ_arr is of type struct pq_element **, then that code works
unaltered. Now, I think you have a typo because s is undeclared, but
I think you meant PQ_arr[n] rather than s[n].

You are right about the *** simply because a swap function that sawp T
objects must be passed two T* arguments, but you don't have to do it
that way of it bothers you:

void PQ_swap_elements(struct pq_element **arr, size_t i, size_t j)
{
struct pq_element *tmp = arr;
arr = arr[j];
arr[j] = tmp;
}

would also work.

As I suggested in comp.programming, since you need other information
to represent a queue, you should pack it all up in a struct
(preferably using the opaque type trick). This will include the
current capacity and current size. It might also include the
comparison function.