/*
 Copyright 2010 Marek p2004a Rusinowski
 www.algorytm.org
*/

#include <cmath>

#define MAX true
#define MIN false

class Heap {
  unsigned int max_size, size, *data;
  bool which;

  void swap(unsigned int index_a, unsigned int index_b) {
    unsigned int x = data[index_a];
    data[index_a] = data[index_b];
    data[index_b] = x;
  }

  bool cmp(unsigned int index_a, unsigned int index_b) {
      return which ? ( data[index_a] < data[index_b] ? true : false) : (data[index_a] > data[index_b] ? true : false);
  }

 public:
  // pobiera aktualna wysokosc kopca
  unsigned int getHeight() {
    return (unsigned int) floor((log((long double) size) / log((long double) 2)) + 1);
  }
  
  // pobiera aktualny rozmiar kopcac (ilosc elementow)
  unsigned int getSize() {
    return size;
  }
  
  // pobiera aktualny maksymalny rozmiar kopca
  unsigned int getMaxSize() {
    return max_size;
  }

  // konstruktor kopca;
  //   jako parametr max_size okreslamy poczatkowy maksymany rozmiar kopca, w parametrze max okreslamy warunek kopca czyli czy ma byc max (normalny) czy min kopiec
  Heap(unsigned int max_size, bool max = true);
  
  // wstawia element do kopca; 
  //   jako parametr value podajemy wartosc nowego elementu
  //   zwraca true jesli sie udalo i false jesli nie (np kopiec pelny)
  bool insert(unsigned int value);
  
  // usowa korzen kopca; 
  //   zwraca wartosc usuwanego korzenia
  unsigned int erase();
  
  // zmienia rozmiar kopca (nowa wartosc moze byc wieksza, moze byc mniejsza);
  //   jako parametr podajemy nowy maksymalny rozmiar kopca
  //   zwraca true jesli sie udalo i false jesli nie (np kopiec zajmuje za duzo i nie da sie zmniejszyc jego maksymalnego rozmiaru na podany)
  bool resize(unsigned int new_size);
};

/*
 Copyright 2010 Marek p2004a Rusinowski
 www.algorytm.org
*/

#include "kopiec.h"
#include <cstring>
#include <cstdio>
#include <cmath>

Heap::Heap(unsigned int ssize, bool max): max_size(ssize), data(new unsigned int [ssize + 2]), size(0), which(max) {
  memset(data, (max ? 0 : 0xFFFFFFFF) , ssize + 2);
}

bool Heap::insert(unsigned int value) {
  if (size == max_size) {
    return false;
  }
  data[size++] = value;
  for (unsigned int i = size; i != 1; i /= 2) {
    if (cmp((i / 2) - 1, i - 1)) {
      swap((i / 2) - 1, i - 1);
    } else {
      break;
    }
  }
  return true;
}

unsigned Heap::erase() {
  if (size == 0) {
    return 0;
  }
  unsigned value = data[0];
  data[0] = data[--size];
  unsigned i = 1;
  while (i * 2 <= size) {
    register unsigned tmp = cmp((i * 2) - 1, i * 2) ? (i * 2) : (i * 2) - 1;
    if (cmp(i - 1, tmp)) {
      swap(i - 1, tmp);
      i = tmp + 1;
    } else {
      break;
    }
  }
  return value;
}

bool Heap::resize(unsigned new_size) {
  if (new_size < size) {
    return false;
  }
  max_size = new_size;
  unsigned *tmp = new unsigned [new_size];
  memset(tmp, (which ? 0 : ~0) , new_size);
  memcpy(tmp, data, size);
  delete [] data;
  data = tmp;
  return true;
}