Finding the running median with 2 heaps [closed]

Question

I am trying to solve running median problem in hackerrank https://www.hackerrank.com/challenges/ctci-find-the-running-median and below is my code

public class Solution {

   public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        MinHeap minHeap = new MinHeap();
        MaxHeap maxHeap = new MaxHeap();
        float median = 0;
        for(int a_i=0; a_i < n; a_i++) {

            // Logic to add the running element
            int element = in.nextInt();
            if (minHeap.size == maxHeap.size) {
                if (element <= median) {
                    maxHeap.addItem(element);
                    median = maxHeap.peek();
                } else {
                    minHeap.addItem(element);
                    median = minHeap.peek();
                }
            } else if (maxHeap.size > minHeap.size) {
                if (element <= median) {
                    minHeap.addItem(maxHeap.poll());
                    maxHeap.addItem(element);
                } else {
                    minHeap.addItem(element);
                }
                median = (float)(maxHeap.peek() + minHeap.peek()) / 2;
            } else {
                if (element <= median) {
                    maxHeap.addItem(element);
                } else {
                    maxHeap.addItem(minHeap.poll());
                    minHeap.addItem(element);
                }
                median = (float)(maxHeap.peek() + minHeap.peek()) / 2;
            }
            System.out.println(median);
        } 
    }

    static abstract class Heap {
        int[] items = new int[10];
        int capacity = 10;
        int size = 0;


        boolean hasLeftChild(int parent) {
            int leftChildIndex = getLeftChildIndex(parent);
            if (leftChildIndex > size - 1) {
                return false;
            }
            return true;
        }

        boolean hasRightChild(int parent) {
            int rightChildIndex = getRightChildIndex(parent);
            if (rightChildIndex > size - 1) {
                return false;
            }
            return true;
        }

        boolean hasParent(int index) {
            if (index > 0) {
                return true;
            } else {
                return false;
            }
        }

        int getLeftChildIndex(int parent) {
            int leftChildIndex = parent * 2 + 1;
            return leftChildIndex;
        } 

        int getRightChildIndex(int parent) {
            int rightChildIndex = parent * 2 + 2;
            return rightChildIndex;
        }

        int getParentIndex(int index) {
            int parent = (index -1)/2;
            return parent;
        }

        int getLeftChild(int parent) {
            return items[getLeftChildIndex(parent)];    
        }

        int getRightChild(int parent) {
            return items[getRightChildIndex(parent)];    
        }

        int getParent(int index) {
            return items[getParentIndex(index)];
        }

        void ensureCapacity() {
            if (size == capacity) {
                items = Arrays.copyOf(items, capacity * 2);
                capacity = capacity * 2;
            }    
        }

        void addItem(int item) {
            ensureCapacity();
            items[size] = item;
            size = size + 1;
            heapifyUp();
        }

        int poll() {
            int topItem = items[0];
            items[0] = items[size - 1];
            size = size - 1;
            heapifyDown();
            return topItem;
        }

        int peek() {
            return items[0]; 
        }

        abstract void heapifyDown();

        abstract void heapifyUp();

        void swap(int indexA, int indexB) {
            int temp = items[indexA];
            items[indexA] = items[indexB];
            items[indexB] = temp;
        }
    }

    static class MinHeap extends Heap {
        void heapifyUp() {
            int index = size - 1;
            while(hasParent(index)) {
                if (getParent(index) <= items[index]) {
                    break;
                } else {
                    swap(getParentIndex(index), index);
                    index = getParentIndex(index);
                }
            }
        }

        void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent) && getLeftChild(parent) <= items[parent]) {
                int smallerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) <= getLeftChild(parent)) {
                    smallerIndex = getRightChildIndex(parent);
                }
                swap(parent, smallerIndex);
                parent = smallerIndex;
            }
        }
    }

    static class MaxHeap extends Heap {
        void heapifyUp() {
            int index = size - 1;
            while(hasParent(index)) {
                if (getParent(index) >= items[index]) {
                    break;
                } else {
                    swap(getParentIndex(index), index);
                    index = getParentIndex(index);
                }
            }
        }

        void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent) && getLeftChild(parent) >= items[parent]) {
                int largerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) >= getLeftChild(parent)) {
                    largerIndex = getRightChildIndex(parent);
                }
                swap(parent, largerIndex);
                parent = largerIndex;
            }
        }
    }
}

It successfully passes for the first basic test case but fails for all other test cases on submitting code. It seems to be correct when i debugged it with some samples of the test input. Can someone review my code and help me understand what the issue is with respect to the current implementation ?

Answer 1

I would offer a test case here. It's a shortened version of test case 1.

24
94455
20555
20535
53125
73634
148
63772
17738
62995
13401
95912
13449
92211
17073
69230
22016
22120
78563
16571
1817
41510
74518
81638
89659

The median of the 24 numbers is 47317.5 But your program produces 52252.5

Hope this test case will help you find out the issue. There is a built-in Java implementation of Heap: PriorityQueue. If you want to try that out to test your logic.

Answer 2

There is a bug with respect to the logic in heapifyDown() methods which caused the incorrect median values

So the corrected heapifyDown methods are below

For MinHeap

void heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent)) {
                int smallerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) < getLeftChild(parent)) {
                    smallerIndex = getRightChildIndex(parent);
                }
                if (items[parent] < items[smallerIndex]) {
                    break;
                } else {
                    swap(parent, smallerIndex);
                }
                parent = smallerIndex; 
            }
        }

For MaxHeap

oid heapifyDown() {
            int parent = 0;
            while(hasLeftChild(parent)) {
                int largerIndex = getLeftChildIndex(parent);
                if(hasRightChild(parent) && getRightChild(parent) > getLeftChild(parent)) {
                    largerIndex = getRightChildIndex(parent);
                }
                if (items[parent] > items[largerIndex]) {
                    break;
                } else {
                    swap(parent, largerIndex);
                }
                parent = largerIndex;
            }
        }