Max Heap 구현

작성일 | In

Max Heap 구현

가능하면 가독성을 높여서 짜본 Heap이다. inline 함수를 최대한 활용해서 push와 pop 동작을 알기 쉽게 구현했다.

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
class Heap {
  int data[100001];
  int bound;

  inline int LS(int a) { return 2*a; }
  inline int RS(int a) { return 2*a+1; }
  inline int PA(int a) { return a/2; }

  inline void swap(int x, int y) {
    int tmp = data[x];
    data[x] = data[y];
    data[y] = tmp;
  }

  inline int max(int x, int y){
    return data[x] > data[y] ? x : y;
  }
  inline int max(int x, int y, int z) {
    return max(x, max(y, z));
  }

 public:
  Heap() {
    memset(data, 0, sizeof(data));
    bound = 1;
  }

  void push(int x) {
    int pos = bound;
    data[bound++] = x;

    while (data[pos] > data[PA(pos)] && pos > 1) {
      swap(pos, PA(pos));
      pos = PA(pos);
    }
  }
  
  int pop() {
    if (bound == 1) return 0;
    int pos = 1;
    int ret = data[1];
    data[1] = data[--bound];
    data[bound] = -1;

    while(LS(pos) < bound || RS(pos) < bound) {
      int m = max(pos, LS(pos), RS(pos));
      if (m != pos) {
        swap(m, pos);
        pos = m;
      } else break;
    }
    return ret;
  }
};