The program inserts a number of values into a priority queue and then removes them. The priority queue treats a larger unsigned integer as a higher priority than a smaller value. The priority queue object keeps a count of the basic operations performed during its lifetime to date, and that count is available via an accessor. In one or two places I have put statements such as op_count++;, but these are incomplete. We only count operations involved in inserting and removing elements, not auxiliary operations such as is_empty() or size() The class implements a priority queue with an unsorted vector.
The program inserts a number of values into a priority queue and then removes them. The priority queue treats a larger unsigned integer as a higher priority than a smaller value. The priority queue object keeps a count of the basic operations performed during its lifetime to date, and that count is available via an accessor.
In one or two places I have put statements such as op_count++;, but these are incomplete. We only count operations involved in inserting and removing elements, not auxiliary operations such as is_empty() or size() The class implements a priority queue with an unsorted
Your assignment is to re-implement the priority queue implementation using a heap built on a vector, exactly as we discussed in class. Leave the framework and public method interfaces completely unchanged. My original test program must work with your new class.
You will have to write new private methods bubble_up and percolate_down. You should not implement heapify or heapsort.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include "pq.h"
using namespace std;
int main()
{
PriorityQueue pq;
pq.push(28);
pq.push(23);
pq.push(2);
pq.push(4);
pq.push(134);
pq.push(204);
pq.push(5);
pq.push(40);
pq.push(8);
pq.push(10);
pq.push(1);
pq.push(183);
while (!pq.is_empty())
{
cout << pq.pop() << endl;
}
uint64_t basic_operations = pq.get_op_count();
cerr << 12 << ' ' << basic_operations << endl;
return 0;
}
#ifndef MY_PQ
#define MY_PQ
#include <cassert>
#include <cstdint>
#include <climits>
#include <vector>
class PriorityQueue
{
public:
/**
* Construct an empty priority queue
*/
PriorityQueue() : op_count{0} {}
/**
* Insert a priority into the PQ
* @param priority the priority of the inserted job
*/
void push(unsigned priority)
{
array.push_back(priority);
op_count++; // one operation for push_back
}
/**
* Remove and return the maximum-priority job in the queue.
* @return the priority of the removed job
*/
unsigned pop()
{
size_t max_position = array.size();
unsigned max_value = 0;
for (size_t index = 0; index < array.size(); index++)
{
op_count += 2; // for loop header
if (array.at(index) > max_value)
{
max_value = array.at(index);
max_position = index;
}
}
op_count += 2; // for loop header last time
assert(max_position != array.size()); // no op_count for sanity check
for (size_t index = max_position; index < array.size() - 1; index++)
{
array.at(index) = array.at(index + 1);
}
array.pop_back();
return max_value;
}
/**
* Report if the queue is empty
* @return true if empty, false otherwise
*/
bool is_empty() const
{
return array.empty();
}
/**
* Report the number of elements in the queue
* @return the number of elements
*/
size_t size() const
{
return array.size();
}
/**
* Return the number of basic operations counted so far
* @return the count of basic operations
*/
uint64_t get_op_count() const
{
return op_count;
}
private:
std::vector<unsigned> array;
uint64_t op_count;
};
#endif
Step by step
Solved in 4 steps
