natalie_code/program2/priorityqueue.cpp

// initial pseudocode from:
// https://www.geeksforgeeks.org/binary-heap/

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

// priority queue class using binary heap
class PriorityQueue{
  int *heapArray;   // pointer to heap array
  int max_size;     // max size of heap array
  int heap_size;    // elements in heap
public:
  // required functions
  void insert(int);
  void removeMax();
  void removeKey(int);
  void change(int*, int*);
  // helpful functions
  void heapifyUp(int);
  void heapifyDown(int);
  //nlohmann::json JSON();
  // other required functions (for now)
  void initiateHeap(int);
};

void PriorityQueue::initiateHeap(int capacity){
    heap_size = 0;
    max_size = capacity;
    heapArray = new int[max_size]; // try to change this to vector... please!!!
}

void PriorityQueue::insert(int newNode){
  if(heap_size == max_size){
    std::cout << "PriorityQueue::insert called on full priority queue" << std::endl;
    return;
  }
  // heapify up until the heap properties are restored
  heapifyUp(newNode);
}

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

  if (heap_size == 1) { // need to check if at root to avoid error
    heap_size--;
  } else {
    // remove the max value (at root)
    heapArray[0] = heapArray[heap_size - 1];
    heap_size--;
    // heapify down until the heap properties are restored
    heapifyDown(0);
  }
}

// deletes all keys at index i
void PriorityQueue::removeKey(int index){
  if (heapArray[index] == NULL) {
    std::cout << "PriorityQueue::removeKey key " << index << " not found" << std::endl;
    return;
  }
  // increase value at index to inf
  // run function extracting the maximum value
}

void PriorityQueue::change(int *key, int *newK){
// needs to change. I'm looking for the key, not the index?
  for (int i = 0; i >= heap_size; i++) {
    if (heapArray[i] == *key) {
      // if the key is found exchange the old key for the new
      heapArray[i] == *newK;

      // figure out the case when heapify up/down are needed
      if (*key > *newK) {
        heapifyUp(i);
      } else if (*key < *newK) {
        heapifyDown(i);
      }

    } else {
      std::cout << "PriorityQueue::change key " << *key << " not found" << std::endl;
      return;
    }
  }

}

void PriorityQueue::heapifyDown(int node){
  int lBranchValue = 2*node;
  int rBranchValue = 2*node + 1;

  int largerNode = node;

  if (lBranchValue < heap_size && heapArray[lBranchValue] > heapArray[node]) {
    largerNode = lBranchValue;
  }

  if (rBranchValue < heap_size && heapArray[rBranchValue] > heapArray[largerNode]) {
    largerNode = rBranchValue;
  }

  if (largerNode != 1) {
    change(&heapArray[node], &heapArray[largerNode]);
    heapifyDown(largerNode);
  }
}

void PriorityQueue::heapifyUp(int node){
  int curIndex = heap_size;
  int parentIndex = (curIndex-1)/2;
  heap_size++;
  // insert new key into the end of the array
  heapArray[curIndex] = node;

  while (curIndex != 0 && heapArray[parentIndex] < heapArray[curIndex]) {
    change(&heapArray[curIndex], &heapArray[parentIndex]);
    curIndex = (curIndex-1)/2;
    parentIndex = (parentIndex-1)/2;
  }
}