Implement a heap-based priority queue CLASS containing characters using a zero-b
ID: 3729600 • Letter: I
Question
Implement a heap-based priority queue CLASS containing characters using a zero-based ARRAY of these records. You may assume that the heap will contain no more than 255 elements. Implement two functions “insert” and “remove”. Function “insert” takes a character as an input and insert it to the priority queue. Function “remove” removes a character with the highest priority, that is to remove the minimum (alphabetically first) character from the queue. Provide the class in C++. Also, write a simple separate program that uses the heap-based queue class.
Explanation / Answer
In below Example we create a class called "PriorityQueue". And then we use that class in our example.
Let's first create PriorityQueue class so that you can include this class in any cpp file
1. Create PriorityQueue.h
class PriorityQueue {
const static int MAX_SIZE = 255;
private:
int front;
int rear;
int size;
int *array;
public:
PriorityQueue();
~PriorityQueue();
void insert(char x);
char remove();
bool empty();
int _size();
};
2. Create class PriorityQueue.cpp
#include <iostream>
#include "PriorityQueue.h"
using namespace std;
PriorityQueue::PriorityQueue() // Constructor function
{
front = rear = -1;
size = 0;
array = new int[MAX_SIZE];
}
PriorityQueue::~PriorityQueue() // Destructor function
{
delete[] array;
}
// Inserts a Character into Priority Queue
// Also maintains smallest element (Highest priority element) at the front
void PriorityQueue::insert(char c)
{
//if queue is full
if ( size == MAX_SIZE ){
return;
}
//else if queue is empty
else if ( empty() ){
rear = front = 0;
}
else {
rear = (rear + 1);
}
int x = (int) c;
int index = rear;
for(int i = front ; i <= rear ; i++) {
if(x < array[i]) {
for(int j = rear ; j >= i ; j--) {
array[j] = array[j-1];
}
index = i;
break;
}
}
array[index] = x;
size++;
}
//Remove top priority element from queue
char PriorityQueue::remove() {
return (char)array[front++];
}
bool PriorityQueue::empty() {
if ( size == 0 )
return true;
else
return false;
}
int PriorityQueue::_size() {
return size;
}
3. Create example file main.cpp
#include <iostream>
#include "PriorityQueue.h"
using namespace std;
int main() {
PriorityQueue queue;
queue.insert('B');
queue.insert('C');
queue.insert('D');
queue.insert('A');
cout << queue.remove() << endl;
cout << queue.remove() << endl;
queue.insert('E');
queue.insert('F');
queue.insert('L');
queue.insert('G');
cout << queue.remove() << endl;
cout << queue.remove() << endl;
cout << queue.remove() << endl;
return 0;
}
4. Use following command to compile. Assuming all files are in same folder
g++ PriorityQueue.cpp main.cpp
5. Run your example as
./a.out
It will print A, B,C, D, E
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.