#include <algorithm>
#include <iostream>
#include <vector>
#include <exception>

using namespace std;

template<typename T>
class DynamicArray {
private:
  vector<T> minHeap;
  vector<T> maxHeap;

public:
  void Insert(T num) {

    make_heap(maxHeap.begin(), maxHeap.end(), less<T>());
    make_heap(minHeap.begin(), minHeap.end(), greater<T>());

    if(((minHeap.size() + maxHeap.size()) & 1) == 0) { // # of elements are even
      if(maxHeap.size()>0 && num<maxHeap[0]) {
	maxHeap.push_back(num);
	push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

	num = maxHeap[0];

	pop_heap(maxHeap.begin(), maxHeap.end(), less<T>());
	maxHeap.pop_back();
      }

      minHeap.push_back(num);
      push_heap(minHeap.begin(), minHeap.end(), greater<T>());
    } else { // # of elements are odd
      if(minHeap.size()>0 && num>minHeap[0]) {
	minHeap.push_back(num);
	push_heap(minHeap.begin(), minHeap.end(), greater<T>());

	num = minHeap[0];

	pop_heap(minHeap.begin(), minHeap.end(), greater<T>());
	minHeap.pop_back();
      }

      maxHeap.push_back(num);
      push_heap(maxHeap.begin(), maxHeap.end(), less<T>());
    }
  }



  int getMedian() {
    int size = minHeap.size()+maxHeap.size();
    
    if(size==0) {
      cerr << "No numbers are available" << endl;
      exit(1);
    }
    
    T median = 0;
    if((size&1)==1)
      median = minHeap[0];
    else
      median = (minHeap[0]+maxHeap[0])/2;

    return median;
  }

  void arrayPrint() {
    //    sort(maxHeap.begin(), maxHeap.end(), less<T>());
    sort_heap(maxHeap.begin(), maxHeap.end(), less<T>());
    for(unsigned i=0; i<maxHeap.size(); i++)
      cout << maxHeap[i] << ' ';
   
    //    sort(minHeap.begin(), minHeap.end(), less<T>());
    sort_heap(minHeap.begin(), minHeap.end(), less<T>());
    for(unsigned i=0; i<minHeap.size(); i++)
      cout << minHeap[i] << ' ';
    cout << endl;
  }
}; 
  


int main(int argc, char **argv) {
  DynamicArray<int> *dArray = new DynamicArray<int>();

  for(int i=0; i<20; i++) {
    dArray->Insert(rand()%100);


    if(i>0) {
      cout << "Median is: " << dArray->getMedian() << endl;

      cout << "Stream is: "; 
      dArray->arrayPrint();
    }
  }

  /*  for(int i=0; i<20; i++) {
    cout << heap[i] << ' ';
  }
  cout << endl; */

  //  cout << dArray->getMedian() << endl;
  
  return 0;
}