Heaps and running median problem, c++

running_median.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void MaxHeapify(int a[], int heap_size, int x) {
  int l = 2*x + 1;
  int r = 2*x + 2;

  int largest = x;
  if (l < heap_size && a[l] > a[x])        largest = l;
  if (r < heap_size && a[r] > a[largest])  largest = r;

  if (largest != x) {
    swap(a[x], a[largest]);
    MaxHeapify(a, heap_size, largest);
  }
}

void MinHeapify(int a[], int heap_size, int x) {
  int l = 2*x + 1;
  int r = 2*x + 2;

  int smallest = x;
  if (l < heap_size && a[l] < a[x])        smallest = l;
  if (r < heap_size && a[r] < a[smallest]) smallest = r;

  if (smallest != x) {
    swap(a[x], a[smallest]);
    MinHeapify(a, heap_size, smallest);
  }
}

int HeapExtractMax(int a[], int& heap_size) {
  int max = a[0];
  a[0] = a[heap_size-1];
  heap_size--;
  MaxHeapify(a, heap_size, 0);
  return max;
}

int HeapExtractMin(int a[], int& heap_size) {
  int min = a[0];
  a[0] = a[heap_size-1];
  heap_size--;
  MinHeapify(a, heap_size, 0);
  return min;
}

int parent(int i) {
  return (i-1)/2;
}
void insertMaxHeap(int arr[], int& heap_size, int k) {
    heap_size++;
    int i = heap_size - 1;
    arr[i] = k;
    while (i != 0 && arr[parent(i)] < k) {
      swap(arr[i], arr[parent(i)]);
      i = parent(i);
    }
}

void insertMinHeap(int arr[], int& heap_size, int k) {
  heap_size++;
  int i = heap_size - 1;
  arr[i] = k;
  while (i != 0 && arr[parent(i)] > k) {
    swap(arr[i], arr[parent(i)]);
    i = parent(i);
  }
}

int main() {
  int n, m;

  ifstream f("data_examples_05/input_16_10000.txt");
  f >> n;

  // read file into memory
  int maxHeap[n];
  int minHeap[n];

  int maxHeapSize = 0;
  int minHeapSize = 0;

  for (int i = 0; i < n; i++) {
    f >> m;
    if (i == 0) {
      insertMaxHeap(maxHeap, maxHeapSize, m);
      // cout << maxHeap[0];
      // cout << "\n";
      continue;
    }
    if (m < maxHeap[0]) {
      insertMaxHeap(maxHeap, maxHeapSize, m);
    } else {
      insertMinHeap(minHeap, minHeapSize, m);
    }
    if (maxHeapSize - minHeapSize > 1) {
      int max = HeapExtractMax(maxHeap, maxHeapSize);
      insertMinHeap(minHeap, minHeapSize, max);
    } else if (minHeapSize - maxHeapSize > 1) {
      int min = HeapExtractMin(minHeap, minHeapSize);
      insertMaxHeap(maxHeap, maxHeapSize, min);
    }

    if (maxHeapSize == minHeapSize) cout << maxHeap[0] << " " << minHeap[0];
    else if (maxHeapSize > minHeapSize) cout << maxHeap[0];
    else cout << minHeap[0];
    cout << "\n";
  }

  return 1;
}