Re: How to choose a Data-Structure for a Priority Queue ?

On Sun, 08 Nov 2009 12:14:10 +0000, Jonathan Campbell wrote:

Ben Bacarisse wrote:
But what BST has O(1) delete (if that is indeed what you are suggesting
above)?
Oops, yes. I was still thinking about the linked list solution that I
suggested in response to an earlier post.


I already implemented a singly linked list solution, it was pretty simple
to create and even seems pretty simple to maintain as compared to a
binary-heap which feels much more complicated. I even wrote a simple unit
test function to test this PQ. I am working on Binary Heap now. Here is
the code for singly linked list based PQ:



/* A Priority Queue (PQ) implemented as singly linked list where elements
are always added according to the priority and the element
* with highest priority is always at the beginning. Removal is done
only by removing the element with highest priority. Priority
* is a /int/.
*
*
* Insertion: O(N) + O(N) in worst case, one for insertion, one for
uniqueness check.
* Find Max: 0(1)
* Deletion: O(1)
*
* VERSION 0.0
*
*/



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



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


enum { SIZE_NAME = 30 };

struct pq_element
{
int priority;
struct pq_element* next;
};

struct pql
{
struct pq_element* head;
struct pq_element* tail;
};



struct pql* PQL_init(void);
struct pq_element* PQL_create_element(int d);


void PQL_insert(struct pql* s, struct pq_element* e);
void PQ_add_element(struct pql* s, struct pq_element* e);
void PQL_remove(struct pql* s);
void PQL_free_single(struct pq_element* e);

void PQL_print(struct pql* s);
void PQL_print_single(struct pq_element* p);
void PQL_unit_test_insertion(struct pql* s);
void PQL_unit_test_removal(struct pql* s);



int main(void)
{
struct pql* pql = PQL_init();

struct pq_element* a1 = PQL_create_element(1);
struct pq_element* a2 = PQL_create_element(2);
struct pq_element* a0 = PQL_create_element(0);
struct pq_element* a6 = PQL_create_element(6);

if(NULL == pql)
{
fprintf(stderr, "IN: %s: malloc() failed\n", __func__);
exit(EXIT_FAILURE);
}
else if(NULL == a1 ||
NULL == a2 ||
NULL == a0 ||
NULL == a6 )
{
fprintf(stderr, "LINE: %d, IN: %s: malloc() failed\n", __LINE__,
__func__);
exit(EXIT_FAILURE);
}

/*
PQL_insert(pql, a1);
PQL_insert(pql, a2);
PQL_insert(pql, a6);
PQL_insert(pql, a0);
PQL_print(pql);

*/
PQL_unit_test_insertion(pql);
PQL_print(pql);

printf("\n-------------- Removing element ----------------\n\n");
PQL_unit_test_removal(pql);
PQL_print(pql);


return 0;
}





struct pq_element* PQL_create_element(int d)
{
struct pq_element* p = malloc(1 * sizeof*p);

if(p)
{
p->priority = d;
}

return p;
}


void PQL_insert(struct pql* s, struct pq_element* e)
{
if(NULL == s)
{
fprintf(stderr, "IN: %s: Can not add element to a NULL list\n",
__func__);
return;
}
else if(NULL == e)
{
fprintf(stderr, "IN: %s: Can not add NULL element to a list\n",
__func__);
return;
}
else if(NULL == s->head) /* adding very first element */
{
printf("IN: %s: Adding very first element\n", __func__);
s->head = s->tail = e;
}
else
{
/* printf("IN: %s: Adding element to PQL\n", __func__); */
PQ_add_element(s,e);
}
}



/* This function works in conjuction with PQ_insert(), hecne there is no
need to check the arguments for NULL */
void PQ_add_element(struct pql* s, struct pq_element* e)
{
struct pq_element* h;
for( h = s->head; h; h = h->next)
{
if(e->priority > h->priority) /* given element has higher priroity
than head of list */
{
struct pq_element* temp = h->next;

if( temp && temp->priority == e->priority)
{
fprintf(stderr, "IN: %s: Element already exists, can not add
\n", __func__);
return;
}
else
{
s->head = e;
e->next = h;
break;
}
}
else if(NULL == h->next) /* we have reached the end of list and
all elements have higher priority then given element */
{
h->next = e;
e->next = NULL;
s->tail = e; /* update tail of list */
break;
}
}
}


void PQL_remove(struct pql* s)
{
if(s && s->head)
{
struct pq_element* h = s->head;
s->head = s->head->next;
PQL_free_single(h);

if(NULL == s->head)
{
s->head = s->tail = NULL;
}
}
}





/* ------------------ printing and small functions ------------------- */
struct pql* PQL_init(void)
{
struct pql* p = malloc(1 * sizeof*p);
if(p) p->head = p->tail = NULL;

return p;
}


void PQL_free_single(struct pq_element* e)
{
free(e);
}


void PQL_print(struct pql* s)
{
struct pq_element* h = NULL;

for( h = s->head; h; h = h->next)
{
PQL_print_single(h);
}
}


void PQL_print_single(struct pq_element* p)
{
if(p)
{
printf("%d\n", p->priority);
}
}









/* ------------------- Unit Testing fucntions ---------------------------
*/
void PQL_unit_test_insertion(struct pql* s)
{
const int limit = 10000000;
int i, r;
struct pq_element* e;

for(i = 0; i != limit; ++i)
{
r = rand();
e = PQL_create_element(r);

if(e)
{
PQL_insert(s, e);
}
}
}


void PQL_unit_test_removal(struct pql* s)
{
const int limit = 6;
int i;

for(i = 0; i != limit; ++i)
{
PQL_remove(s);
}
}

========================== OUTPUT ================================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra single.c
[arnuld@dune programs]$ ./a.out
IN: PQL_insert: Adding very first element
186687031
180494694
82812627
31597025
15019312
8496173
2493077
1183876
74808
16105
13935
2638
95
37

-------------- Removing element ----------------

2493077
1183876
74808
16105
13935
2638
95
37
[arnuld@dune programs]$





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

.

Relevant Pages