natalie_code/program2/priorityqueue.cpp

/* Priority queue class to build heap array
Code from Geeks for Geeks (https://www.geeksforgeeks.org/binary-heap/) used as a starting point
*/


#include <iostream>
#include <cstdio>
#include <string>
#include "priorityqueue.h"
#include "json.hpp"

//
void PriorityQueue::initiateHeap(int capacity){
    heap_size = 0;
    max_size = capacity;
    heapArray = new int[max_size + 1];
}

// inserts a new key into end of heap array to then
void PriorityQueue::insert(int key){
  if(heap_size == max_size){
    std::cout << "PriorityQueue::insert called on full priority queue" << std::endl;
    return;
  }

  heap_size++;
  heapArray[heap_size] = key;
  heapifyUp(heap_size);
}

// clean up memory to avoid memory leaks
void PriorityQueue::deleteHeap(){
  delete[] heapArray;
}

void PriorityQueue::removeMax(){
  if (heap_size <= 0) {
    std::cout << "PriorityQueue::removeMax called on an empty priority queue" << std::endl;
    return;
  }

  if (heap_size == 1){
    heap_size--;
  } else if (heap_size == 2) {
    heapArray[1] = heapArray[2];
    heap_size--;
  } else {

    heapArray[1] = heapArray[heap_size];
    heap_size--;
    heapifyDown(1);
  }
}

int PriorityQueue::returnMax(){
  int topHeapKey = heapArray[1];
  return topHeapKey;
}

void PriorityQueue::removeKey(int key){
  for (int i = 1; i <= heap_size; i++) {
    if (heapArray[i] == key) {
      int beforeValue = heapArray[i];
      int afterValue = heapArray[heap_size];
      swap(&heapArray[i], &heapArray[heap_size]);
      heap_size--;

      if (beforeValue == afterValue) {
        return;
      } else if (afterValue < beforeValue) {
        heapifyDown(i);
        return;
      } else if (afterValue > beforeValue) {
        heapifyUp(i);
        return;
      }
    }
  }
  std::cout << "PriorityQueue::removeKey key " << key << " not found" << std::endl;
}

void PriorityQueue::change(int key, int newKey){
  for (int i = 1; i <= heap_size; i++) {
    if (heapArray[i] == key) {
      heapArray[i] = newKey;

      if (key == newKey) {
        return;
      } else if (newKey > key) {
        heapifyUp(i);
        return;
      } else if (newKey < key) {
        heapifyDown(i);
        return;
      }
    }
  }
  std::cout << "PriorityQueue::change key " << key << " not found" << std::endl;
}

void PriorityQueue::swap(int *key, int *otherKey){
    int temp = *otherKey;
    *otherKey = *key;
    *key = temp;
}

void PriorityQueue::heapifyDown(int index){
  int lBranchIndex = 2*index;
  int rBranchIndex = 2*index + 1;

  int largerKeyIndex = index;

  if (lBranchIndex <= heap_size && heapArray[lBranchIndex] > heapArray[largerKeyIndex]) {
    largerKeyIndex = lBranchIndex;
  }

  if (rBranchIndex <= heap_size && heapArray[rBranchIndex] > heapArray[largerKeyIndex]) {
    largerKeyIndex = rBranchIndex;
  }

  if (largerKeyIndex != index) {
    swap(&heapArray[index], &heapArray[largerKeyIndex]);
    heapifyDown(largerKeyIndex);
  }
}

void PriorityQueue::heapifyUp(int index){
  if (index <= 1){
    return;
  }

  int curIndex = index;
  int parentIndex = (curIndex)/2;

  while (parentIndex > 0 && heapArray[parentIndex] < heapArray[curIndex]) {
    swap(&heapArray[parentIndex], &heapArray[curIndex]);
    curIndex = (curIndex)/2;
    parentIndex = (parentIndex)/2;
  }
}

void PriorityQueue::printJSONTree(int maxHeapSize, int numOperations){
  nlohmann::json outputJSON;

  for (int i = heap_size; i >= 1; i--) {
    int keyValue = heapArray[i];

    int lBranchIndex = 2*i;
    int rBranchIndex = 2*i + 1;
    int parentIndex = i/2;

    std::stringstream convert2String_i;
    convert2String_i << i;
    std::string indexForJSON = convert2String_i.str();

    outputJSON[indexForJSON]["key"] = keyValue;

    // if not at the root, find the index of the parent node
    if (i > 1) {
      outputJSON[indexForJSON]["parent"] = parentIndex;
    }
    // is there a left branch
    if (lBranchIndex <= heap_size) {
      outputJSON[indexForJSON]["leftChild"] = lBranchIndex;
    }
    // is there a right branch
    if (rBranchIndex <= heap_size) {
      outputJSON[indexForJSON]["rightChild"] = rBranchIndex;
    }
  }

  // metadata output
  outputJSON["metadata"]["maxHeapSize"] = maxHeapSize;
  outputJSON["metadata"]["max_size"] = max_size;
  outputJSON["metadata"]["numOperations"] = numOperations;
  outputJSON["metadata"]["size"] = heap_size;
  std::cout << outputJSON << std::endl;

}