java Priority Queue A priority queue operates differently than a regular queue a
ID: 3857168 • Letter: J
Question
java Priority Queue
A priority queue operates differently than a regular queue as it allows some elements to move through the queue more quickly than others. The classic example of a priority queue is a hospital emergency room where the sickest patients are the first to see the doctor even if a less sick patient has been waiting longer
Since a queue’s primary responsibility is determining the next element to be dequeued it must do so very efficiently. In a priority queue this can be tricky as we want to avoid examining every element in the queue when an element is enqueued or dequeued (this is considered inefficient). Thus, one common way to store a priority queue that does this efficiently is a heap
A heap is an array representation of a binary tree (a tree where every node has at most two children) such that each subtree of the tree has the heap property. The heap property is that the root of a tree is greater (has a higher priority) than any of the other elements in the subtree. Even though it is a binary tree, a heap is always stored as an array. The children of an element at index i in array are stored at indices 2i and 2i + 1. The parent of i can be found at index bi/2c.
For example, in the heap in Figure 2 the root is node containing 9, which is also the largest element in the array. It is stored as position 0 in the array representation of the heap. It has two children6 and 7 stored at positions 1 and 2 in the array which are bigger than all their children (they are the largest in their respective subtrees). It leaves are 4, 2 and 5.
The trick to a heap is adding and removing elements while preserving the heap property. There are two methods that do this: heapify and reverseHeapify. Whenever an element is altered a call to one of these methods will restore the heap property. If the element altered is an internal node of the tree (a node with one or more children) then heapify should be called. If it is a leaf of the tree (a node with no children) then reverseHeapify should be called.
heapify works by comparing the current internal node with its children to see which is the largest. If the root is not the largest then it is swapped with the largest of its children. Since the child has now been altered it needs to check to make sure it still satisfies the heap property. heapify works its way down the tree in this manner and, when it is complete, the tree should again be a heap. The details of how heapify works are a little complex but the method is provided for you, you just need to understand when to use it, which we will discuss a bit more below.
reverseHeapify works by comparing the current node with its parent. It the current node is larger than its parent then it swaps itself with its parent. The parent still might not be correct, it now needs to compare its parent with its grand parent, and so on, until it reaches the top of the tree. reverseHeapify is easy to implement using a while loop which keeps going until parent is larger than the child. While the parent is smaller than the child it swaps the parent with the child and makes then moves up to the parent (so that the parent will become the child during the next iteration of the loop). We will discuss when to use reverseHeapify a bit more below
Class PriorityQueue
The priority of a Job is determined by the owner of the Job. Job has a method getOwner that returns a number 0, 1 or 2 indicating the owner. The higher the number of the owner the higher the priority of the Job. There will likely be many Jobs with the same priority.
Since we are using a heap (a type of array) we don’t need to keep track of the head like in a linked-list queue. This is because it is always position 0 in the array. However, we do need to keep track of atail. The tail is the position after the last used position in the array. Thus, the tail of an empty queue will be at position 0.
Included with the assignment is a skeleton the the class. Some of the methods needed by the heap have been implemented for you. Methods left, right and parent give the index of the left child, right child and parent respectively of an index i. The method swap swaps two elements of the array. heapify is also implemented for you. Also, the constructor has been implemented for you already, there is no need to modify it.
You will need to implement the queue methods: isEmpty, enqueue, dequeue and clear. You will also need to implement reverseHeapify. Since a heap is an array, you will also need to implement resize, which doubles the size of the array just like in Assignment #1.
enqueue adds an element to the end of the heap (the tail). Since the heap is stored as an array, this simply means adding an element at the tail and incrementing the tail. However, we must ensure that the heap property is maintained. Since the last element in the heap cannot have any children it must be a leaf so we can call reverseHeapify to enforce the heap property. Also, if the heap is too small to add a new element, we must call resize before adding the element.
dequeue removes the first element in the heap and returns it. The challenge is that we cannot leave the beginning of the array empty. We cannot shift the other elements forward either, not only is this inefficient but it will also destroy the heap property. The trick is to realize that we can replace the first element with absolutely any element in the heap so long as heapify is called. There is only one element that can be moved without destroying the heap property: the last element. Thus, we swap the first element and the last element of heap, remove and return the last element and then call heapify on the first element.
class Job:public class Job
{
public static final int APPLICATION = 0;
public static final int USER = 1;
public static final int SYSTEM = 2;
private int owner;
private int duration;
private int id;
private static int currentId = 0;
public Job(int owner, int duration)
{
this.owner = owner;
this.duration = duration;
this.id = currentId ++;
}
public int getId()
{
return this.id;
}
public int getOwner()
{
return this.owner;
}
public int getDuration()
{
return this.duration;
}
public void run(int time)
{
this.duration -= time;
if (this.duration < 0)
{
this.duration = 0;
}
try
{
if (time > duration)
{
Thread.sleep(time);
}
else
{
Thread.sleep(duration);
}
}
catch (Exception e)
{
// Do nothing
}
}
public boolean equals(Job other)
{
return this.getId() == other.getId();
}
public String toString()
{
StringBuffer result = new StringBuffer();
result.append("Job ");
result.append(getId());
result.append(" owned by ");
switch(getOwner())
{
case SYSTEM: result.append("the system "); break;
case USER: result.append("the user "); break;
case APPLICATION: result.append("an application "); break;
default: result.append(" ERROR "); break;
}
result.append("has ");
result.append(duration);
result.append(" microseconds remaining;");
return result.toString();
}
}
class PriorityQueue
public class PriorityQueue implements Queue
{
private Job[] heap;
private int tail;
public PriorityQueue()
{
heap = new Job[10];
tail = 0;
}
public boolean isEmpty()
{
// TODO Implement this method
return true; // Dummy return values; please remove
}
public void enqueue(Job element)
{
// TODO Implement this method
}
public Job dequeue()
{
// TODO Implement this method
return null; // Dummy return value; please remove
}
public void clear()
{
// TODO Implement this method
}
private void resize()
{
// TODO Implement this method
}
private void reverseHeapify(int i)
{
// TODO Implement this method
}
private int parent(int i)
{
return (int) Math.floor((i - 1) / 2.0f);
}
private int left(int i)
{
return 2 * i + 1;
}
private int right(int i)
{
return 2 * i + 2;
}
private void swap(int i, int j)
{
Job temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private void heapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < tail &&
heap[l].getOwner() > heap[largest].getOwner())
{
largest = l;
}
if (r < tail &&
heap[r].getOwner() > heap[largest].getOwner())
{
largest = r;
}
if (largest != i)
{
swap(i, largest);
heapify(largest);
}
}
}
Explanation / Answer
class PriorityQueue
{
private Job[] heap;
private int tail;
public PriorityQueue()
{
heap = new Job[10];
tail = 0;
}
public boolean isEmpty()
{
return tail == 0;
}
public void enqueue(Job element)
{
heap[tail++] = element;
reverseHeapify(tail);
}
public Job dequeue()
{
Job temp = heap[0];
heap[0] = heap[--tail];
heapify(0);
return temp;
}
public void clear()
{
heap = new Job[10];
tail = 0;
}
private void resize()
{
Job[] newHeap = new Job[tail*2];
System.arraycopy(heap, 0, newHeap, 0, tail);
heap = newHeap;
}
private void reverseHeapify(int i)
{
if (i > 0)
if (heap[parent(i)].getOwner() < heap[i].getOwner()) {
swap(i, parent(i));
reverseHeapify(parent(i));
}
}
private int parent(int i)
{
return (int) Math.floor((i - 1) / 2.0f);
}
private int left(int i)
{
return 2 * i + 1;
}
private int right(int i)
{
return 2 * i + 2;
}
private void swap(int i, int j)
{
Job temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private void heapify(int i)
{
int l = left(i);
int r = right(i);
int largest = i;
if (l < tail &&
heap[l].getOwner() > heap[largest].getOwner())
{
largest = l;
}
if (r < tail &&
heap[r].getOwner() > heap[largest].getOwner())
{
largest = r;
}
if (largest != i)
{
swap(i, largest);
heapify(largest);
}
}
}
Let me know if you get any error. I dont have the Job class so cant check the code! I hope you understand
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.