11931 - 수 정렬하기 4

 

11931번: 수 정렬하기 4

 

힙 정렬이 짜기도 쉽고, 이해도 쉽다

 

메모리도 좋고

 

이거 계속 쓰쟈

 

#include <stdio.h>

const int LM = 1e6;

int maxComp(int x, int y) { return x > y; }
int minComp(int x, int y) { return x < y; }
int N;

void swap(int& x, int& y) { int z = x; x = y; y = z; }

struct PQ {
  int hn;
  int heap[LM + 10];
  int (*comp)(int, int);

  void init(int flag) {
    hn = 0;
    comp = flag ? maxComp : minComp;
  }

  void push(int n) {
    heap[++hn]= n;

    for (int c = hn; c > 1; c /= 2) {
      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }
  }

  int pop() {
    swap(heap[1], heap[hn--]);

    for (int c = 2; c <= hn; c *= 2) {
      if (c < hn && comp(heap[c + 1], heap[c])) {
        c++;
      }

      if (comp(heap[c], heap[c / 2])) { swap(heap[c], heap[c / 2]); }
      else break;
    }

    return heap[hn + 1];
  }

} pq;

void init() {
  pq.init(1);

  scanf("%d", &N);

  for (int n = 0; n < N; ++n) {
    int t;

    scanf("%d", &t);

    pq.push(t);
  }
}

void print() {
  while(pq.hn) {
    printf("%d\n", pq.pop());
  }
}

int main() {
  // freopen("11931.txt", "r", stdin);

  init();

  print();

  return 0;
}

 

삼성아 고마워 !