Priority Queue | Min heap


class MinPriorityQueue> {
    private Key[] queue;
    private int count;
    private static final int CAPACITY = 3;
    
    public MinPriorityQueue() {
        this(CAPACITY);
    }
    
    public MinPriorityQueue(int capacity) {
        queue = (Key[]) new Comparable[capacity];
        count = 0;
    }
    
    public boolean isEmpty() {
        return count == 0;
    }
    
    public void insert(Key key) {
        // validate size and resize queue is needed 
        if(queue.length == count) {
            resize(2*queue.length);
        }
        // add key after last eleent in queue 
        queue[count++] = key;
        
        // maintain binary heap property
        swim(count-1);
    }
    
    public Key deleteMin() {
        Key min = queue[0]; // For sorting swap it with last element
        // assign last element to root 
        queue[0] = queue[--count];
        // free last space 
        queue[count] = null;
        // maintain binary heap property
        sink(0);
        //validate and resize queue 
        if(count < queue.length/4) {
            resize(queue.length/2);
        }
        return min;
    }
    
    private void swim(int i) {
        // get left child
        int parent = getParentIndex(i);
        while(i > 0 && greater(queue[parent], queue[i])) {
            swap(parent, i);
            i = parent;
            parent = getParentIndex(i);
        }
    }
    
    private void sink(int root) {
        int child = getLeftChildIndex(root);
        while(child <= count-1) {
            // if there is right child. Right chlild = Left child + 1  
            if(child < count-1 && greater(queue[child], queue[child+1])) {
                child = child + 1;// point child to right child as it is lesser than left child 
            }
            // if binary heap property already satisfied then break the loop 
            if(greater(queue[child], queue[root])) {
                break;
            }
            swap(root, child);
            root = child;
            child = getLeftChildIndex(root);
        }
    }
    
    private boolean greater(Key key1, Key key2) {
        return key1.compareTo(key2) > 0;
    }
    
    private void swap(int i, int j) {
        Key temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }
    
    /**
     * Get parent index of binary heap node. Index start with 0.
     */
    private int getParentIndex(int i) {
        return (i-1)/2;
    }
    
    /**
     * Get left child index of binary heap node. Index start with 0.
     */
    private int getLeftChildIndex(int i) {
        return (2*i+1);
    }
    
    /**
     * Get left child index of binary heap node. Index start with 0.
     */
    private int getRightChildIndex(int i) {
        return (2*i+2);
    }
    
    private void resize(int size) {
        // create temp array
        Key[] temp = (Key[]) new Comparable[size];
        // copy all elements from queue to temp 
        for(int i = 0; i < count; i++) {
            temp[i] = queue[i];
        }
        // assign temp to queue 
        queue = temp;
    }
    
	public static void main (String[] args) {
	    System.out.println("Test 1 ");
		MinPriorityQueue queue = new MinPriorityQueue();
		int[] arrayInts = new int[] {11,13,7,12,16,9,24,5,10,3};
		
		// insert all elements in queue 
		for(int key : arrayInts) {
		    queue.insert(key);
		}
		
		while(!queue.isEmpty()) {
		    System.out.print(queue.deleteMin() + " ");
		}
		
		System.out.println("\nTest 2 ");
		MinPriorityQueue queue2 = new MinPriorityQueue<>();
		String[] arrayStr = new String[] {"My", "Name", "Is", "Raghav", "M", "And", "I", "Stay", "In", "Bangalore"};
		
		// insert all elements in queue 
		for(String key : arrayStr) {
		    queue2.insert(key);
		}
		
		while(!queue2.isEmpty()) {
		    System.out.print(queue2.deleteMin() + " ");
		}
	}
}

Test 1 
3 5 7 9 10 11 12 13 16 24 
Test 2 
And Bangalore I In Is M My Name Raghav Stay 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance