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.

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question

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.

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

Expert Solution
steps

Step by step

Solved in 4 steps

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY