Priority queue descending order


class HeapSortDescendingOrder {
    private static Comparable[] array;
    private static int count;
    
    private HeapSortDescendingOrder() {
    }
    
    public static void sort(Comparable[] list) {
        // assign list to array so it can be used in private methods without passing to method parameter
        array = list;
        count = list.length;
        
        // Build min heap
        for(int i = array.length/2; i >= 0; i--) {
            sink(i);
        }
        
        // shift each element at sorted position 
        while(count > 0) {
            // put 0th element in it's sorted positon 
            swap(0, --count);
            // maintain heap property
            sink(0);
        }
    }
    
    private static 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(array[child], array[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(array[child], array[root])) {
                break;
            }
            swap(root, child);
            root = child;
            child = getLeftChildIndex(root);
        }
    }
    
    private static boolean greater(Comparable key1, Comparable key2) {
        return key1.compareTo(key2) > 0;
    }
    
    private static void swap(int i, int j) {
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    /**
     * Get parent index of binary heap node. Index start with 0.
     */
    private static int getParentIndex(int i) {
        return (i-1)/2;
    }
    
    /**
     * Get left child index of binary heap node. Index start with 0.
     */
    private static int getLeftChildIndex(int i) {
        return (2*i+1);
    }
    
    /**
     * Get left child index of binary heap node. Index start with 0.
     */
    private static int getRightChildIndex(int i) {
        return (2*i+2);
    }
    
    private static void display() {
        for(Comparable key : array) {
            System.out.print(key + " ");
        }
    }
    
	public static void main (String[] args) {
	    System.out.println("Test 1 ");
		Integer[] arrayInts = new Integer[] {11,13,7,12,16,9,24,5,10,3};
		HeapSortDescendingOrder.sort(arrayInts);
		
		// Print sorted elements 
	    display();
		
		System.out.println("\nTest 2 ");
		String[] arrayStr = new String[] {"My", "Name", "Is", "Raghav", "M", "And", "I", "Stay", "In", "Bangalore"};
		HeapSortDescendingOrder.sort(arrayStr);
		
		// Print sorted elements
		display();
	}
}

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

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance