CareerCup

package com.datastructure.priorityheap;

import java.util.NoSuchElementException;
 
class BinaryHeap    
{
    private static final int d = 2;
    private int heapSize;
    private int[] heap;
 
    public BinaryHeap(int capacity)
    {
        heapSize = 0;
        heap = new int[capacity + 1];
    }
 
    public boolean isEmpty( )
    {
        return heapSize == 0;
    }
 
    public boolean isFull( )
    {
        return heapSize == heap.length;
    }
 
    public void makeEmpty( )
    {
        heapSize = 0;
    }
 
    private int parent(int i) 
    {
        return (i - 1)/d;
    }
 
    private int kthChild(int i, int k) 
    {
        return d * i + k;
    }
 
    public void insert(int x)
    {
        if (isFull( ) )
            throw new NoSuchElementException("OverFlow : Heap is full");
        heap[heapSize++] = x;
        heapifyUp(heapSize - 1);
    }
 
    public int findMin( )
    {
        if (isEmpty() )
            throw new NoSuchElementException("Underflow: Heap is empty");           
        return heap[0];
    }
 
    public int deleteMin()
    {
        int keyItem = heap[0];
        delete(0);
        return keyItem;
    }
 
    public int delete(int ind)
    {
        if (isEmpty() )
            throw new NoSuchElementException("Underflow Exception");
        int keyItem = heap[ind];
        heap[ind] = heap[heapSize - 1];
        heapSize--;
        heapifyDown(ind);        
        return keyItem;
    }
 
    private void heapifyUp(int childInd)
    {
        int tmp = heap[childInd];    
        while (childInd > 0 && tmp < heap[parent(childInd)])
        {
            heap[childInd] = heap[ parent(childInd) ];
            childInd = parent(childInd);
        }                   
        heap[childInd] = tmp;
    }
 
    private void heapifyDown(int ind)
    {
        int child;
        int tmp = heap[ ind ];
        while (kthChild(ind, 1) < heapSize)
        {
            child = minChild(ind);
            if (heap[child] < tmp)
                heap[ind] = heap[child];
            else
                break;
            ind = child;
        }
        heap[ind] = tmp;
    }
 
    private int minChild(int ind) 
    {
        int bestChild = kthChild(ind, 1);
        int k = 2;
        int pos = kthChild(ind, k);
        while ((k <= d) && (pos < heapSize)) 
        {
            if (heap[pos] < heap[bestChild]) 
                bestChild = pos;
            pos = kthChild(ind, k++);
        }    
        return bestChild;
    }
 
    public void printHeap()
    {
        System.out.println("Heap = ");
        for (int i = 0; i < heapSize; i++)
            System.out.print(heap[i] +" ");
        System.out.println();
    }     
}
 
public class BinaryHeapImpl
{
    public static void main(String[] args)
    {
        BinaryHeap bh = new BinaryHeap(6);
        bh.insert(3);
        bh.insert(2);
        bh.insert(1);
        bh.insert(8);
        bh.insert(5);
        System.out.println("Min Element :-"+bh.findMin());
        bh.printHeap(); 
        bh.deleteMin();
        System.out.println("Min Element :-"+bh.findMin());
        bh.printHeap();
    }
}

Priority Queue Interface

package priorityQueue;

public interface PriorityQueue<K,V>{

	public int size();
	
	public boolean isEmpty();
	
	public Entry<K,V> min() throws EmptyPriorityQueueException;
	
	public Entry<K, V> insert(K key, V value) throws UnComparableKeyException;
	
	public Entry<K, V> removeMin() throws EmptyPriorityQueueException;
}

Heap Based Priority Queue
--------------------------------------

public class HeapPriorityQueue<K, V> implements PriorityQueue<K, V> {

	Heap<K, V> heap;
	
	public HeapPriorityQueue() {
		super();
		heap = new Heap<>();
	}
	
	public HeapPriorityQueue(Comparator<? super K> comparator) {
		super();
		heap = new Heap<>(comparator);
	}
	
	@Override
	public int size() {
		return heap.size();
	}

	@Override
	public boolean isEmpty() {
		return heap.isEmpty();
	}

	@Override
	public Entry<K, V> min() throws EmptyPriorityQueueException {
		return heap.getMin();
	}

	@Override
	public Entry<K, V> insert(K key, V value) throws UnComparableKeyException {
		return heap.add(key, value);
	}

	@Override
	public Entry<K, V> removeMin() throws EmptyPriorityQueueException {
		return heap.removeMin();
	}

}

Heap Implementation using Complete Binary Tree
-----------------------------------

public class Heap<K, V> {

	ArrayListCompleteBinaryTree<Entry<K, V>> completeBinaryTree = new ArrayListCompleteBinaryTree<Entry<K, V>>();
	Comparator<? super K> comparator;
	
	public Heap(Comparator<? super K> comparator){
		this.comparator = comparator;
	}
	
	public Heap(){
		comparator = null;
	}
	
	public Entry<K, V> add(K key, V value) throws UnComparableKeyException{
		return add(new Entry<K, V>(key, value));
	}
	
	public Entry<K, V> add(Entry<K, V> entry) throws UnComparableKeyException{
		// handle case of comparable interface as well.
		if (isEmpty()){
			return completeBinaryTree.add(entry).getElement();
		}
		
		ArrayListCompleteBinaryTreeNode<Entry<K, V>> addedEntry = completeBinaryTree.add(entry); // adds element to the end.
		K addedKey = addedEntry.getElement().getKey();
		ArrayListCompleteBinaryTreeNode<Entry<K, V>> parentNode = completeBinaryTree.getParentNode(addedEntry);
		K parentKey = parentNode.getElement().getKey();
		
		while(addedKeyLessThanParentKey(addedKey, parentKey)){
			addedEntry = completeBinaryTree.swap(addedEntry,parentNode); // swap and get new position of added entry.
			parentNode = completeBinaryTree.getParentNode(addedEntry);
			if (parentNode == null){
				break;
			}
			parentKey = parentNode.getElement().getKey();
		}
		return addedEntry.getElement();
	}

	public Entry<K, V> removeMin() throws EmptyPriorityQueueException{
		
		throw new EmptyPriorityQueueException("Not yet implemented");
	}
	
	public Entry<K, V> getMin(){
		if (isEmpty()){
			return null;
		}
		
		
		return completeBinaryTree.getRootElement();
	}
	
	public boolean isEmpty(){
		return completeBinaryTree.isEmpty();
	}

	private boolean addedKeyLessThanParentKey(K addedKey, K parentKey) throws UnComparableKeyException {
		if (comparator == null){
			if (addedKey instanceof Comparable<?> && parentKey instanceof Comparable<?>){
				@SuppressWarnings("unchecked")
				Comparable<K> compatableAddedKey = (Comparable<K>)addedKey;
				if (compatableAddedKey.compareTo(parentKey) < 0){
					return true;
				} else {
					return false;
				}
			}else {
				throw new UnComparableKeyException();
			}
		} else {// use comparator
			if (comparator.compare(addedKey, parentKey) < 0){
				return true;
			} else {
				return false;
			}
		}
	}

	public int size() {
		return completeBinaryTree.size();
	}
}

Array based Complete Binary Tree
---------------------------------------------

public class ArrayListCompleteBinaryTree<E> implements CompleteBinaryTree<E>{

	ArrayList<ArrayListCompleteBinaryTreeNode<E>> arrayList = new ArrayList<ArrayListCompleteBinaryTreeNode<E>>();

	public ArrayListCompleteBinaryTree() {
		super();
		arrayList.add(0, null);
	}
	
	@Override
	public ArrayListCompleteBinaryTreeNode<E> add(E element) {
		int addIndex = arrayList.size();
		ArrayListCompleteBinaryTreeNode<E> treeNode = new ArrayListCompleteBinaryTreeNode<E>(addIndex, element);
		arrayList.add(addIndex, treeNode);
		return treeNode;
	}

	@Override
	public E remove() {
		ArrayListCompleteBinaryTreeNode<E> lastItem = arrayList.remove(arrayList.size()-1);
		return lastItem.getElement();
	}
	
	public E getRootElement(){
		return arrayList.get(1).getElement();
	}
	
	public ArrayListCompleteBinaryTreeNode<E> getRootNode(){
		return arrayList.get(1);
	}

	public ArrayListCompleteBinaryTreeNode<E> getParentNode(ArrayListCompleteBinaryTreeNode<E> node){
		if (isRoot(node)){
			return null;
		}
		int pos = node.getIndex();
		int parentPos = 0;
		if ((pos%2) == 0){ //it is even ie, left child
			parentPos = pos/2;
		} else {
			parentPos = (pos - 1)/2;
		}
		return arrayList.get(parentPos);
	}
	
	public boolean isEmpty() {
		return (arrayList.size() == 1 ? true : false);
	}
	
	public ArrayListCompleteBinaryTreeNode<E> swap(ArrayListCompleteBinaryTreeNode<E> node1, ArrayListCompleteBinaryTreeNode<E> node2){
		int node1Index = node1.getIndex();
		int node2Index = node2.getIndex();
		
		node1.setIndex(node2Index);
		node2.setIndex(node1Index);

		arrayList.set(node1Index, node2);
		arrayList.set(node2Index, node1);
		
		return node1;
	}
	
	public boolean isRoot(ArrayListCompleteBinaryTreeNode<E> node){
		if (node.getIndex() == 1){
			return true;
		}else {
			return false;
		}
	}

	public int size() {
		return arrayList.size() - 1;
	}
	
}

Complete Binary Tree Node
-------------------------------------

public class ArrayListCompleteBinaryTreeNode<E>{

	int index;
	E element;
	
	public ArrayListCompleteBinaryTreeNode() {
		index = -1;
		element = null;
	}
	
	public ArrayListCompleteBinaryTreeNode(int index, E element){
		this.index = index;
		this.element = element;
	}
	
	public void setIndex(int index){
		this.index = index;
	}
	
	public int getIndex(){
		return index;
	}
	
	public E getElement(){
		return element;
	}

}

I used default hashCode method along with MAD (Multiply Add and Divide) to get hash Value. Collision resolved by Separate chaining. Remove is not implemented but could be implemented as add.

Here is the implementations in c#

We first define the the element class which will have queue element

public class Element
{
        public int priority;
        public int value;
}

once we have defined the element class, we initialise the queue, and define some common parameters for the queue

public static Element[] minQueue { get; set; }

public static int queueCurrentSize { get; set; }

public static int maxQueueSize { get; set; }

Then we ask use to input the max size of the queue, as we have to define some size for it, although there exits some implementations where the element is added to the queue on the fly, but we have to bear the computational burden, which is heigher, so, mostly you will find that the queue implementation need the size.

After this, we ask user to take an action which he/she want to perform on the queue

Console.WriteLine("Following Action can be taken on the priority queue");
Console.Write("Extract Min(Choose Action : EM){0}Insert(Choose Action : I){0}Get Min(Choose Action : GM){0}Queue Size(Choose Action : QS){0}Print Queue(Choose Action : PQ){0}Clear Queue(Choose Action : CQ){0}Exit(Choose Action : Exit){0}Choose Your Action : ", '\n');
while (true)
{
    string action = Console.ReadLine().Trim();
    if (action.Equals("EM", StringComparison.InvariantCultureIgnoreCase) 
        || action.Equals("I", StringComparison.InvariantCultureIgnoreCase) 
        || action.Equals("GM", StringComparison.InvariantCultureIgnoreCase) 
        || action.Equals("QS", StringComparison.InvariantCultureIgnoreCase)
        || action.Equals("PQ", StringComparison.InvariantCultureIgnoreCase)
        || action.Equals("CQ", StringComparison.InvariantCultureIgnoreCase)
        || action.Equals("Exit", StringComparison.InvariantCultureIgnoreCase))
    {
        return action.ToUpperInvariant();
    }
    else
    {
        Console.WriteLine("Choose correctly please");
    }
}

Once we have the input action from the user, we can use the switch statement to choose between actions and make correct function call

actionTaken = GetUserAction();
switch(actionTaken)
{
    case "EM" :
        Extract_Min();
        break;
    case "I" :
        Insert();
        break;
    case "GM" :
        Get_Min();
        break;
    case "QS" :
        Console.WriteLine("Queue current size is : {0}",queueCurrentSize);
        break;
    case "PQ" :
        Print_Queue();
        break;
    case "CQ":
        Clear_Queue();
        break;
    case "EXIT" :
        Console.WriteLine("Exiting");
        return;
    default :
        Console.WriteLine("Exiting due to some problem");
        return;
}

Here are the implementations of eah of these functions
1) Clearing the queue

private static void Clear_Queue()
{
    Console.WriteLine("Clearing the Queue");
    queueCurrentSize = 0;
}

2) Printing the queue

private static void Print_Queue()
{
    Console.WriteLine("Queue contains following elements");
    for(int i = 0; i < queueCurrentSize;i++)
    {
        Console.WriteLine("(Value : {0}, Priority : {1})", minQueue[i].value, minQueue[i].priority);
    }
}

3) Getting the minimum priority element

private static void Get_Min()
{
    if (queueCurrentSize > 0)
    {
        Console.WriteLine("The min priority element is : (Value : {0}, Priority : {1})", minQueue[0].value, minQueue[0].priority);
    }
    else
    {
        Console.WriteLine("The queue is empty");
    }
}

4) Extracting the minimum(or deleting the minimum priority element)

private static void Extract_Min()
{
    if (queueCurrentSize > 0)
    {
        Element minElement = minQueue[0];
        minQueue[0] = minQueue[queueCurrentSize - 1];
        queueCurrentSize = queueCurrentSize - 1;
        MaintainTopToButtomQueue();
        Console.WriteLine("The extracted min priority element is : (Value : {0}, Priority : {1})", minElement.value, minElement.priority);
    }
    else
    {
        Console.WriteLine("The queue is empty");
    }
}

private static void MaintainTopToButtomQueue()
{
    int parent,lowest,leftChild,rightChild;
    parent = 0;leftChild = 1;rightChild = 2;
    Element temp = new Element();
    while (leftChild < queueCurrentSize)
    {

        if (minQueue[parent].priority <= minQueue[leftChild].priority)
        {
            lowest = parent;
        }
        else
        {
            lowest = leftChild;
        }
        if (rightChild < queueCurrentSize && (minQueue[lowest].priority > minQueue[rightChild].priority))
        {
            lowest = rightChild;
        }

        if (lowest == parent)
        {
            break;
        }
        else
        {
            temp = minQueue[parent];
            minQueue[parent] = minQueue[lowest];
            minQueue[lowest] = temp;
            parent = lowest;
            leftChild = 2 * parent + 1;
            rightChild = 2 * parent + 2;
        }
    }
}

5) Inserting new elements

private static void Insert()
{
    if (queueCurrentSize < maxQueueSize)
    {
        int value, priority;
        string strValue, strPriority;
        Console.WriteLine("Please enter the details of the element(write exit to go to main queue options)");
        Console.Write("Value : ");
        while(true)
        {
            strValue = Console.ReadLine().Trim();
            if(strValue.Equals("exit",StringComparison.InvariantCultureIgnoreCase))
            {
                return;
            }
            else if(!int.TryParse(strValue,out value))
            {
                Console.WriteLine("Enter correctly please");
            }
            else
            {
                break;
            }
        }
        Console.Write("Priority : ");
        while (true)
        {
            strPriority = Console.ReadLine().Trim();
            if (strPriority.Equals("exit", StringComparison.InvariantCultureIgnoreCase))
            {
                return;
            }
            else if (!int.TryParse(strPriority, out priority))
            {
                Console.WriteLine("Enter correctly please");
            }
            else
            {
                break;
            }
        }
        Element element = new Element { value = value, priority = priority };
        queueCurrentSize = queueCurrentSize + 1;
        minQueue[queueCurrentSize - 1] = element;
        MaintainButtomToTopQueue();
    }
    else
    {
        Console.WriteLine("Queue is full, please extract some entries first");
    }
}

private static void MaintainButtomToTopQueue()
{
    int parent,child;
    child = queueCurrentSize-1;
    Element temp = new Element();
    while (child > 0)
    {
        parent = Convert.ToInt32(Math.Floor((1.0*child - 1) / 2));
        if(minQueue[parent].priority > minQueue[child].priority)
        {
            temp = minQueue[parent];
            minQueue[parent] = minQueue[child];
            minQueue[child] = temp;
            child = parent;
        }
        else
        {
            break;
        }
    }
}

we can add more functionalities to the queue like increasing/decreasing the size of the queue, performing the shorting, etc.