-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheap_priority_queue.h
More file actions
97 lines (77 loc) · 4.07 KB
/
heap_priority_queue.h
File metadata and controls
97 lines (77 loc) · 4.07 KB
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
92
93
94
95
96
97
#ifndef HEAP_PRIORITY_QUEUE_H
#define HEAP_PRIORITY_QUEUE_H
#ifndef huff_data_t
#define HUFF_DATA_T huff_data_t
typedef struct huff_data_t {
char *element;
int weight;
} huff_data_t;
#endif
typedef struct tree_node_t {
struct huff_data_t *data;
struct tree_node_t *left;
struct tree_node_t *right;
} tree_node_t;
typedef struct heap_pq_node_t {
struct tree_node_t *tree_node;
struct heap_pq_node_t *next;
} heap_pq_node_t;
/*
binary_heap_pq_t
+---------------------+
| head | ----> +--------------------+
| | | heap_pq_node_t |
| size | +--------------------+
+---------------------+ | tree_node | ----> +------------------+
| next | | tree_node_t |
+--------------------+ +------------------+
/ | data |
/ | left | ----> +------------------+
/ | right | | tree_node_t |
/ +------------------+ +------------------+
/ | data |
/ | left |
/ | right |
/ +------------------+
/
/
/
/
+--------------------+
| heap_pq_node_t |
+--------------------+
| tree_node | ----> +------------------+
| next | | tree_node_t |
+--------------------+ +------------------+
| data |
| left | ----> +------------------+
| right | | tree_node_t |
+------------------+ +------------------+
| data |
| left |
| right |
+------------------+
*/
/**
* binary heap priority queue
*/
typedef struct binary_heap_pq_t{
heap_pq_node_t *head;
int size;
} binary_heap_pq_t;
binary_heap_pq_t* create_binary_heap_pq();
int is_empty(binary_heap_pq_t *heap);
heap_pq_node_t* create_new_node(char *element, int weight);
void insert_node(binary_heap_pq_t *heap, char *element, int weight);
void insert_heap_pq_node(binary_heap_pq_t *heap, heap_pq_node_t *new_node);
void delete_node(binary_heap_pq_t *heap, heap_pq_node_t **previous, heap_pq_node_t **current);
void remove_top_node(binary_heap_pq_t *heap, heap_pq_node_t **topNode);
void free_binary_heap_pq(binary_heap_pq_t *heap);
void free_tree_node(tree_node_t *node);
void free_heap_priority_queue(binary_heap_pq_t *heap);
void free_heap_pq_node(heap_pq_node_t *node);
void print_heap_pq_node(heap_pq_node_t *node);
void print_heap(binary_heap_pq_t *heap);
void traverse_list_and_trees(binary_heap_pq_t *heap, void (*traverse_func)(tree_node_t *));
void print_heap_post_order(tree_node_t *root);
#endif