Java - Priority Queue The Question: Here is the code: --------------------------
ID: 3573333 • Letter: J
Question
Java - Priority Queue
The Question:
Here is the code:
---------------------------------------------------------------------------------------
Implement a priority queue class based on the max-heap class implementa- tion of Figure 5.19. The following methods should be supported for manip- ulating the priority queue void enqueue (int objectID int priority) int de queue void changeweight (int Object ID int newPriority); Method enqueue inserts a new object into the priority queue with ID num- ber Object ID and priority priority. Method dequeue removes the object with highest priority from the priority queue and returns its object ID Method changeweight changes the priority of the object with ID number Object ID to be newPriority. The type for E should be a class that stores the object ID and the priority for that object. You will need a mech- anism for finding the position of the desired object within the heap. Use an array, storing the object with ObjectID i in position i. (Be sure in your testing to keep the ObjectIDS within the array bounds.) You must also modify the heap implementation to store the object's position in the auxil iary array so that updates to objects in the heap can be updated as well in the arrayExplanation / Answer
DUtill.java
import java.util.*;
import java.math.*;
/** A bunch of utility functions. */
class DSutil<E> {
/** Swap two Objects in an array
@param A The array
@param p1 Index of one Object in A
@param p2 Index of another Object A
*/
public static <E> void swap(E[] A, int p1, int p2) {
E temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the Objects in an array.
@param A The array
*/
// int version
// Randomly permute the values of array "A"
static void permute(int[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
public static void swap(int[] A, int p1, int p2) {
int temp = A[p1];
A[p1] = A[p2];
A[p2] = temp;
}
/** Randomly permute the values in array A */
static <E> void permute(E[] A) {
for (int i = A.length; i > 0; i--) // for each i
swap(A, i-1, DSutil.random(i)); // swap A[i-1] with
} // a random element
/** Initialize the random variable */
static private Random value = new Random(); // Hold the Random class object
/** Create a random number function from the standard Java Random
class. Turn it into a uniformly distributed value within the
range 0 to n-1 by taking the value mod n.
@param n The upper bound for the range.
@return A value in the range 0 to n-1.
*/
static int random(int n) {
return Math.abs(value.nextInt()) % n;
}
}
MaxHeap.java
import java.lang.Comparable;
/** Max-heap implementation */
public class MaxHeap<E extends Comparable<? super E>> {
private E[] Heap; // Pointer to the heap array
private int size; // Maximum size of the heap
private int n; // Number of things in heap
/** Constructor supporting preloading of heap contents */
public MaxHeap(E[] h, int num, int max)
{ Heap = h; n = num; size = max; buildheap(); }
/** @return Current size of the heap */
public int heapsize() { return n; }
/** @return True if pos a leaf position, false otherwise */
public boolean isLeaf(int pos)
{ return (pos >= n/2) && (pos < n); }
/** @return Position for left child of pos */
public int leftchild(int pos) {
assert pos < n/2 : "Position has no left child";
return 2*pos + 1;
}
/** @return Position for right child of pos */
public int rightchild(int pos) {
assert pos < (n-1)/2 : "Position has no right child";
return 2*pos + 2;
}
/** @return Position for parent */
public int parent(int pos) {
assert pos > 0 : "Position has no parent";
return (pos-1)/2;
}
/** Insert val into heap */
public void insert(E val) {
assert n < size : "Heap is full";
int curr = n++;
Heap[curr] = val; // Start at end of heap
// Now sift up until curr's parent's key > curr's key
while ((curr != 0) && Heap[curr]!=null&&
(Heap[curr].compareTo(Heap[parent(curr)]) > 0)) {
DSutil.swap(Heap, curr, parent(curr));
curr = parent(curr);
}
}
/** Heapify contents of Heap */
public void buildheap()
{ for (int i=n/2-1; Heap[i]!=null&&i>=0; i--) siftdown(i); }
/** Put element in its correct place */
private void siftdown(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
while (!isLeaf(pos)) {
int j = leftchild(pos);
if ((j<(n-1)) && (Heap[j].compareTo(Heap[j+1]) < 0))
j++; // j is now index of child with greater value
if (Heap[pos].compareTo(Heap[j]) >= 0) return;
DSutil.swap(Heap, pos, j);
pos = j; // Move down
}
}
/** Remove and return maximum value */
public E removemax() {
assert n > 0 : "Removing from empty heap";
DSutil.swap(Heap, 0, --n); // Swap maximum with last value
if (n != 0) // Not on last element
siftdown(0); // Put new heap root val in correct place
return Heap[n];
}
/** Remove and return element at specified position */
public E remove(int pos) {
assert (pos >= 0) && (pos < n) : "Illegal heap position";
if (pos == (n-1)) n--; // Last element, no work to be done
else
{
DSutil.swap(Heap, pos, --n); // Swap with last value
// If we just swapped in a big value, push it up
while ((pos > 0) &&
(Heap[pos].compareTo(Heap[parent(pos)]) > 0)) {
DSutil.swap(Heap, pos, parent(pos));
pos = parent(pos);
}
if (n != 0) siftdown(pos); // If it is little, push down
}
return Heap[n];
}
public int search(int objectId)
{
for(int i=0;i<Heap.length;i++)
{
Node h=(Node)Heap[i];
if(h.objectId==objectId)
{
return i;
}
}
return -1;
}
}
Node.java
public class Node implements Comparable{
int objectId;
int priority;
@Override
public int compareTo(Object o) {
// TODO Auto-generated method stub
Node arg0=(Node) o;
return priority>arg0.priority?1:(priority==arg0.priority)?0:-1;
}
}
PriorityQueue.java
public class Node implements Comparable{
int objectId;
int priority;
@Override
public int compareTo(Object o) {
// TODO Auto-generated method stub
Node arg0=(Node) o;
return priority>arg0.priority?1:(priority==arg0.priority)?0:-1;
}
}
Operation.java
public class Operation {
public static void main(String args[])
{
PriorityQueue pq;
pq=new PriorityQueue();
pq.enqueue(12, 1);
pq.enqueue(10, 2);
pq.enqueue(9, 3);
pq.enqueue(8, 4);
pq.enqueue(7, 5);
System.out.println("Values"+pq.dequeue()+pq.dequeue()+pq.dequeue());
pq.enqueue(6, 5);
System.out.println(pq.dequeue());
pq.changeWeight(12, 5);
System.out.println(pq.dequeue());
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.