Project1Project1(don\'t do this project): Using a heap, implementation the prior
ID: 3764117 • Letter: P
Question
Project1Project1(don't do this project): Using a heap, implementation the priority queue class from section 8.4. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap (as in the solution of Self-Test Exercise 2) and an array, data that contains the heap with the entries. We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which data[i] was added to the queue. For example, if entry[7] was the 33rd item added to the priority queue, the order[7] would be 33. When you are comparing two entries with equal priority, use the order number to "break the tie" (so that if two entries have the same priority number, then the one with the earlier order number, then the one with the earlier order number will come out of the priority queue first). -Project2(do this): Repeat Project1, with no predefined limit on the size of the heap. Use a dynamic array.(don't do this project): Using a heap, implementation the priority queue class from section 8.4. The class should have a static constant member variable, CAPACITY, which is the maximum size of the heap (as in the solution of Self-Test Exercise 2) and an array, data that contains the heap with the entries. We also want to have FIFO behavior for entries with equal priority. To obtain this behavior, the class should have an extra private member variable that is an array, order, where order[i] contains the order in which data[i] was added to the queue. For example, if entry[7] was the 33rd item added to the priority queue, the order[7] would be 33. When you are comparing two entries with equal priority, use the order number to "break the tie" (so that if two entries have the same priority number, then the one with the earlier order number, then the one with the earlier order number will come out of the priority queue first). -Project2(do this): Repeat Projectl, with no predefined limit on the size of the heap. Use a dynamic array.Explanation / Answer
#include <iostream>
using namespace std;
class PriorityQueue{
private:
static const int CAPACITY = 10;
int data[CAPACITY];
int order[CAPACITY];
int pos;
int entered;
public:
PriorityQueue(){
pos = 1;
entered = 0;
int i =0;
for( i = 0 ; i<CAPACITY; i++){
data[i] = 0;
order[i] = 0;
}
}
void enqueue(int num){
entered++;
if(pos == 1){
data[1] = num;
order[1] = entered;
}
else{
data[pos] = num;
order[pos] = entered;
heapify(pos);
}
pos++;
}
int dequeue(){
int temp = data[1];
data[1] = data[pos-1];
data[pos-1]=0;
order[1] = order[pos-1];
order[pos-1] = 0;
heapifyDown(1);
return temp;
}
void heapify(int index){
if(index/2 < 1){
return;
}
else{
int t;
if(data[index] > data[index/2]){
t = data[index];
data[index] = data[index/2];
data[index/2] = t;
t = order[index];
order[index] = order[index/2];
order[index/2] = t;
heapify(index/2);
}
else if(data[index] == data[index/2]){
if(order[index] > order[index/2]){
t = data[index];
data[index] = data[index/2];
data[index/2] = t;
t = order[index];
order[index] = order[index/2];
order[index/2] = t;
heapify(index/2);
}
else{
return;
}
}
else{
return;
}
}
}
void heapifyDown(int index){
int leftchild = 2*index;
int rightchild = 2*index+1;
int min;
if(index >= 9){
return;
}
else{
if(leftchild >= CAPACITY){
return;
}
min = index;
if(data[index] < data[leftchild]){
min = leftchild;
}
else if(data[index] == data[leftchild]){
if(order[index] < order[leftchild]){
min = leftchild;
}
}
if( (rightchild < CAPACITY) && data[index] < data[rightchild]){
min = rightchild;
}
else if(data[index] == data[rightchild]){
if(order[index] < order[leftchild]){
min = rightchild;
}
}
if(min != index){
int te = data[index];
data[index] = data[min];
data[min] = te;
te = order[index];
order[index] = order[min];
order[min] = te;
heapifyDown(min);
}
}
}
};
int main(){
PriorityQueue Q1;
Q1.enqueue(5);
Q1.enqueue(7);
Q1.enqueue(3);
Q1.enqueue(2);
Q1.enqueue(1);
Q1.enqueue(9);
cout << Q1.dequeue();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.