question archive Assume we are building a process scheduling system for an operating system
Assume we are building a process scheduling system for an operating system
Subject:Computer SciencePrice: Bought3
Assume we are building a process scheduling system for an operating system. After a process has been added to the scheduler's priority queue, we might want to adjust its priority later (for example, a system administrator might want to decrease the priority of a process started by a user - lower priority values mean the process gets more CPU time).
Take a look at the file Process.java, which implements an (extremely simplified) process. Each process contains a unique process ID and a priority. Two Process objects are equal if they have the same process ID, even if they have a different priority. The processes are comparable by their priority. This means that two Process instances may be equal according to their process ID, but one may be greater than the other, based on their priority. Take a look at the equals, hashCode, and compareTo methods in Process.java to understand how this is implemented.
Next, take a look at the file BinaryHeap.java implements a Binary Heap. In the main method, we create a number of processes and add them to a heap.
heap.insert(new Process("p1",20)); heap.insert(new Process("p2",40)); heap.insert(new Process("p3",30)); heap.insert(new Process("p4",10)); Finally we adjust the priority for process p2, forcing it to run next.
heap.insert(new Process("p2",5)); // decrease priority for p2 The heap array now looks like this:
[null, <p2,5>, <p4,10>, <p3,30>, <p2,40>, <p1,20>]
Even though p2 would be the next process to be run, we would still have a second copy of p2 left on the heap. This is not what we want.
Your task is to modify the class BinaryHeap so that, when insert is called with an object that is equal to one already in the heap, the old object should be replaced with the new one, and the position in the heap array should be adjusted. "Equal" in this case means that the objects are equal according to their equals and hashCode methods. However, the two objects might behave differently with respect to their compareTo methods, in which case the position of the position of the new item in the heap needs to change.
With the modified heap, using the same sequence of inserts as above, the heap array should look like this:
[null, <p2,5>, <p4,10>, <p3,30>, <p1,20>, null]
Additional instructions:
-The insert operation should still take only O(log N) time (N is the size of the heap). This means that you cannot search the heap to check if an item is already present.
-Use a Hash Map (java.util.HashMap), to record the current heap array position for each item in the heap. If an item is already present, insert the new object in place of the old one and then adjust the position for that item. Make sure to keep the Hash Map up-to-date on each heap operation.
-Do not change the signature of the BinaryHeap class or any of its methods. You can, of course, add methods and instance variables.
-You should be able to adjust the priority of an item in either direction (making the priority value smaller or larger).
import java.util.Arrays;
import java.util.HashMap;
public class BinaryHeap<T extends Comparable<? super T>> {
private static final int DEFAULT_CAPACITY = 100;
private int currentSize; // Number of elements in heap
private T[ ] array; // The heap array
private HashMap<T, Integer> itemToArrayIndex; // TODO: you will use this hashmap mapping keys to positions in the heap.
/**
* Construct the binary heap.
*/
public BinaryHeap( ) {
this( DEFAULT_CAPACITY );
}
/**
* Construct the binary heap.
* @param capacity the capacity of the binary heap.
*/
@SuppressWarnings("unchecked")
public BinaryHeap( int capacity ) {
currentSize = 0;
array = (T []) new Comparable[ capacity + 1 ];
itemToArrayIndex = new HashMap<>(); // empty heap, empty hashmap
}
/**
* Test if the priority queue is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return currentSize == 0;
}
/**
* Test if the priority queue is logically full.
* @return true if full, false otherwise.
*/
public boolean isFull( ) {
return currentSize == array.length - 1;
}
/**
* Make the priority queue logically empty.
*/
public void makeEmpty( ) {
currentSize = 0;
}
/**
* Insert into the priority queue, maintaining heap order.
* Duplicates are allowed.
* @param x the item to insert.
* @exception IndexOutOfBoundsException if container is full.
*/
public void insert(T x) throws IndexOutOfBoundsException {
// TODO:This method needs to be modified
if( isFull( ) )
throw new IndexOutOfBoundsException( );
int hole = ++currentSize;
//Percolate up
while (hole>1 && x.compareTo(array [hole /2]) <0 ) {
array[hole] = array[hole/2];
if (x.compareTo(array [hole /2]) <0)
hole /= 2;
}
array[ hole ] = x;
}
/**
* Find the smallest item in the priority queue.
* @return the smallest item, or null, if empty.
*/
public T findMin( ) {
if( isEmpty( ) )
return null;
return array[ 1 ];
}
/**
* Remove the smallest item from the priority queue.
* @return the smallest item, or null, if empty.
*/
public T deleteMin( ) {
if( isEmpty( ) )
return null;
T minItem = findMin( );
int index = currentSize;
array[ 1 ] = array[ currentSize-- ];
array[index] = null;
percolateDown( 1 );
return minItem;
}
/**
* Establish heap order property from an arbitrary
* arrangement of items. Runs in linear time.
*/
private void buildHeap( ) {
for( int i = currentSize / 2; i > 0; i-- )
percolateDown( i );
}
/**
* Internal method to percolate down in the heap.
* @param hole the index at which the percolate begins.
*/
private void percolateDown( int hole ) {
// TODO:This method needs to be modified
int child;
T tmp = array[ hole ];
for( ; hole * 2 <= currentSize; hole = child ) {
/* 4*/ child = hole * 2;
/* 5*/ if( child != currentSize &&
/* 6*/ array[ child + 1 ].compareTo( array[ child ] ) < 0 )
/* 7*/ child++;
/* 8*/ if( array[ child ].compareTo( tmp ) < 0 ){
/* 9*/ array[ hole ] = array[ child ];
} else
/*10*/ break;
}
/*11*/ array[ hole ] = tmp;
}
/**
* Get a string representation of the heap array.
* @return string representation of the array backing the this heap.
*/
public String printArray() {
return Arrays.asList(array).toString();
}
/**
* Get a string representation of the heap.
* @return a tree representing the tree encoded in this heap.
*/
public String printAsTree() {
StringBuilder sb = new StringBuilder();
printAsTree(sb,1);
return sb.toString();
}
/**
* Recursive internal method to assemble a tree
* string representing the heap.
*/
private void printAsTree(StringBuilder sb,int i) {
if (2*i <= currentSize) { // has left child
sb.append("(");
sb.append(array[i]);
sb.append(" ");
printAsTree(sb,2*i);
if ((2*i + 1) <= currentSize){ // has right child
sb.append(" ");
printAsTree(sb, 2*i+1);
}
sb.append(")");
} else {
sb.append(array[i]);
}
}
public static void main( String [ ] args ) {
BinaryHeap<Process> h = new BinaryHeap<>(10);
h.insert(new Process("p1",20));
System.out.println(h.printArray());
h.insert(new Process("p2",40));
System.out.println(h.printArray());
h.insert(new Process("p3",30));
System.out.println(h.printArray());
h.insert(new Process("p4",10));
System.out.println(h.printArray());
// Now change the priority of p2
h.insert(new Process("p2",5));
System.out.println(h.printArray());
}
}
public class Process implements Comparable<Process>{
public int priority;
public String name;
public Process(String name, int priority){
this.name = name;
this.priority = priority;
}
public int compareTo(Process other) {
return this.priority - other.priority;
}
public boolean equals(Object other) {
if (other instanceof Process) {
Process otherProcess = (Process) other;
return this.name.equals(otherProcess.name);
} else {
return false;
}
}
public int hashCode() {
return this.name.hashCode();
}
public String toString() {
return "<"+this.name+","+this.priority+">";
}
}
