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
void PriorityQueue::initiateHeap(int capacity){
    heap_size = 0;
    max_size = capacity;
    heapArray = new int[max_size];
}

void PriorityQueue::insert(int key){
  if(heap_size == max_size){
    std::cout << "PriorityQueue::insert called on full priority queue" << std::endl;
    return;
  }
  // increase array size and insert new key at end
  heap_size++;
  int keyIndex = heap_size;
  // heapify up until the heap properties are restored
  heapifyUp(key, keyIndex);
}

void PriorityQueue::deleteHeap(){
  // clean up memory so deallocate array
  delete[] heapArray;
}

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){
    //heapArray[0] == 0;
    heap_size--;
  } else if (heap_size == 2) { // need to check if at root to avoid error
    heapArray[1] = heapArray[2];
    heap_size--;
  } else {
    // remove the max value (at root)
    heapArray[1] = heapArray[heap_size];
    heapifyDown(1);
    heap_size--;
  }
}

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) {
      // change the key at index with last heap key
      change(&heapArray[i], &heapArray[heap_size]);
      // erase the last node erasing the unwanted key
      heap_size--;
      // heapify to preserve heap properties
      heapifyDown(i);
      return;
    }
  }
  std::cout << "PriorityQueue::removeKey key " << key << " not found" << std::endl;
  return;
}

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

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

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

  int largerKeyIndex = index;

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

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

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

void PriorityQueue::heapifyUp(int key, int index){
  int curIndex = index;
  int parentIndex = (curIndex)/2;
  // insert new key into the end of the array
  heapArray[curIndex] = key;

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

void PriorityQueue::printArray(){
  for (int i = 1; i <= heap_size; i++) {
    std::cout << heapArray[i] << " , ";
  }
  std::cout << std::endl;
}