# Heap implementation of the “median maintenance” algorithm

I have implemented a heap data structure for Coursera's algorithms course. The problem I have to solve is:

The goal of this problem is to implement the "Median Maintenance" algorithm. The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,…,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,…,xk; if k is even, then mk is the (k/2)th smallest number among x1,…,xk.)

Find the sum of the 1000 medians.

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

class Heap{
public:
vector<int> heap;

int parent(int i);
int* children(int i);
int insert(int key);
int bubbleUp(int i);
int extractMin();
int bubbleDown(int i);
int findMin(int a, int b);
};

Source

#include "medmain.h"

int Heap::parent(int i){
if (i%2 == 0)   return i/2-1;
else return (i-1)/2;
}

int* Heap::children(int i){
int* child = new int[3];
child[0] = 2*i+1;
child[1] = 2*i+2;
if (heap[child[0]] < heap[child[1]])  child[2] = child[0];
else child[2] = child[1];
return child;
}

int Heap::insert(int key){
heap.push_back(key);
if (heap.size()>1) bubbleUp(heap.size()-1);
return 0;
}

int Heap::bubbleUp(int i){
if (i==0) return 1;
if (heap[parent(i)] > heap[i]){
iter_swap(heap.begin() + parent(i), heap.begin() + i);
bubbleUp(parent(i));
}
return 1;
}

int Heap::extractMin(){
iter_swap(heap.begin(), heap.end()-1);
int minValue = heap.back();
heap.pop_back();
bubbleDown(0);
return minValue;
}

int Heap::findMin(int a, int b){
if (heap[a]<heap[b]) return a;
else return b;
}

int Heap::bubbleDown(int i){
int *child = children(i);
bool leftExists, rightExists;
leftExists = (child[0] < heap.size());
rightExists = (child[1] < heap.size());
int candidate;
if (leftExists && rightExists)  candidate = findMin(child[0], child[1]);
else if (leftExists && !rightExists) candidate = child[0];
else if (!leftExists && rightExists) candidate = child[1];
else {
delete[] child;
return -1;
}

if (heap[i] > heap[candidate]){
iter_swap(heap.begin() + i, heap.begin() + candidate);
bubbleDown(candidate);
}
delete[] child;
return 1;
}

int main(){
Heap heapL,heapH;

ifstream ipstream;
ipstream.open("Median.txt");
int output1, output2, output;
vector<int> median;

ipstream >> output1;
ipstream >> output2;

if (output1<=output2)   {heapL.insert(-output1);heapH.insert(output2);
median.push_back(output1);median.push_back(output2);}

else {heapH.insert(output1);heapL.insert(-output2);
median.push_back(output2);median.push_back(output1);}

int MaxofheapL, MinofheapH; int heapLhigh = 0, heapHhigh= 0, transfer;
while (ipstream >> output){

MaxofheapL = -*(heapL.heap.begin());
MinofheapH = *(heapH.heap.begin());

if (output <= MaxofheapL)   heapL.insert(-output);
else                heapH.insert(output);

if( int(heapL.heap.size()) - int(heapH.heap.size()) >=2){
transfer = (-1)*heapL.extractMin();
heapH.insert(transfer);
}

if (int(heapH.heap.size()) - int(heapL.heap.size()) >=2){
transfer = (-1)*heapH.extractMin();
heapL.insert(transfer);
}

if (int(heapH.heap.size()) > int(heapL.heap.size())){
median.push_back(heapH.heap[0]);
}
else if (int(heapH.heap.size()) <= int(heapL.heap.size())){
median.push_back((-1)*heapL.heap[0]);
}

}
long int sum = 0;
for (vector<int>::iterator it = median.begin() ; it!= median.end() ; it++){
sum+=*it;
}
cout << sum%10000 << endl;
return 0;
}
• Why have you implemented a heap? I am not sure I understand the relationship of the heap to the problem. – Martin York Jun 29 '15 at 6:01
• int Heap::parent(int i){return (i-1)/2;} – Martin York Jun 29 '15 at 6:04

### min heap, max heap

To keep track of the running median, an efficient solution is to store the higher half of numbers in a min heap, and the lower half of numbers in a max heap. When adding a new number, keep the size of the heaps balanced, and then the median is one of the top elements.

You did essentially this, but with a little bit unintuitive twist: instead of a min heap and a max heap, you use two min heaps, and emulate the max heap by inserting numbers negated. This may have seemed easier than implementing a heap that can be configured as min or max, but in the end you have a lot of extra logic related to negating elements for the fake max heap, and reversing the negation when you take elements out.

Think of it this way: the heap is a tool to make your job easier. A tool like this should reduce the complexity of the rest of the program. The tool is best if it let's the rest of the program focus on the main logic (keeping the heaps balanced, finding the median), without worrying about all the negations.

### Heap interface

All methods in your heap are declared public, and they shouldn't be. The essential methods of a heap that your main implementation needs:

• insert
• removeTop
• size

Methods like bubbleUp, bubbleDown are low level implementation details that should be hidden from clients.

### Unnecessary storage

You store the medians in a vector and then iterate over it to calculate the sum. It would be better to calculate the sum a you find the medians, no need for the extra storage.

I can't speak too well to the structure itself, but there's a couple of things with general practice, namely:

Using namespace std

This is bad practice, and you should avoid it wherever you can.

if(this) doThat();

Yes, this works, and is much nicer to look at (depending on perspective), but you should always put in your braces. This is because of the goto fail; bug. Basically, what if you edit this section of code and forget about the lack of braces, and still run doThat() regardless of if(this) not still being there?

if(this)
{
doThat();
}

More indentation stuff

You're doing a lot of things on one line, and for me, at least, that makes it a bit more tricky to figure out what's happening. Things like

if (output1<=output2)   {heapL.insert(-output1);heapH.insert(output2);
median.push_back(output1);median.push_back(output2);}

would be much nicer as

if (output1 <= output2)
{
heapL.insert(-output1);
heapH.insert(output2);
median.push_back(output1);
median.push_back(output2);
}

public vector<int> heap

I can't see a good reason for this to be public. Unless I missed some instance where you're accessing it directly, you're already using it as if it were private, so why not make it that way.

• Thanks for the feedback. I will think about access the next time – cppprogrammer Jun 29 '15 at 12:53