aboutsummaryrefslogtreecommitdiff
path: root/smallest_num_set.c
blob: dabe17ea84785bc279691c571e2249e5ffecd31b (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
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
98
99
100
// 2336. Smallest Number in Infinite Set
#include <stdbool.h>
#include <stdlib.h>

/*
 * you have a set which contains all positive integers [1,2,3,...]
 * implement the SmallestInfiniteSet class:
 * - SmallestInfiniteSet() initialises the SmallestInfiniteSet
 *   object to contain all positive integers
 * - int popSmallest() removes and returns the smallest integer
 *   contained in the infinite set
 * - void addBack(int num) adds a positive integer num back into
 *   the infinite set, if it is not already in the infinite set
 */

typedef struct {
  int *heap;
  bool *hash;
  int heap_size;
} SmallestInfiniteSet;

SmallestInfiniteSet *SmallestInfiniteSetCreate() {
  SmallestInfiniteSet *res = malloc(sizeof(SmallestInfiniteSet));
  res->heap = malloc(1001 * sizeof(int));
  res->hash = malloc(1000 * sizeof(bool));
  for (int i = 0; i < 1000; i++) {
    res->heap[i] = i + 1;
    res->hash[i] = true;
  }
  res->heap_size = 1000;
  return res;
}

int SmallestInfiniteSetPopSmallest(SmallestInfiniteSet *obj) {
  if (!obj->heap_size)
    return -1;
  int res = obj->heap[0];
  obj->hash[res - 1] = false;
  obj->heap[0] = obj->heap[obj->heap_size - 1];
  obj->heap_size--;
  int pos = 0, tmp;
  while (pos < obj->heap_size) {
    if ((2 * pos + 1) >= obj->heap_size)
      break;
    if (2 * pos + 1 == obj->heap_size - 1) {
      if (obj->heap[pos] > obj->heap[2 * pos + 1]) {
        tmp = obj->heap[pos];
        obj->heap[pos] = obj->heap[2 * pos + 1];
        obj->heap[2 * pos + 1] = tmp;
        pos = 2 * pos + 1;
      }
      break;
    }
    if (obj->heap[pos] > obj->heap[2 * pos + 1] ||
        obj->heap[pos] > obj->heap[2 * pos + 1]) {
      if (obj->heap[2 * pos + 1] <= obj->heap[2 * pos + 1]) {
        tmp = obj->heap[2 * pos + 1];
        obj->heap[2 * pos + 1] = obj->heap[pos];
        obj->heap[pos] = tmp;
        pos = 2 * pos + 1;
      } else {
        tmp = obj->heap[2 * pos + 2];
        obj->heap[2 * pos + 2] = obj->heap[pos];
        obj->heap[pos] = tmp;
        pos = 2 * pos + 2;
      }
    } else
      break;
  }
  return res;
}

void SmallestInfiniteSetAddBack(SmallestInfiniteSet *obj, int num) {
  if (obj->hash[num - 1])
    return;
  else
    obj->hash[num - 1] = true;
  obj->heap[obj->heap_size] = num;
  int pos = obj->heap_size;
  obj->heap_size++;
  int tmp;
  while (pos && (obj->heap[pos] < obj->heap[(pos - 1) / 2])) {
    tmp = obj->heap[(pos - 1) / 2];
    obj->heap[(pos - 1) / 2] = obj->heap[pos];
    obj->heap[pos] = tmp;
    pos = (pos - 1) / 2;
  }
}

void SmallestInfiniteSetFree(SmallestInfiniteSet *obj) {
  free(obj->heap);
  free(obj);
}

int main() {
  SmallestInfiniteSet *obj = SmallestInfiniteSetCreate();
  int param_1 = SmallestInfiniteSetPopSmallest(obj);
  SmallestInfiniteSetAddBack(obj, 2);
  SmallestInfiniteSetFree(obj);
}