I am looking for a complete C code that implements a prioritized queue
(Heap Method preferred). I am trying to implement several prioritized
buffers on an Atmel microcontrollers (Electrical Engineering, no much
software knowledge) using standard C code (no C++, classes or OOP).
Basically, I have a previously defined Structure such as follows:

typedef struct
{
	unsigned char prority;
	unsigned char packetType;
	unsigned int destinationAddress; 	
	unsigned int sourceAddress; 			
	char payload[26]; 			
} Packet;

I need to be able to have a FIFO Buffer / Priority Queue to hold 10
"Packet" structures and they need to be ordered based upon the
priority (zero being the highest). It needs to have the regular Queue
functions:

- AddItem [Enqueue] : Add item and orders it by priority, moving all
that are necessary to be moved, and also in a FIFO fashion.
- RemoveItem [Dequeue] : Removes the item with highest priority (or if
more than one has the same priority, the first one that came, regular
FIFO).
- isEmpty : check if buffer is empty.
- isFull : check if buffer is full.

and any other you think it is necessary. The functions will most
likely pass a BUFFER and the Element to be add [AddItem], or pass a
BUFFER and return the removed element [removeItem].

I have to stress out that since this is for a microcontroller, it must
not use any OOP, classes or advance techniques, pure and simple ANSI C
code. If you use special libraries please make sure to let me know,
because not all of them are available on my compiler (CodeVision AVR).

Thank you very much! Sorry for asking this like that, but I have never
taken a Data Structures Class and I am just trying to attempt a packet
manager on a AVR microcontroller.

Thanks again.

/*priority queue, using a binary heap with static maximum size
This code is in the public domain, but I would be glad if you leave my name in:
Rene Wiermer, rwiermer@googlemail.com. Feedback is welcome.

The implemementation is based on Heapsort as described in
"Introduction to Algorithms" (Cormen, Leiserson, Rivest, 24. printing)
*/

/*needed for test only*/
#include <stdio.h>
/**/

#define MAX_SIZE 10

typedef struct
{
        unsigned char priority;
        unsigned char packetType;
        unsigned int destinationAddress;        
        unsigned int sourceAddress;                     
        char payload[26];                       
} Packet;

typedef struct {
	Packet* packets[MAX_SIZE];
	unsigned int size;
} PacketHeap;


void heap_init(PacketHeap* h) {
	h->size=0;
}

void heap_heapify(PacketHeap* h,int i) {
	int l,r,smallest;
	Packet* tmp;
	l=2*i; /*left child*/
	r=2*i+1; /*right child*/

	if ((l < h->size)&&(h->packets[l]->priority < h->packets[i]->priority))
		smallest=l;
	else 
		smallest=i;
	if ((r < h->size)&&(h->packets[r]->priority < h->packets[smallest]->priority))
		smallest=r;
	if (smallest!=i) {
		/*exchange to maintain heap property*/
		tmp=h->packets[smallest];
		h->packets[smallest]=h->packets[i];
		h->packets[i]=tmp;
		heap_heapify(h,smallest);
	}
}

void heap_addItem(PacketHeap* h,Packet* packet) {
	unsigned int i,parent;	
	h->size=h->size+1;
	i=h->size-1;
	parent=i/2;
	/*find the correct place to insert*/
	while ((i > 0)&&(h->packets[parent]->priority > packet->priority)) {
		h->packets[i]=h->packets[parent];
		i=parent;
		parent=i/2;
	}
	h->packets[i]=packet;
}

Packet* heap_extractMin(PacketHeap* h) {
	Packet* max;
	if (heap_isEmpty(h))
		return 0;
	max=h->packets[0];
	h->packets[0]=h->packets[h->size-1];
	h->size=h->size-1;
	heap_heapify(h,0);
	return max;
}

int heap_isEmpty(PacketHeap *h) {
	return h->size==0;
}

int heap_isFull(PacketHeap *h) {
	return h->size>=MAX_SIZE;
}

/*Test code*/
int main() {
	PacketHeap heap;
	unsigned char i;
	Packet p[10];
	p[0].priority=123;
	p[1].priority=23;
	p[2].priority=0;
	p[3].priority=22;
	p[4].priority=255;
	p[5].priority=1;
	p[6].priority=10;
	p[7].priority=3;
	p[8].priority=101;
	p[9].priority=102;

	heap_init(&heap);
	for (i=0;i<10;i++) {
		printf("Add %i\n",p[i].priority);
		heap_addItem(&heap,&(p[i]));
	}
	while (!heap_isEmpty(&heap)) {
		i=heap_extractMin(&heap)->priority;
		printf("%i\n",i);
	}
}

So, the previous post is my attempt on it. A good excercise to brush
up old C knowledge.

Since you are using only a maximum of 10 elements, this solution with
a heap maybe overkill. There should be not much difference to a
reasonably implemented linear search.

But i have to think a bit, whether this algorithms acts like a FIFO
when there are equal priorities or not.

Heapsort is not stable, which means that this priority queue does not
hold the FIFO condition for elements with same priority.
If you need this (e.g. if you want to guarantee, that a packet is
leaving in a reasonable time), you need to modify the algorithm (e.g.
add a secondary key, which holds information about the sequence of
adding) or use another one (linear search, for example).

Do you have code for the Linear Search you are telling me about? The
final use for this task will be a FIFO for basically only three type
of packages with priorities 1,2 and 3 respectively. Therefore the FIFO
quality should be met. I mentioned Heap because that is the only term
I found was associated with Priority Queues always (I have to say it
again, not very good at programming). What would you suggest? I really
need help on this! The reason what I am also worring about speed, it's
because this will run on a microcontroller with limited processing and
RAM.

Thank you again for understanding the problem :)

/*priority queue using a sorted ring buffer with static maximum size.
FIFO property is maintained.
This code is in the public domain, but I would be glad if you leave my name in:
Rene Wiermer, rwiermer@googlemail.com. Feedback is welcome.

*/

/*needed for test only*/
#include <stdio.h>
/**/

#define MAX_SIZE 10

typedef struct
{
        unsigned char priority;
        unsigned char packetType;
        unsigned int destinationAddress;        
        unsigned int sourceAddress;                     
        char payload[26];                       
} Packet;

typedef struct {
        Packet* packets[MAX_SIZE];
        unsigned int size;
	unsigned int currentmin; /*current minimum element*/
} PacketQueue;


void queue_init(PacketQueue* q) {
	q->size=0;
	q->currentmin=0;
}

int queue_nextElem(PacketQueue* q,int i) {
	if (i==queue_lastElem(q))
		return q->currentmin;
	return (i+1)%MAX_SIZE;
}

int queue_prevElem(PacketQueue* q,int i) {
	if (i==q->currentmin)
		return queue_lastElem(q);
	return (i+MAX_SIZE-1)%MAX_SIZE;
}

int queue_lastElem(PacketQueue* q) {
	return (q->currentmin+q->size-1)%MAX_SIZE;
}


void queue_addItem(PacketQueue* q,Packet* p) {
/*WARNING: no check performed, if buffer is full*/
	if (q->size==0) {
		q->currentmin=0;
		q->packets[q->currentmin]=p;
		q->size=1;
	}
	else {
		unsigned int stop,maxelem,i;
		unsigned char key;
		key=p->priority;
		i=queue_lastElem(q);
		q->size=q->size+1;
		stop=queue_lastElem(q);
		/*Insert into the sorted ring buffer, starting from the back to
maintain FIFO property*/
		while (i!=stop&&(q->packets[i]->priority>key)) {
			q->packets[queue_nextElem(q,i)]=q->packets[i];
			i=queue_prevElem(q,i);		
		}
		q->packets[queue_nextElem(q,i)]=p;
	}
	
}

Packet* queue_extractMin(PacketQueue* q) {
/*WARNING: no check performed, if buffer is empty*/
	Packet* min;
	min=q->packets[q->currentmin];
	q->currentmin=queue_nextElem(q,q->currentmin);
	q->size=q->size-1;
	return min;
}

int queue_isFull(PacketQueue* q) {
	return	q->size>=MAX_SIZE;
}

int queue_isEmpty(PacketQueue* q) {
	return q->size==0;
}
int main() {
        PacketQueue heap;
        int i,j;
        Packet p[10];
        p[0].priority=123;
        p[1].priority=124;
        p[2].priority=0;
        p[3].priority=222;
        p[4].priority=245;
        p[5].priority=1;
        p[6].priority=101;
        p[7].priority=3;
        p[8].priority=101;
        p[9].priority=102;

        queue_init(&heap);
	for (j=0;j<1000000;j++) {
        for (i=0;i<10;i++) {
                queue_addItem(&heap,&(p[i]));
        }

	
        while (!queue_isEmpty(&heap)) {
                i=queue_extractMin(&heap)->priority;
        }
	}
}

This code is not exactly linear search (searching the minimum in a
list at extraction) but instead does the hard work when adding an item
(maintaing a sorted list), but the theoretical complexity of the
algorithm should be the same. It is implemented as a circular buffer
with static size.
To give a rough estimate of running time: On my 1Ghz Athlon, with GCC
3.4 and all optimization, 10.000.000 round of completely filling and
removing from the queue:

Heap (no FIFO)   Sorted List (FIFO)
1.547s           4.625s

I am to lazy to make the heap implementation FIFO-proof. It should'nt
be that hard, though (e.g. write a comparison routine for packets,
which also includes a secondary key, which reflects the order of
inclusion).  Some registered expert could to it for the money. Also
the code needs thorough testing in all different situations.
If you or an expert is  willing to donate some money for my work, I
would suggest "Books for Africa" (http://www.booksforafrica.org/).

Dear Rene Wiermer,

I extremely appreciate your help and time. I did not know that you
were not answering the question as a researcher. I am going to close
this discussion and donate http://www.booksforafrica.org the money
that I intended for this question as it has been answered :)

Thank you once again!