Skip to content

Instantly share code, notes, and snippets.

@rweeks
Created November 29, 2012 00:56
Show Gist options
  • Save rweeks/4165962 to your computer and use it in GitHub Desktop.
Save rweeks/4165962 to your computer and use it in GitHub Desktop.
min_queue.c
typedef struct node {
int v;
node *prev_min;
node *next;
} node;
typedef struct {
node *head;
node *tail;
} min_queue;
int min_queue_append( min_queue *q, int v) {
n = malloc(sizeof node);
n->v = v;
n->next = NULL;
if (q->head == NULL) {
q->head = n;
}
if (q->tail != NULL) {
q->tail->next = n;
n->prev_min = (q->tail->v < q->tail->prev_min->v) ? q->tail : q->tail->prev_min;
q->tail = n;
}
else
{
q->tail = n;
n->prev_min = NULL;
}
}
int min_queue_pop( min_queue *q, int *v ) {
}
int min_queue_min( min_queue *q, int *min) {
if (q->tail == NULL) { return -1; };
if (q->tail->prev_min == NULL) { *min = q->tail->v; return 0};
*min = (q->tail->v < q->tail->prev_min->v) ? q->tail->v : q->tail->prev_min->v;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment