C言語でプライオリティーキュー構造体

C言語で関数ポインタを使ってカプセル化に挑戦してみた
でやってみたカプセル化にならって、優先順位付きキューを実装してみました。

int型を扱うシンプルな作りをしていて、構造体を作るときに渡す列挙体の値で優先順位を昇順か降順か選択できます。また、ヒープに使う領域が不足したらメモリ領域を自動で伸張する作りになっています。１万でも１０万でも要素を入れちゃえる。

また、ヒープを操作するときに、ノード操作のためにルートノードの番号は１なので、仕様する配列は０番目を使わないか、インデクス操作をごにょごにょするか、普通はどちらかをすると思うんですが、今回はＣ言語の配列の添え字が１から始まるように工夫してみました。

int a[10];
int p = a-1;

これで配列の添え字が１スタートになりました。

そんな感じです.てきとう.

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

//
// utility
//
void
swap(int* p, int* q)
{
    int swp = *q;
    *q = *p;
    *p = swp;
}

//
// data structure
//
enum pqueue_order {
    PQUEUE_ORDER_DESC = -1,
    PQUEUE_ORDER_ASC = 1
};

typedef struct pqueue {
    int* heap;
    int reserved;                     // reserved memory size
    int size;                         // heap size
    int (*push)(struct pqueue*, int);
    int (*pop)(struct pqueue*);
    int (*empty)(struct pqueue*);
    enum pqueue_order ord;
} pqueue_t;

//
// methods
//
int
pqueue_push(pqueue_t* self, int n)
{
    int node;
    int *heap;
    
    // ordering
    n *= self->ord;
    
    // expand heap size if stervation occured
    if (self->size >= self->reserved) {
        self->reserved = self->reserved * 2;
        self->heap = realloc(self->heap, self->reserved * sizeof(int));
    }
    
    heap = self->heap - 1; // index start from 1
    heap[++self->size] = n;

    // up-heap
    for (node = self->size; heap[node] < heap[node / 2] && node != 1; node/=2)
        swap(heap + node, heap + node/2);
   
    return 0;
}

int
pqueue_pop(pqueue_t* self)
{
    int ret;
    int left, rght;
    int node, downto;
    int *heap = self->heap - 1; // index start from 1
    
    if (self->size == 0)
        return -1;
    
    // de-ordering
    ret = heap[1] * self->ord;
    
    // down-heap
    heap[1] = heap[(self->size)--];
    for (node = 1, downto = -1; node != downto; swap(heap + node, heap + downto), node = downto) {
        int left = node*2    ;
        int rght = node*2 + 1;
        
        downto = node;
        // downto = min(parent, left child, right child)
        if (left <= self->size && heap[left] < heap[downto])
            downto = left;
        if (rght <= self->size && heap[rght] < heap[downto])
            downto = rght;
    }
    
    return ret;
}

int
pqueue_empty(pqueue_t* self)
{
    return self->size == 0;
}

//
// constructor
//
pqueue_t*
create_pqueue(enum pqueue_order ord)
{
    pqueue_t *p = malloc(sizeof(pqueue_t));
    
    p->size = 0;
    p->reserved = 2;
    p->heap = malloc(p->reserved * sizeof(int));
    
    p->ord = ord;
    
    p->push = pqueue_push;
    p->pop = pqueue_pop;
    p->empty = pqueue_empty;
    
    return p;
}

//
// destructor
//
void
dispose_pqueue(pqueue_t* q)
{
    free(q->heap);
    free(q);
}

int
test()
{
    pqueue_t *q;
    q = create_pqueue(PQUEUE_ORDER_DESC);

    q->push(q, 5);
    q->push(q, 1);
    q->push(q, 8);
    q->push(q, 9);
    q->push(q, -1);
    
    while (!q->empty(q))
        printf("%d%c", q->pop(q), 10);
    
    dispose_pqueue(q);
    
    return 0;
}

int main()
{
    test();
    return 0;
}

実行結果

$ ./a.out 
9
8
5
1
-1