Problem in C++ a. Write the definition of the class template to define the prior
ID: 3571635 • Letter: P
Question
Problem in C++
a. Write the definition of the class template to define the priority queues,
as discussed in this chapter as an abstract data type (ADT).
b. Write the definitions of the function templates to implement the
operations of the priority queues as defined in part (a).
Basically they want us to use to heap algorithm to implement the ADT class
priorityQueue.
Problem 12 from Pg. 596 in Using Data Structures with C++ By D.S. Malik
Please let me know if you have any questions.
Below is the heap algorithm,some details from the book, and the class Template provided for queues.
==========Heap Algorithm===========
template
void arrayListType::heapSort()
{
elemType temp;
buildHeap();
for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0;
lastOutOfOrder--)
{
temp = list[lastOutOfOrder];
list[lastOutOfOrder] = list[0];
list[0] = temp;
heapify(0, lastOutOfOrder - 1);
}//end for
}//end heapSort
===================Details===================
We can write algorithms similar
to the ones used in the function heapify to insert an element in the priority queue
(addQueue operation), and remove an element from the queue (deleteQueue operation).
The next two sections describe these algorithms.
INSERT AN ELEMENT IN THE PRIORITY QUEUE
Assuming the priority queue is implemented as a heap, we perform the following steps:
1. Insert the new element in the first available position in the list. (This
ensures that the array holding the list is a complete binary tree.)
2. After inserting the new element in the heap, the list might no longer be
a heap. So to restore the heap:
while (the parent of the new entry is smaller than the new entry)
swap the parent with the new entry.
1
0
Priority Queues (Revisited) | 575
Notice that restoring the heap might result in moving the new entry to the root node.
REMOVE AN ELEMENT FROM THE PRIORITY QUEUE
Assuming the priority queue is implemented as a heap, to remove the first element of the
priority queue, we perform the following steps:
1. Copy the last element of the list into the first array position.
2. Reduce the length of the list by 1.
3. Restore the heap in the list.
The other operations for priority queues can be implemented in the same way as
implemented for queues. We leave the implementation of the priority queues as an
exercise for you; see Programming Exercise 12 at the end of this chapter.
===========Template class for queues==============
//*************************************************************
// Author: D.S. Malik
//
// This class specifies the basic operations on a queue.
//*************************************************************
template
class queueADT
{
public:
virtual bool isEmptyQueue() const = 0;
//Function to determine whether the queue is empty.
//Postcondition: Returns true if the queue is empty,
// otherwise returns false.
virtual bool isFullQueue() const = 0;
//Function to determine whether the queue is full.
//Postcondition: Returns true if the queue is full,
// otherwise returns false.
virtual void initializeQueue() = 0;
//Function to initialize the queue to an empty state.
//Postcondition: The queue is empty.
virtual Type front() const = 0;
//Function to return the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the first element of the queue
// is returned.
virtual Type back() const = 0;
//Function to return the last element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: If the queue is empty, the program
// terminates; otherwise, the last element of the queue
// is returned.
virtual void addQueue(const Type& queueElement) = 0;
//Function to add queueElement to the queue.
//Precondition: The queue exists and is not full.
//Postcondition: The queue is changed and queueElement is
// added to the queue.
virtual void deleteQueue() = 0;
//Function to remove the first element of the queue.
//Precondition: The queue exists and is not empty.
//Postcondition: The queue is changed and the first element
// is removed from the queue.
};
Explanation / Answer
Part (a)
Abstract Data Type:
Abstract data type or ADT is defined as a set of objects together with a specified amount of operation.
Priority queue is a data type having following operation:
1. Insert an element with assigned priority
2. Return the element with highest priority
3. Delete the element with highest priority
Part (b)
Operations in Priority queue
1. Here the data type T compares the priorities assigned to the elements. Hence, consider the case for any two elements a,b, using T we can test a<b, hence, get the comparison of the elements.
2. At the time of inserting new element in the priority queue, we have to assign a priority of the element.Hence, queue stores the two items, one is element itself and the assocated priority with the element.
In the first method priority can be find by the comparison, but the second method is more useful.
Code:
public class SequenceSimplePriorityQueue implements SimplePriorityQueue {
protected Sequence seq = new NodeSequence();
protected Comparator com;
protected Object extractKey (Position ps) {
return ((item)ps.element()).key();
}
protected Object extractElem (Position ps) {
return ((item)ps.element()).element();
}
public SequenceSimplePriorityQueue (Comparator c) {
this.com = c; }
public int size () {return seq.size(); }
public boolean isEmpty () { return seq.isEmpty(); }
public void insertItem (Object k, Object e) throws InvalidKeyException {
if (!com.isComparable(k))
throw new InvalidKeyException("The key is not valid");
else
if (seq.isEmpty())
seq.insertFirst(new Item(k,e));
else
if (comp.isGreaterThan(k,extractKey(seq.last())))
seq.insertAfter(seq.last(),new Item(k,e));
else {
Position cur = seq.first();
while (com.isGreaterThan(k,extractKey(cur)))
cur = seq.after(cur);
seq.insertBefore(cur,new item(k,e));
}
}
public Object minElement () throws
EmptyContainerException {
if (seq.isEmpty())
throw new EmptyContainerException("The priority queue is empty");
else
return extractElem(seq.first());
}
Part(c)
Implement priority queue using heaps
Add an element
void add (const T & info)
{
size=size+1;
a[size]=info;
CheckheapProperty(size);
}
void CheckheapProperty(int ps)
{
if(ps >1 && a[pos]> a[pos/2])
{
swap(a,ps,ps/2);
CheckheapProperty(ps/2);
}
}
void swap (int a, int b, int c)
{
a=b;
b=c;
c=a;
}
Remove an element
void delete()
{
swap(a,1,size);
size=size-1;
CheckheapProperty(1);
}
void CheckheapProperty(int ps)
{
if(2*ps<=size)
i=ps;
if(a[i]>a[ps])
{
swap(a,i,ps);
CheckheapProperty(i);
}
}
}
void swap (int a, int b, int c)
{
a=b;
b=c;
c=a;
}
Code:
struct node
{
int priority;
int info;
struct node *next;
}
class queueADT
{
private:
node *front;
public:
virtual bool isEmptyQueue() const = 0;
{
if(pq.isEmpty())
{
return true;
}
else
{
return false;
}
}
virtual bool isFullQueue() const = 0;
{
if(front==last)
{
return true;
}
else
{
return false;
}
}
virtual void initializeQueue() = 0;
{
PriorityQueue<int> pq;
}
virtual Type front() const = 0;
{
int first = pq.front();
}
virtual Type back() const = 0;
{
int last = pq.back();
}
virtual void enqueue(const Type& queueElement) = 0;
{
pq.enqueue(value, priority);
}
virtual void dequeue() = 0;
{
int first=pq.dequeue();
}
};
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.