Share my solution with my binaryHeap


  • 0
    C

    public class MedianFinder {

    private BinaryHeap<Integer> bigTopHeap;
    private BinaryHeap<Integer> smallTopHeap;
    
    /** initialize your data structure here. */
    public MedianFinder() {
    	bigTopHeap = new BinaryHeap<Integer>(BinaryHeap.HeapType.bigTopHeap);
        smallTopHeap = new BinaryHeap<Integer>(BinaryHeap.HeapType.smallTopHeap);
    }
    
    public void addNum(int num) {
    	if(smallTopHeap.size() < bigTopHeap.size()){
    		bigTopHeap.insert(num);
    		Integer newNum = bigTopHeap.deleteTop();
    		smallTopHeap.insert(newNum);
    	}
    	else{
    		smallTopHeap.insert(num);
    		Integer newNum = smallTopHeap.deleteTop();
    		bigTopHeap.insert(newNum);
    	}
    }
    
    public double findMedian() {
    	int size = bigTopHeap.size() + smallTopHeap.size();
    	if((size & 1) == 0){
    		return ((double) bigTopHeap.findTop() + smallTopHeap.findTop()) / 2;
    	}
    	else
    		return (double)bigTopHeap.findTop();
    }
    

    }

    class BinaryHeap <AnyType extends Comparable<? super AnyType>> {

    private static final int DEFAULT_CAPACITY = 10;
    
    private int currentSize;
    private AnyType[] array;
    
    private HeapType type;
    
    public enum HeapType{
    	bigTopHeap,
    	smallTopHeap
    }
    
    public BinaryHeap(HeapType type){
    	this.type = type;
    	currentSize = 0;
    	array = (AnyType[]) new Comparable[(DEFAULT_CAPACITY + 2) * 11 / 10];
    }
    
    public BinaryHeap(HeapType type, int capacity){
    	this.type = type;
    	currentSize = 0;
    	array = (AnyType[]) new Comparable[(capacity + 2) * 11 / 10];
    }
    
    public BinaryHeap(HeapType type, AnyType[] items){
    	this.type = type;
    	currentSize = items.length;
    	array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
    	
    	int i = 1;
    	for(AnyType item : items)
    		array[i++] = item;
    	buildHeap();
    }
    
    
    
    public void insert(AnyType x){
    	if(currentSize == array.length - 1)
    		enlargeArray(array.length * 2 + 1);
    	int hole = ++ currentSize;
    	for(; hole > 1 && isSwap(x, array[hole / 2]); hole /= 2)
    		array[hole] = array[hole / 2];
    	array[hole] = x;
    }
    
    public AnyType findTop(){
    	if(currentSize == 0)
    		return null;
    	else
    		return array[1];
    }
    
    public AnyType deleteTop(){
    	if(isEmpty()){
    		return null;
    	}
    	
    	AnyType topItem = findTop();
    	array[1] = array[currentSize--];
    	percolateDown(1);
    	
    	return topItem;
    }
    
    public int size(){
    	return currentSize;
    }
    
    public boolean isEmpty(){
    	return currentSize == 0;
    }
    
    public void makeEmpty(){
    	currentSize = 0;
    }
    
    
    private boolean isSwap(AnyType newEle, AnyType oldEle){
    	return type == HeapType.smallTopHeap ? newEle.compareTo(oldEle) < 0 : newEle.compareTo(oldEle) > 0;
    }
    
    private void percolateDown(int hole){
    	int child;
    	AnyType tmp = array[hole];
    	
    	for ( ; hole * 2 <= currentSize; hole = child) {
    		child = hole * 2;
    		if(child != currentSize && isSwap(array[child + 1], array[child]))
    			child ++;
    		if(isSwap(array[child], tmp))
    			array[hole] = array[child];
    		else
    			break;
    	}
    	array[hole] = tmp;
    }
    
    private void buildHeap(){
    	for(int i = currentSize / 2; i > 0; i--)
    		percolateDown(i);
    }
    
    private void enlargeArray(int newSize){
    	AnyType[] newArray = (AnyType[]) new Comparable[newSize];
    	
    	for(int i = 1; i < array.length; i++){
    		newArray[i] = array[i];
    	}
    	array = newArray;
    }
    

    }

    /**

    • Your MedianFinder object will be instantiated and called as such:
    • MedianFinder obj = new MedianFinder();
    • obj.addNum(num);
    • double param_2 = obj.findMedian();
      */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.