1/* Please note that C doesn't have a built-in priority queue. Below is a custom implementation using a min-heap, which might not be directly executable without additional heap functions. */
2#include <limits.h>
3#include <stdbool.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7
8#define MAX_SIZE 1000
9
10typedef struct {
11    int* heap;
12    int size;
13    bool present[MAX_SIZE + 1];
14} SmallestInfiniteSet;
15
16SmallestInfiniteSet* smallestInfiniteSetCreate() {
17    SmallestInfiniteSet* obj = malloc(sizeof(SmallestInfiniteSet));
18    obj->heap = malloc(sizeof(int) * (MAX_SIZE + 1));
19    obj->size = 0;
20    for (int i = 0; i <= MAX_SIZE; ++i) {
21        obj->present[i] = true;
22    }
23    return obj;
24}
25
26void heapify(int* heap, int size, int index) {
27    int smallest = index;
28    int left = 2 * index + 1;
29    int right = 2 * index + 2;
30
31    if (left < size && heap[left] < heap[smallest])
32        smallest = left;
33
34    if (right < size && heap[right] < heap[smallest])
35        smallest = right;
36
37    if (smallest != index) {
38        int temp = heap[index];
39        heap[index] = heap[smallest];
40        heap[smallest] = temp;
41
42        heapify(heap, size, smallest);
43    }
44}
45
46void insertHeap(SmallestInfiniteSet* obj, int num) {
47    int i;
48    i = obj->size++;
49    obj->heap[i] = num;
50
51    while (i && obj->heap[i] < obj->heap[(i - 1) / 2]) {
52        int temp = obj->heap[i];
53        obj->heap[i] = obj->heap[(i - 1) / 2];
54        obj->heap[(i - 1) / 2] = temp;
55        i = (i - 1) / 2;
56    }
57}
58
59int removeMin(SmallestInfiniteSet* obj) {
60    if (obj->size <= 0)
61        return INT_MAX;
62    if (obj->size == 1) {
63        obj->size--;
64        return obj->heap[0];
65    }
66    int root = obj->heap[0];
67    obj->heap[0] = obj->heap[--obj->size];
68    heapify(obj->heap, obj->size, 0);
69    return root;
70}
71
72int smallestInfiniteSetPopSmallest(SmallestInfiniteSet* obj) {
73    int smallest = removeMin(obj);
74    obj->present[smallest] = false;
75    return smallest;
76}
77
78void smallestInfiniteSetAddBack(SmallestInfiniteSet* obj, int num) {
79    if (!obj->present[num]) {
80        insertHeap(obj, num);
81        obj->present[num] = true;
82    }
83}
84
85void smallestInfiniteSetFree(SmallestInfiniteSet* obj) {
86    free(obj->heap);
87    free(obj);
88}
89

1