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 array1. The keys are doubles and the values are std::pairs of ints that represent player ids.

Some terminology: the ith node of the heap stores the KeyValuePair at index i in the array. That is, the 1st 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 TODOs. 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 KeyValuePairs in the heap.

PriorityQueue::getKey(size_t i) : Returns the key of the ith node in the heap.

PriorityQueue::heapifyUp(size_t i) : a.k.a. swimup, percolates the ith node up the heap to ensure the heap property is preserved.

PriorityQueue::heapifyDown(size_t i) : a.k.a. sink, percolates the ith node down the heap to ensure the heap property is preserved.

PriorityQueue::removeNode(size_t i) : Removes the ith 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 typedefs.

///////////////

priorityqueue.h:

#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_

///////////////

priorityqueue.cpp:

#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

}