【AOJ ALDS1_9】C: Heaps - Priority Queue

問題

優先度付きキュー | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• 優先度付きキューを実装する問題
• （体がしんどいので元気になったらしっかり書きます許して）

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define MAX 2000000
#define INF (1<<30)
#define left(i) (i * 2);
#define right(i) (i * 2 + 1)

using namespace std;

int h;
int A[MAX+2];

void maxHeapify(int i){
  int r = right(i);
  int l = left(i);
  int _max = i;
  
  if(l <= h && A[l] > A[_max]) _max =l;
  if(r <= h && A[r] > A[_max]) _max = r;

  if(_max != i){
    swap(A[i], A[_max]);
    maxHeapify(_max);
  }
}

int extract(){
  if(h < 1) return -INF;
  int maxv = A[1];
  A[1] = A[h];
  h--;
  maxHeapify(1);
  return maxv;
}

void insert(int x){
  h++;
  A[h] = -INF;
  if(x < A[h]) return;
  
  A[h] = x;
  int i = h;
  while(i > 1 && A[i/2] < A[i]){
    swap(A[i/2], A[i]);
    i /= 2;
  }
  
}

signed main(){
  string command;
  int n;
  h = 0;
  while(true){
    cin >> command;    
    if(command == "end") break;
    if(command == "insert"){
      cin >> n;
      insert(n);
    }else{
      cout << extract() << endl;;
    }
    
  }
}

風邪ひきながらといたので, 定数の0が1つ足りなくて小一時間悩むというミスをした. 元気なときにやらないとダメだね.