This is an implementation of the priority queue abstract data structure based on the min-heap. Furthermore, the min-heap uses an array for structuring its internal nodes. That said, the add( ) and removeMin( ) operations have a logarithmic runtime complexity, O( log n ), whereas the min( ) operation has a constant runtime complexity, O( 1 ) (as it does not remove the minimum element from the heap, but it just returns it). Finally, the implementation is as follows (do note that this implementation only works with non-negative integers):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
/** Priority Queue implementation based on Min-Heap */
public class PriorityQueue {
private final int MAX_SIZE;
private static final int DEFAULT_SIZE = 1024;
private static final int ROOT = 1;
private static final int NULL = -1;
private int[ ] array;
private int lastIndex = ROOT;
/** Constructs a priority queue with the specified size */
public PriorityQueue( int size ) {
MAX_SIZE = size;
array = new int[ MAX_SIZE ];
java.util.Arrays.fill( array, NULL );
}
/** Constructs a priority queue with the default size */
public PriorityQueue() {
this( DEFAULT_SIZE );
}
/** Adds a new element to the array while maintaining the min-heap property */
public void add( int element ) {
if( element < 0 || lastIndex == MAX_SIZE ) {
return;
}
int elementIndex = lastIndex++;
array[ elementIndex ] = element;
while( array[ elementIndex ] < array[ parent( elementIndex ) ] ) {
swap( elementIndex, parent( elementIndex ) );
elementIndex = parent( elementIndex );
}
}
/** Returns the parent index */
private int parent( int index ) {
return index / 2;
}
/** Returns the left child index */
private int leftChild( int index ) {
return 2 * index;
}
/** Returns the right child index */
private int rightChild( int index ) {
return 2 * index + 1;
}
/** Returns the smallest child index */
private int minChild( int index ) {
int leftChildIndex = leftChild( index );
int rightChildIndex = rightChild( index );
if( leftChildIndex >= MAX_SIZE && rightChildIndex >= MAX_SIZE ) return NULL;
else if( rightChildIndex >= MAX_SIZE ) return leftChildIndex;
if( array[ leftChildIndex ] == NULL && array[ rightChildIndex ] == NULL ) return NULL;
else if( array[ rightChildIndex ] == NULL ) return leftChildIndex;
return array[ leftChildIndex ] <= array[ rightChildIndex ] ? leftChildIndex : rightChildIndex;
}
/** Returns the minimum element from the heap */
public int min() {
return array[ ROOT ];
}
/** Returns and removes the minimum element from the heap */
public int removeMin() {
int rootElement = array[ ROOT ];
int elementIndex = --lastIndex;
int element = array[ elementIndex ];
array[ ROOT ] = element;
array[ elementIndex ] = NULL;
elementIndex = ROOT;
for( int minChildIndex; ( ( minChildIndex = minChild( elementIndex ) ) != NULL )
&& ( array[ elementIndex ] > array[ minChildIndex ] ); ) {
swap( elementIndex, minChildIndex );
elementIndex = minChildIndex;
}
return rootElement;
}
/** Checks if the heap is empty */
public boolean isEmpty( ) {
return lastIndex == ROOT;
}
/** Helper method for swapping elements in the array */
private void swap( int a, int b ) {
int temp = array[ a ];
array[ a ] = array[ b ];
array[ b ] = temp;
}
@Override
public String toString( ) {
StringBuffer sb = new StringBuffer( "[" );
for( int i = 1; i < lastIndex; i++ ) {
sb.append( array[ i ] );
if( i + 1 < lastIndex ) sb.append( ", " );
}
sb.append( "]" );
return sb.toString( );
}
}
|
And for your testing needs I was so nice as to supply you with the following JUnit test (I’ll try not to make a habit out of it 
):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.Random;
import java.util.Date;
public class PriorityQueueTest {
@Test
public void BasicTest( ) {
PriorityQueue instance = new PriorityQueue( );
for( int i = 0; i != 10; i++ ) {
instance.add( i );
}
for( int i = 0; i != 10; i++ ) {
assertEquals( i, instance.removeMin( ), 0.0 );
}
}
@Test
public void StressTest( ) {
java.util.PriorityQueue<Integer> queue = new java.util.PriorityQueue<Integer>( );
PriorityQueue myQueue = new PriorityQueue( );
Random random = new Random( new Date( ).getTime( ) );
for( int i = 0; i < 1000; i++ ) {
int item = random.nextInt( 1000 );
queue.offer( item );
myQueue.add( item );
}
for( int i = 0; i < 1000; i++ ) {
if( i % 2 == 0 ) {
assertEquals( queue.poll( ), myQueue.removeMin( ), 0.0 );
} else {
assertEquals( queue.peek( ), myQueue.min( ), 0.0 );
}
}
}
@Test
public void testIsEmpty( ) {
PriorityQueue instance = new PriorityQueue( );
boolean expResult = true;
boolean result = instance.isEmpty( );
assertEquals( expResult, result );
}
@Test
public void testGetMin( ) {
PriorityQueue instance = new PriorityQueue( );
float expResult = -1;
float result = instance.min( );
assertEquals( expResult, result, 0.0 );
}
@Test
public void testRemoveMin( ) {
PriorityQueue instance = new PriorityQueue( );
float expResult = -1;
float result = instance.removeMin( );
assertEquals( expResult, result, 0.0 );
}
}
|
My1OOInterview 