Using the effect of the following operation sequence on the heap implementation
ID: 3692066 • Letter: U
Question
Using the effect of the following operation sequence on the heap implementation of the priority queue ADT. Using a heap, implement the priority queue class. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap and an array, data, that contains the heap with the entries.
class priorityQueue
{
private:
int size;
int *data;
public:
static const int CAPACITY = 50;
priorityQueue();//constructor
~priorityQueue();//destructor
int getParent(int index);
int getLeftChild(int index);
int getRightChild(int index);
void swap(int & item1, int & i);
void insert(int item); //enqueue - heap_insert
void printArray(int[]);
void heapify(int index);
//remove and return the smallest item currently in the priority queue
int extractMin();
//dequeue bool empty() const;
int min() const; //return the smallest item
};
int main()
{
priorityQueue myqueue;
if (myqueue.empty()) cout << "My priority Queue is empty " << endl;
myqueue.insert(59);
myqueue.insert(41);
myqueue.insert(25);
myqueue.insert(12);
myqueue.insert(91);
myqueue.min();
myqueue.extractMin();
myqueue.insert(34);
myqueue.insert(63);
myqueue.extractMin();
myqueue.insert(75);
myqueue.insert(85);
myqueue.extractMin();
cout << "Minimum value is ";
cout << myqueue.min() << endl;
system("pause");
return 0;
Explanation / Answer
priorityQueue::priorityQueue()
{
size = CAPACITY;
data = new int[size];
}
priorityQueue::~priorityQueue()
{
delete[] data;
}
int priorityQueue::getParent(int index)
{
return (index - 1) / 2;
}
int priorityQueue::getLeftChild(int index)
{
return (index + 1) * 2 - 1;
}
int priorityQueue:: getRightChild(int index)
{
return (index + 1) * 2;
}
void priorityQueue::swap(int &item1, int &i)
{
int temp = item1;
item1 = i;
i = temp;
}
void priorityQueue::siftUp(int nodeIndex) {
int parentIndex, tmp;
if (nodeIndex != 0) {
parentIndex = getParentIndex(nodeIndex);
if (data[parentIndex] > data[nodeIndex]) {
tmp = data[parentIndex];
data[parentIndex] = data[nodeIndex];
data[nodeIndex] = tmp;
siftUp(parentIndex);
}
}
}
void priorityQueue::insert(int value) {
if (size == 50)
throw string("Heap's underlying storage is overflow");
else {
size++;
data[Size - 1] = value;
siftUp(size - 1);
}
}
void priorityQueue::printArray(int a[])
{
cout << "Print Array A:" << endl;
int counter;
for (counter = 0; counter <a.length; counter++)
{
cout << a[counter] << " ";
}
cout << endl << endl;
}
void priorityQueue::heapify(int index)
{
int temp, l, r, heapify1;
l = getLeftChild(index);// getting the left child
r = getRightChild(index);// getting the right child
//if one of the children is bigger than the index
if((data[index] < data[l]) || (data[index]< Data[r]))
{
//if left is the bigger child
if(data[l] > data[r])
{
//swap parent with left child
temp = data[index];
data[index] = data[l];
data[l] = temp;
heapify1 = l; // index that was swapped
}
//if right is the bigger child
else
{
//swap parent with right child
temp = data[index];
data[index] = data[r];
data[r] = temp;
heapify1 = r; // index that was swapped
}
heapify(heapify1);
}
}
int priorityQueue::priorityQueue::min()
{
int minValue = data[0];
if ( empty() ){
return -1;
}
else
{
index= (index + 1) % size;
}
//find smallest value
for (int i = 0; i <= 50; i++){
if (data[i] < minValue)
minValue = data[i];
}
//return smallest value
return data[0];
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.