Finish the (Minimum) PriorityQueue class in the files priorityqueue.h and priorityqueue.cpp . It must implemented as an array-based binary heap with the root node at index 1 of the array 1 . The keys are double s and the values are std::pair s of int s that represent player ids. Some terminology: the i th node of the heap stores the KeyValuePair at index i in the array. That is, the 1 st node has the minimum Key in the heap since we are writing a minimum priority queue. Implement the following member functions, which are marked in priorityqueue.cpp with TODO s. I recommend implementing them in this order, as you should be using some of these functions when you implement the others. PriorityQueue::isEmpty() : Returns true if and only if the heap is empty. PriorityQueue::size() : Returns the number of KeyValuePair s in the heap. PriorityQueue::getKey(size_t i) : Returns the key of the i th node in the heap. PriorityQueue::heapifyUp(size_t i) : a.k.a. swimup , percolates the i th node up the heap to ensure the heap property is preserved. PriorityQueue::heapifyDown(size_t i) : a.k.a. sink , percolates the i th node down the heap to ensure the heap property is preserved. PriorityQueue::removeNode(size_t i) : Removes the i th node from the heap. PriorityQueue::min() : Returns the KeyValuePair that has the minimum Key in the heap. PriorityQueue::removeMin() : Returns and removes the KeyValuePair that has the minimum Key in the heap. PriorityQueue::insert(KeyValuePair kv) : Inserts a key-value pair into the priority queue. The types Key , Value , and KeyValuePair are defined in priorityqueue.h using typedef s.

Relevant files are

DocViewer

Zoom

Pages

#ifndef _PRIORITYQUEUE_H_

#define _PRIORITYQUEUE_H_

#include

#include

#include "json.hpp"

typedef double Key;

typedef std::pair Value;

typedef std::pair KeyValuePair;

class PriorityQueue {

public:

PriorityQueue(std::size_t max_nodes);

void insert(Key k);

void insert(KeyValuePair kv);

KeyValuePair min();

KeyValuePair removeMin();

bool isEmpty() const;

size_t size() const;

nlohmann::json JSON() const;

private:

void heapifyUp(size_t i);

void heapifyDown(size_t i);

void removeNode(size_t i);

Key getKey(size_t i);

std::vector nodes_;

size_t max_size_;

size_t size_;

const static size_t ROOT = 1;

}; // class PriorityQueue

#endif // _PRIORITYQUEUE_H_

And

DocViewer

Page

of 2Zoom

Pages

#include

#include "json.hpp"

#include "priorityqueue.h"

PriorityQueue::PriorityQueue(std::size_t max_size) :

nodes_(max_size + 1, KeyValuePair()),

max_size_(max_size),

size_(0) {

}

void PriorityQueue::insert(Key k) {

insert(std::make_pair(k, std::make_pair(0, 0)));

}

void PriorityQueue::insert(KeyValuePair kv) {

// TODO: complete this function

}

KeyValuePair PriorityQueue::min() {

// TODO: complete this function

}

KeyValuePair PriorityQueue::removeMin() {

// TODO: complete this function

}

bool PriorityQueue::isEmpty() const {

// TODO: complete this function

}

size_t PriorityQueue::size() const {

// TODO: complete this function

}

nlohmann::json PriorityQueue::JSON() const {

nlohmann::json result;

for (size_t i = 1; i <= size_; i++) {

nlohmann::json node;

KeyValuePair kv = nodes_[i];

node["key"] = kv.first;

node["value"] = kv.second;

if (i != ROOT) {

node["parent"] = std::to_string(i / 2);

}

if (2 * i <= size_) {

node["leftChild"] = std::to_string(2 * i);

}

if (2 * i + 1 <= size_) {

node["rightChild"] = std::to_string(2 * i + 1);

}

result[std::to_string(i)] = node;

}

result["metadata"]["max_size"] = max_size_;

result["metadata"]["size"] = size_;

return result;

}

void PriorityQueue::heapifyUp(size_t i) {

// TODO: complete this function

}

void PriorityQueue::heapifyDown(size_t i) {

// TODO: complete this function

}

void PriorityQueue::removeNode(size_t i) {

// TODO: complete this function

}

Key PriorityQueue::getKey(size_t i) {

// TODO: complete this function

}

Annotations