Homework SourseA priority queue is implemented as a linked list sorted from
Solution
A priority queue is different from a \"normal\" queue, because instead of being a \"first-in-first-out\" data structure, values come out in order by priority. A priority queue might be used, for example, to handle the jobs sent to the Computer Science Department\'s printer: Jobs sent by the department chair should be printed first, then jobs sent by professors, then those sent by graduate students, and finally those sent by undergraduates. The values put into the priority queue would be the priority of the sender (e.g., using 4 for the chair, 3 for professors, 2 for grad students, and 1 for undergrads), and the associated information would be the document to print. Each time the printer is free, the job with the highest priority would be removed from the print queue, and printed. (Note that it is OK to have multiple jobs with the same priority; if there is more than one job with the same highest priority when the printer is free, then any one of them can be selected.)
Enqueue:- it is the operation to place the new item at the tail of the queue.
Dequeue:- it is the operation to remove the next item from the head of the queue.
There are 2 methods of implementing the priority queues:
1) Array:- In standard linear array: 0 is the first element and array.length-1 is the last element. All objects removed would come from element 0. All objects added would go 1 past the last occupied slot. To implement this , when an object is removed, all the elements must be moved down by 1 spot.
Queue class ( array based)
class queuearray
{
private object[] queue;
private int start, end;
public Queuearray(int size)
{
queue= new object[size];
start=end=-1;
}
public boolean enqueue(object data);
public object dequeue();
public void clear();
public boolean isEmpty();
public boolean isFull();
}
// Enqueue method array based
public boolean enqueue(object data)
{
if(((end+1)%queue.length)==start)
return false; //queue is full
// move the end of the queue and add the element
end=(end+1)%queue.length;
queue[end]=data;
if(start==-1){start = 0;}
return true;
}
// Dequeue method array based
public object dequeue()
{
if (start==-1)
return null ; // empty list
// get the object , update the start, and retuen the object\'
object tmp= queue[start];
if (start==end)
start=end=-1;
else
start=(start+1)%queue.length;
return tmp;
}
A heap is a binary tree (in which each node contains a Comparable key value), with two special properties:
The ORDER property:
The SHAPE property:
The classic way to implement a priority queue is using a data structure called a binary heap. A binary heap will allow us both enqueue and dequeue items in O(logn) O(log n).The binary heap has two common variations: the min heap, in which the smallest key is always at the front, and the max heap, in which the largest key value is always at the front.
The basic operations we will implement for our binary heap are as follows:
Insertion of a new element into a heap is done in two steps. First the element is inserted in the only place with room for it,- At the bottom of the tree, - And next it is shifted up the tree until the heap property holds. The insertion is trivial, but the siftup deserves extra attention because of its importance for the performance. In C it can be implemented for example in this way.
void siftup(index c)
{
while(c!=root &&data[parent(c)]<data[c])
{
swap( &data[parent(c)], &data[c]);
c=parent(c);
}
}
Deletion of the maximum element from the heap must find an element to replace the maximum element (in the root). As for insertion this is done in to steps. First the maximum element (the root) is replaced with the last element of the heap, and next the new root is shifted down the tree along the path of the largest children. In C the siftdown operation can be described like this
void siftdown (index p)
{
index c;
for( c=child(p); c<n;p=c,c=child(p))
{
if( data[c]<data[c+1])c=c+1;
if (data[p]<data[c]) swap(&data[p], &data[c])
else return;
};
if(c==n &&(data[p]<data[c]))
swap(&data[p], &data[c]);
};
The major problem with the queue implemented using array is, It will work for only fixed number of data. That means, the amount of data must be specified in the beginning itself. Queue using array is not suitable when we don\'t know the size of data which we are going to use. A queue data structure can be implemented using linked list data structure. The queue which is implemented using linked list can work for unlimited number of values. That means, queue using linked list can work for variable size of data (No need to fix the size at beginning of the implementation). The Queue implemented using linked list can organize as many data values as we want.
To implement queue using linked list, we need to set the following things before implementing actual operations.
enQueue(value) - Inserting an element into the Queue
We can use the following steps to insert a new node into the queue...
deQueue() - Deleting an Element from Queue
We can use the following steps to delete a node from the queue...
display() - Displaying the elements of Queue
We can use the following steps to display the elements (nodes) of a queue...
when binary heap is used to implement a priority queue, both insert and pull can be done on O (LogN) worst case time. Insert has an average of constant time. To build the heap from already exist N items, it takes o(N) worst case time.
