blob: cf5930217105a8091ec57f8e3dcbd453433a9a67 (
plain)
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
|
#include "priority_queue.h"
#include <stdlib.h>
PriorityQueue *initialize() {
PriorityQueue *queue = malloc(sizeof(PriorityQueue));
queue->size = 0;
queue->head = NULL;
return queue;
}
Node *create_node(int priority, int data) {
Node *node = malloc(sizeof(Node));
node->priority = priority;
node->data = data;
node->next = NULL;
return node;
}
// This function is constant time O(1)
int size(PriorityQueue *queue) {
return queue->size;
}
// This function is linear time O(n)
void add(PriorityQueue *queue, Node *node) {
queue->size++;
if (queue->head == NULL) {
queue->head = node;
return;
}
Node *tmp = queue->head;
Node *prev = NULL;
while(tmp != NULL) {
if (tmp->data > node->data) {
node->next = tmp;
if (tmp == queue->head)
queue->head = node;
else if (prev != NULL)
prev->next = node;
break;
}
prev = tmp;
tmp = tmp->next;
}
}
// This function is constant time O(1)
Node *delete_min(PriorityQueue *queue) {
if (queue->head) {
Node *tmp = queue->head;
queue->head = tmp->next;
queue->size--;
return tmp;
}
return NULL;
}
void destroy(PriorityQueue *queue) {
Node *current = queue->head;
Node *tmp;
while(current) {
tmp = current, current = current->next;
if (tmp) free(tmp);
}
free(queue);
}
|
