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
|
# STC [cpque](../include/stc/cpque.h): Priority Queue
A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
A user-provided argument `<`or `>` must be supplied to set the ordering, e.g. using `>` would cause the smallest element to appear as the top().
See the c++ class [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue) for a functional reference.
## Header file and declaration
```c
#define i_tag
#define i_val // required
#define i_cmp // required if i_val is a struct
#define i_valdel
#define i_valfrom
#define i_valto
#define i_valraw
#include <stc/cpque.h>
```
`X` should be replaced by the value of i_tag in all of the following documentation.
## Methods
```c
cpque_X cpque_X_init(void);
cpque_X cpque_X_clone(cpque_X pq);
void cpque_X_clear(cpque_X* self);
void cpque_X_make_heap(cpque_X* self);
void cpque_X_del(cpque_X* self); // destructor
size_t cpque_X_size(cpque_X pq);
bool cpque_X_empty(cpque_X pq);
const cpque_X_value_t* cpque_X_top(const cpque_X* self);
void cpque_X_push(cpque_X* self, cpque_X_value_t value);
void cpque_X_emplace(cpque_X* self, cpque_X_rawvalue_t raw);
void cpque_X_emplace_items(cpque_X *self, const cpque_X_rawvalue_t arr[], size_t n);
void cpque_X_pop(cpque_X* self);
void cpque_X_erase_at(cpque_X* self, size_t idx);
cpque_X_value_t cpque_X_value_clone(cpque_X_value_t val);
```
## Types
| Type name | Type definition | Used to represent... |
|:---------------------|:--------------------------------------|:------------------------|
| `cpque_X` | `struct {cpque_X_value_t* data; ...}` | The cpque type |
| `cpque_X_value_t` | Depends on underlying container type | The cpque element type |
| `cpque_X_rawvalue_t` | " | cpque raw value type |
## Example
```c
#include <stc/crandom.h>
#include <stdio.h>
#define i_tag i
#define i_val int64_t
#define i_cmp -c_default_compare // min-heap
#include <stc/cpque.h>
int main()
{
size_t N = 10000000;
stc64_t rng = stc64_init(1234);
stc64_uniform_t dist = stc64_uniform_init(0, N * 10);
// Declare heap, with defered del()
c_forauto (cpque_i, heap)
{
// Push ten million random numbers to priority queue, plus some negative ones.
c_forrange (N)
cpque_i_push(&heap, stc64_uniform(&rng, &dist));
c_emplace(cpque_i, heap, {-231, -32, -873, -4, -343});
// Extract and display the fifty smallest.
c_forrange (50) {
printf("%zd ", *cpque_i_top(&heap));
cpque_i_pop(&heap);
}
}
}
```
Output:
```
-873 -343 -231 -32 -4 3 5 6 18 23 31 54 68 87 99 105 107 125 128 147 150 155 167 178 181 188 213 216 272 284 287 302 306 311 313 326 329 331 344 348 363 367 374 385 396 399 401 407 412 477
```
|
