Code Destine

Problem Statement

Design a Minimum/Maximum PriorityQueue data structure using Binary Heap data structure. The Queue data structure will supports the following operations:

1. enqueue(N) :- It insert element N to the back of the queue.
2. dequeue() :- It removes and returns the maximum/minimum element of the queue.
3. peek() :- It returns (not remove) the maximum/minimum element of the queue.
4. isEmpty() :- It checks whether the queue is empty.
5. size() :- It return the total number of elements.

Example 

PriorityQueue pq = new PriorityQueueBH<>(true);
pq.enqueue(20);
pq.enqueue(10);
pq.enqueue(30);
pq.peek();    // return 10
pq.dequeue(); // return 10
pq.size();    // return 2

Solution

The most optimal way of designing a PriorityQueue data structure is by using a Binary Heap data structure.

A Binary Heap is a heap data structure that takes the form of a complete binary tree with two additional constraints:

1. Complete Tree: All levels of the binary tree should be fully filled except possibly the last level and if the last level is not complete, the nodes of the last level should be filled from left to right.
2. Heap Property: A Binary Heap can be a Min Heap or Max Heap. In a Min Heap, the root of any subtree must be less than or equal to its immediate children, Therefore making the root node the smallest among all the nodes of the Binary Heap. The Max Heap is similar to Min Heap with a difference is that the root node is greatest among all the nodes of the Binary Heap.

A Binary Heap can be represented by an array. Heap property of the array must be maintained when a new element is added or an element is removed from the array, to maintain this heap property following operations are to be performed:

1. Swim: This operation is performed when a new element is added at the end of the array. Here we recursively check if its value is less than its parent or not (Min Heap) if true, then we swap the position of the new element with its parent.
2. Sink: This operation is performed when a new element is added at the start of the array. Here we recursively check if its value is greater than its children or not (Min Heap) if true, then we swap the position of the new element with its child (a child whose value is greater among the two children).

In the context of the PriorityQueue data structure, its each operation will work in the following way:

1. enqueue(N) :- It inserts an element N in the array list and performs the swim operation to maintain the heap property.
2. dequeue() :- It swaps the last element with the first element of the array and removes and returns the new last element of the array. In the end, it performs the sink operation to maintain the heap property.
3. peek() :- It returns the first element of the array list (index 1).
4. isEmpty() :- If the size of the array list is less than or equal to 1, then return true otherwise return false.
5. size() :- It returns the size of the array list -1 as value (null is inserted in the first position).

PriorityQueue Interface

public interface PriorityQueue<T> {

	public void enqueue(T t);
	
	public T dequeue();
	
	public boolean isEmpty();
	
	public int size();
	
	public T peek();
	
}

PriorityQueue Implementation

import java.util.ArrayList;
import java.util.List;

public class PriorityQueueBH<T extends Comparable<T>> implements PriorityQueue<T> {

	private boolean MIN = false;
	private List<T> list;
	
	public PriorityQueueBH() {
		this.list = new ArrayList<T>();
		this.list.add(null);
	}
	
	public PriorityQueueBH(boolean MIN) {
		this();
		this.MIN = true;
	}
	
	@Override
	public void enqueue(T t) {
		this.list.add(t);
		swim();
	}
	
	private void swim(){
		int n = this.list.size()-1;
		while(n >1 && check(this.list.get(n/2),this.list.get(n))){
			swap(n/2,n);
			n = n/2;
		}
	}

	@Override
	public T dequeue() {
		if(!isEmpty()) {
			T t = this.list.get(1);
			swap(1,this.list.size()-1);
			this.list.remove(this.list.size()-1);
			sink(1);
			return t;
		}
		return null;
	}
	
	@Override
	public T peek() {
		if(!isEmpty()) {
			return this.list.get(1);
		}
		return null;		
	}
	
	private void sink(int n){
		int j;
		while(n*2 <= this.list.size()-1){
			j = n*2;
			if(j < this.list.size()-1 && check(this.list.get(j),this.list.get(j+1)))
				j++;
			if(!check(this.list.get(n),this.list.get(j)))
				break;
			swap(j,n);
			n = j;
		}
	}

	@Override
	public boolean isEmpty() {
		return list.size()<=1;
	}

	@Override
	public int size() {
		return this.list.size()-1;
	}

	private boolean check(Comparable t1, Comparable t2){
		if(MIN){
			return t1.compareTo(t2)>0;
		}else{
			return t1.compareTo(t2)<0;
		}
	}
	
	private void swap(int i, int j){
		T swap = this.list.get(i);
		this.list.set(i, this.list.get(j));
		this.list.set(j, swap);
	}
}

Similar Post

1. Next Greater Element
2. Relative Ranks
3. Valid Parentheses

That’s all for Design PriorityQueue using Binary Heap Algorithm in Java, If you liked it, please share your thoughts in a comments section and share it with others too.