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
Post a Comment