#ifndef INDEX$\_$PRIORITY$\_$QUEUE$\_$HPP$\_$

#define INDEX$\_$PRIORITY$\_$QUEUE$\_$HPP$\_$

#include

#include

template

class IndexPriorityQueue $\{$

private:

std::vector priorities $\{\}$;

std::vector priorityQueue $\{\}$;

std::vector indexToPosition $\{\}$;

int size$\_=0$;

public:

explicit IndexPriorityQueue$($int$)$;

void push$($const T&$,$ int$)$;

void pop$()$;

void erase$($int$)$;

bool contains$($int$)$ const;

void changeKey$($const T&$,$ int$)$;

std::pair top$()$ const;

bool empty$()$ const;

int size$()$ const;

private:

$//$ TODO: you may want to add your own member functions. swim? sink?

$\}$;

$//$ Useful helper functions

int leftChild$($int i$)\{$

return $2*$i;

$\}$

int rightChild$($int i$)\{$

return $2*$i $+1$;

$\}$

int parent$($int i$)\{$

return i$/2$;

$\}$

$//$ IndexPriorityQueue member functions

template

IndexPriorityQueue::IndexPriorityQueue$($int N$)\{$

$\}$

template

bool IndexPriorityQueue::empty$()$ const $\{$

return true;

$\}$

template

int IndexPriorityQueue::size$()$ const $\{$

return $0$;

$\}$

template

void IndexPriorityQueue::push$($const T& priority, int index$)\{$

$\}$

template

void IndexPriorityQueue::pop$()\{$

$\}$

template

void IndexPriorityQueue::erase$($int index$)\{$

$\}$

template

std::pair IndexPriorityQueue::top$()$ const $\{$

return $\{$T $\{\},0\}$;

$\}$

$//$ if vertex i is not present, insert it with key

$//$ otherwise change the associated key value of i to key

template

void IndexPriorityQueue::changeKey$($const T& key, int index$)\{$

$\}$

template

bool IndexPriorityQueue::contains$($int index$)$ const $\{$

$\}$

#endif $//$ INDEX$\_$PRIORITY$\_$QUEUE$\_$HPP$\_$