Heapify routine for Min-Max Heap

heapify.cpp

  // This is a minor modificatioin for the one wrongly implemented in http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
  // Heapification
// Note that, for the current median tracing problem
// we need to heapify only towards root, always
void heapify(int i, bool down= false)
{
    if (!down){
        // heapify up
        int p = parent(i);

        // comp - differentiate MaxHeap and MinHeap
        // percolates up
        if( p >= 0 && comp(A[i], A[p]) )
        {
            Exch(A[i], A[p]);
            heapify(p);
        }

        return;
    }

    // heapify down
    int left = this->left(i);
    int right = this->right(i);

    if(left <= this->heapSize && !comp(A[i], A[left])){
        Exch(A[i], A[left]);
        return heapify(left);
    }
    if(right <= this->heapSize && !comp(A[i], A[right])){
        Exch(A[i], A[right]);
        return heapify(right);
    }
}

// Deletes root of heap
int deleteTop()
{
    int del = -1;

    if( heapSize > -1)
    {
        del = A[0];

        Exch(A[0], A[heapSize]);
        heapSize--;
        heapify(0, true);
    }

    return del;
}