1 /*priority queue, using a binary heap with static maximum size
2 This code is in the public domain, but I would be glad if you leave my name in:
3 Rene Wiermer, rwiermer@googlemail.com. Feedback is welcome.
5 The implemementation is based on Heapsort as described in
6 "Introduction to Algorithms" (Cormen, Leiserson, Rivest, 24. printing)
9 /*needed for test only*/
13 #define MAX_SIZE 100000
14 typedef struct priormsg_s
{
15 unsigned int priority
;
23 priormsg
* msgs
[MAX_SIZE
];
28 void heap_init(MsgHeap
* h
) {
32 int heap_size(MsgHeap
* h
)
36 void heap_heapify(MsgHeap
* h
,int i
) {
40 r
=2*i
+1; /*right child*/
42 if ((l
< h
->size
)&&(h
->msgs
[l
]->priority
< h
->msgs
[i
]->priority
))
46 if ((r
< h
->size
)&&(h
->msgs
[r
]->priority
< h
->msgs
[smallest
]->priority
))
49 /*exchange to maintain heap property*/
50 tmp
=h
->msgs
[smallest
];
51 h
->msgs
[smallest
]=h
->msgs
[i
];
53 heap_heapify(h
,smallest
);
57 void heap_addItem(MsgHeap
* h
, priormsg
* packet
) {
58 unsigned int i
,parent
;
62 /*find the correct place to insert*/
63 while ((i
> 0)&&(h
->msgs
[parent
]->priority
> packet
->priority
)) {
64 h
->msgs
[i
]=h
->msgs
[parent
];
71 priormsg
* heap_extractMin(MsgHeap
* h
) {
76 h
->msgs
[0]=h
->msgs
[h
->size
-1];
82 int heap_isEmpty(MsgHeap
*h
) {
86 int heap_isFull(MsgHeap
*h
) {
87 return h
->size
>=MAX_SIZE
;