-
Notifications
You must be signed in to change notification settings - Fork 1
/
min_pq.h
executable file
·91 lines (60 loc) · 2.3 KB
/
min_pq.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**@file
Functions and structures for implementing a minimizing priority queue.
Copyright (C) 2006-2010 Rob Hess <hess@eecs.oregonstate.edu>
@version 1.1.2-20100521
*/
#ifndef MINPQ_H
#define MINPQ_H
#include <stdlib.h>
/******************************* Defs and macros *****************************/
/* initial # of priority queue elements for which to allocate space */
#define MINPQ_INIT_NALLOCD 512
/********************************** Structures *******************************/
/** an element in a minimizing priority queue */
struct pq_node
{
void* data;
int key;
};
/** a minimizing priority queue */
struct min_pq
{
struct pq_node* pq_array; /* array containing priority queue */
int nallocd; /* number of elements allocated */
int n; /**< number of elements in pq */
};
/*************************** Function Prototypes *****************************/
/**
Creates a new minimizing priority queue.
*/
extern struct min_pq* minpq_init();
/**
Inserts an element into a minimizing priority queue.
@param min_pq a minimizing priority queue
@param data the data to be inserted
@param key the key to be associated with \a data
@return Returns 0 on success or 1 on failure.
*/
extern int minpq_insert( struct min_pq* min_pq, void* data, int key );
/**
Returns the element of a minimizing priority queue with the smallest key
without removing it from the queue.
@param min_pq a minimizing priority queue
@return Returns the element of \a min_pq with the smallest key or NULL
if \a min_pq is empty
*/
extern void* minpq_get_min( struct min_pq* min_pq );
/**
Removes and returns the element of a minimizing priority queue with the
smallest key.
@param min_pq a minimizing priority queue
@return Returns the element of \a min_pq with the smallest key of NULL
if \a min_pq is empty
*/
extern void* minpq_extract_min( struct min_pq* min_pq );
/**
De-allocates the memory held by a minimizing priorioty queue
@param min_pq pointer to a minimizing priority queue
*/
extern void minpq_release( struct min_pq** min_pq );
#endif