一个C优先级队列实现

刚下班没事干，实现了一个简单的优先级队列

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

typedef void (*pqueue_setindex) (void *obj, int pq_index);
typedef int (*pqueue_cmp) (void* obj1, void* obj2);
typedef struct pqueue_struct
{
void **heap;
int numelem;
pqueue_setindex setindex;
pqueue_cmp cmp;

}pqueue;

pqueue* pqueue_new(int pq_size, pqueue_setindex setindexf, pqueue_cmp cmpf)
{
pqueue * pq = (pqueue*)calloc(1, sizeof(pqueue));
if( pq == NULL) goto error;
pq->heap = (void**)calloc(1, pq_size*sizeof(void*));
if( pq->heap == NULL) {
free(pq);
goto error;
}
pq->numelem = 0;
pq->setindex = setindexf;
pq->cmp = cmpf;
return pq;
error:
return NULL;
}

void pqueue_delete(pqueue * pq)
{
if(pq == NULL || pq->heap == NULL) return;
free(pq->heap);
free(pq);
}

int pqueue_upheap(pqueue* pq, int pq_index)
{
void *obj = (void*)pq->heap[pq_index];
int i = pq_index, parent;
while(i > 0)
{
parent = i >> 1;
if( pq->cmp( pq->heap[parent], obj ) < 0 )
{
pq->heap[i] = pq->heap[parent];
pq->setindex(pq->heap[parent], i);
i = parent;
}
else break;

}
pq->heap[i] = obj;
pq->setindex(obj, i);
return i;
}

void pqueue_downheap(pqueue* pq, int pq_index)
{
void *obj = pq->heap[pq_index];
int i = pq_index, child;
while(i < pq->numelem)
{
child = i << 1;
if( pq->cmp( pq->heap[child], pq->heap[child+1]) < 0 ) child++;
if( pq->cmp( pq->heap[child], obj) > 0)
{
pq->heap[i] = pq->heap[child];
pq->setindex(pq->heap[child], i);
i = child;
}
else break;

}
pq->heap[i] = obj;
pq->setindex(obj, i);
}

void* pqueue_get(pqueue * pq, int pq_index)
{
return pq->heap[pq_index];
}

int pqueue_size(pqueue* pq)
{
return pq->numelem;
}

int pqueue_insert( pqueue * pq, void *obj )
{
pq->heap[pq->numelem] = obj;
pqueue_upheap(pq, pq->numelem);
pq->numelem ++;
return 0;
}

void pqueue_remove( pqueue * pq, int pq_index)
{
void *obj = pq->heap[pq_index];
pq->setindex(obj,0);
pq->heap[pq_index] = pq->heap[--pq->numelem];
pq->setindex(pq->heap[pq_index],pq_index);
int i = pqueue_upheap(pq, pq_index);
pqueue_downheap(pq, i);

}
//////////////
typedef struct pelem_struct
{
int priority;
int pq_index;
void *obj;
}pelem;

void setindex(void *elem, int pq_index)
{
((pelem*)elem)->pq_index = pq_index;
}
int cmp(void * pelem1, void * pelem2)
{
return ((pelem*)pelem1)->priority - ((pelem*)pelem2)->priority;
}
void print(pqueue* pq)
{
int num = pqueue_size(pq);
if(!num) {
printf("pqueue is none\n");
return;
}
int i;
for(i = 0; i < num; i++)
printf("index:%d, priority:%d\n",i,((pelem*)(pqueue_get(pq,i)))->priority);
}

void main()
{
pqueue * pq = pqueue_new(16, setindex, cmp);
if(pq == NULL) printf("cannot create pqueue\n");
pelem p1,p2,p3;
p1.priority = 10;
p2.priority = 5;
p3.priority = 6;
pqueue_insert(pq, &p1);
print(pq);
pqueue_insert(pq, &p2);
pqueue_insert(pq, &p3);
print(pq);
pqueue_remove(pq, p2.pq_index);
print(pq);

}

巴特西

一个C优先级队列实现

最新文章

热门文章