Implement the push and pop methods of the priority queue class, and implement private methods bubble_up and percolate_down.

#ifndef PRIORITY_QUEUE #define PRIORITY_QUEUE #include #include class PQ { public: /** * Construct an empty priority queue */ PQ() : op_count {0} {} // disallow both copy constructors and both operator= methods PQ(const PQ& pq) = delete; PQ(const PQ&& pq) = delete; PQ& operator= (const PQ& pq) = delete; PQ& operator= (const PQ&& pq) = delete; /** * Insert a priority into the PQ * @param priority the priority of the inserted job */ void push(unsigned priority) { } /** * Remove and return the maximum-priority job in the queue. * @return the priority of the removed job */ unsigned pop() { assert(array.size() != 0); return 0; } /** * Report if the queue is empty * @return true if empty, false otherwise */ bool is_empty() const { return array.empty(); } /** * Return the number of basic operations counted so far * @return the count of basic operations */ size_t get_op_count() const { return op_count; } /** * Reset the basic operations counter */ void reset_op_count() { op_count = 0; } private: std::vector array; size_t op_count; }; #endif

#include #include #include #include #include "pq.h" using namespace std; int main(int argc, char * argv[]) { if (argc != 2) { cerr << "Usage: " << argv[0] << " n where n is the number of values" << endl; return 1; } size_t number_of_values {static_cast(stoul(argv[1]))}; const unsigned MAX_RANDOM_VALUE = 1000000; default_random_engine get_next_value (static_cast (chrono::system_clock::now().time_since_epoch().count())); uniform_int_distribution uniform(0, MAX_RANDOM_VALUE); PQ priority_queue; for (size_t index = 0; index < number_of_values; index++) { priority_queue.push(uniform(get_next_value)); } size_t number_of_operations_push = priority_queue.get_op_count(); priority_queue.reset_op_count(); for (size_t index = 0; index < number_of_values; index++) { unsigned dummy = priority_queue.pop(); } size_t number_of_operations_pop = priority_queue.get_op_count(); cout << number_of_values << ' ' << number_of_operations_push << ' ' << number_of_operations_pop << endl; return 0; }