c$++$ #ifndef $\_$HEAP$\_$H$\_$

#define $\_$HEAP$\_$H$\_$

#include

#include

using std::vector;

using std::cout;

using std::cin;

using std::endl;

class BinaryHeap

$\{$

private:

vector array; $//$ The heap array

int currentSize;

void buildHeap$()$;

void percolateDown$($ int pos $)$;

void percolateUp$($ int pos $)$;

public:

explicit BinaryHeap$($ int capacity $=100)$;

explicit BinaryHeap$($ const vector & items $)$;

int size$()$ const;

bool isEmpty$()$ const;

void print$()$ const;

int getMin$()$ const;

void insert$($ const int & x $)$;

void deleteMin$()$;

void deleteMin$($ int & minItem $)$;

void decreaseKey$($ int pos, int amountToDecrease $)$;

void increaseKey$($ int pos, int amountToIncrease $)$;

$\}$;

$/**$

$*$ Constructor

$*$

$*$ @param capacity the initial capacity of the heap

$*/$

BinaryHeap::BinaryHeap$($int capacity$)$

$\{$

array $=$ vector$($capacity$)$;

currentSize $=0$;

$\}$

$/**$

$*$ delete the minimum from the heap

$*$

$*$ @return bool whether the heap is empty

$*/$

bool BinaryHeap::isEmpty$()$ const

$\{$

return currentSize $==0$;

$\}$

$/**$

$*$ delete the minimum from the heap

$*$

$*$ @return bool whether the heap is empty

$*/$

int BinaryHeap::size$()$ const

$\{$

return currentSize;

$\}$

$/**$

$*$ Print the heap in a linear array

$*$

$*/$

void BinaryHeap::print$()$ const

$\{$

$//$ TODO $1$

$\}$

$/**$

$*$ get the minimum value in heap

$*$

$*$ @return x the minimum value

$*/$

int BinaryHeap::getMin$()$ const

$\{$

$//$ TODO $2$

$//$ just a place holder

return $1$;

$\}$

$/**$

$*$ insert an item to the heap

$*$

$*$ @param x the value to be inserted to the heap

$*/$

void BinaryHeap::insert$($ const int & x $)$

$\{$

$//$ TODO $3$

$\}$

$/**$

$*$ delete the minimum from the heap

$*$

$*/$

void BinaryHeap::deleteMin$()$

$\{$

$//$ TODO $4$

$\}$

$/**$

$*$ delete the minimum from the heap

$*$

$*$ @param minItem the value of the minimium item will be assigned to minItem

$*/$

void BinaryHeap::deleteMin$($ int & minItem $)$

$\{$

$//$ TODO $5$

$\}$

$/**$

$*$ Percolate down an item

$*$

$*$ @param pos the array position of the item to be percolated down.

$*/$

void BinaryHeap::percolateDown$($ int pos $)$

$\{$

$//$ TODO $6$

$\}$

$/**$

$*$ Percolate up an item

$*$

$*$ @param pos the array position of the item to be percolated up$.$

$*/$

void BinaryHeap::percolateUp$($int pos$)$

$\{$

$//$ TODO $7$

$\}$

$/**$

$*$ Constructor to create a Heap from a vector of integers

$*$

$*$ @param items a vector of integers to construct the heap

$*/$

BinaryHeap::BinaryHeap$($ const vector & items $)$

$\{$

$//$ TODO $8$

$//$ use buildheap$(),$ not allowed to use insert$()$

$\}$

$/**$

$*$ Establish heap order property from an arbitrary

$*$ arrangement of items. Runs in linear time.

$*/$

void BinaryHeap::buildHeap$()$

$\{$

$//$ TODO $9$

$\}$

$/**$

$*$ Increase the value of a node

$*$ Thus decrease the priority

$*$

$*$ @param pos the array position of the item to increase

$*$ @param amountToIncrease the positive value to be ADDED to the item

$*/$

void BinaryHeap::increaseKey$($int pos, int amountToIncrease$)$

$\{$

$//$ TODO $10$

$\}$

$/**$

$*$ Decrease the value of a node

$*$ Thus increase the priority

$*$

$*$ @param pos the array position of the item to decrease

$*$ @param amountToDecrease the positive value to be SUBTRACTED from the item

$*/$

void BinaryHeap::decreaseKey$($int pos, int amountToDecrease$)$

$\{$

$//$ TODO $11$

$\}$

#endif $//\_$HEAP$\_$H$\_$