heap - changicho/algorithm-training GitHub Wiki

long long heap[100002];
int heap_size = 0;

void heap_delete() {
  int current, left, right;

  heap[1] = heap[heap_size];
  heap[heap_size] = 0;
  heap_size -= 1;

  if (heap_size == 0) {
    return;
  }

  current = 1;
  while (true) {
    left = current * 2;
    right = current * 2 + 1;

    if (left > heap_size) {
      break;
    }

    // if it has only left node
    if (right > heap_size) {
      if (heap[left] < heap[current]) {   // 변경점
        swap(heap[left], heap[current]);
        current = left;
        continue;
      }
    }
    // if it has two node
    else {
      if (heap[left] <= heap[right]) {   // 변경점
        if (heap[left] < heap[current]) {   // 변경점
          swap(heap[left], heap[current]);
          current = left;
          continue;
        }
      }
      else {
        if (heap[right] < heap[current]) {   // 변경점
          swap(heap[right], heap[current]);
          current = right;
          continue;
        }
      }
    }

    if (current == left / 2) {
      break;
    }
  }

  return;
}

void heap_push(int input) {
  heap_size += 1;
  heap[heap_size] = input;

  int current = heap_size, parent;

  while (true) {
    if (current == 1) break;

    parent = current / 2;

    if (heap[current] < heap[parent]) {   // 변경점
      swap(heap[parent], heap[current]);
    }
    else {
      break;
    }
    current = parent;
  }
}

priority_queue<int> pq; // 우선순위 큐 선언

cin >> input;

switch(input){
  case 0:{
    if (pq.empty()) {   // queue가 비어있을 경우 0 출력
      cout << "0\n";
    } else {
      // 가장 위에 들어가있는 값을 출력
      cout << pq.top() << "\n";
      pq.pop();
    }
  }
  case 1:{
    pq.push(x); // 입력한 숫자 queue에 삽입
  }
}

struct Data {
  int abs, value;
};
struct compare {
  bool operator()(Data a, Data b) {
    if (a.abs != b.abs) {
      return a.abs > b.abs;
    }
    return a.value > b.value;
  }
};
priority_queue<Data, vector<Data>, compare> pq;

struct Data {
  int abs, value;
};
bool operator<(Data a, Data b) {
  if (a.abs != b.abs) {
    return a.abs > b.abs;
  }
  return a.value > b.value;
}
priority_queue<Data> pq;

struct Data {
  int abs, value;
  bool operator<(const Data &b) const {
    if (abs != b.abs) {
      return abs > b.abs;
    }
    return value > b.value;
  }
};
priority_queue<Data> pq;