CODE:

#include 
#include 
#include 


template  >
class IndexedPriorityQueue{
	class AccessorSubstance;
public:
	//アクセサ：これを利用して順位変更や削除を行える。イテレーターと異なり捜査能力や参照能力は付加されていない
	typedef std::shared_ptr Accessor;
public:
	//コンストラクタは特に何もない
	IndexedPriorityQueue();

	//要素をキューに追加する
	Accessor push(const ItemType& item);

	//アクセサを用いて要素の優先順位を再変更する
	void change_priority(const ItemType& item, const Accessor& a);

	//アクセサを用いて要素を削除する
	void erase(const Accessor& a);

	//もっとも優先順位の高い要素を削除する
	void pop();

	//もっとも優先順位の高い要素の参照を得る
	ItemType& top();
	const ItemType& top() const;

	//キューのサイズを得る
	unsigned int size() const;

	//キューが空かどうか
	bool empty() const;


	//------------------------------------------------------------------------------------------------
	//以下はプライベート
	//------------------------------------------------------------------------------------------------
private:
	//ヒープを下から上に操作する(特定の要素をヒープの上層へ持っていく)
	void UpHeap(unsigned int k);
	//ヒープを上から下に操作する(特定の要素をヒープの下層へ持っていく)
	void DownHeap(unsigned int k);

	//アクセサの実態
	class AccessorSubstance{
		friend IndexedPriorityQueue;
		#if DEBUG || _DEBUG
		//デバグ時はアクセサのチェックを行う
			//親を保存しアクセサ使用時にチェック
			IndexedPriorityQueue* m_Parent;
			//アクセサが有効な値を示しているか？
			bool m_isValid;
		#endif
		unsigned int m_Index;
		//アクセサそのものはコピーできない
		AccessorSubstance& operator=(const AccessorSubstance& other);
		AccessorSubstance(const AccessorSubstance& other);
		#if DEBUG || _DEBUG
			//デバグ用コンストラクタ
			AccessorSubstance(unsigned int k, IndexedPriorityQueue* parent):m_Index(k),m_isValid(true),m_Parent(parent){
			}
		#else
			//コンストラクタ
			AccessorSubstance(unsigned int k):m_Index(k){
			}
		#endif
	};
	//実際に値を格納する構造体
	struct Unit{
		ItemType m_Item;
		//アクセサへのウィークポインタを保存する（順位変更時にアクセサが生きていた場合そのインデックスを変更できるようするため）
		std::weak_ptr m_Accessor;
	};
	//比較関数
	Comp m_Comp;
	//ヒープ本体
	std::vector m_Heap;
	//要素数
	unsigned int m_Counter;
};


template
IndexedPriorityQueue::IndexedPriorityQueue():m_Counter(0){
}

template
typename IndexedPriorityQueue::Accessor IndexedPriorityQueue::push(const ItemType& item){
	#if DEBUG || _DEBUG 
		//デバグ時にはインデックスのほかに自身のポインタを渡して他のキューと併用できなくする
		Accessor acc(new AccessorSubstance(++m_Counter, this) );
	#else
		//デバグでなければポインタチェックを行わない
		Accessor acc(new AccessorSubstance(++m_Counter) );
	#endif
	//アイテムを作成
	Unit u = {item, std::weak_ptr(acc)};
	//ヒープに追加して
	m_Heap.push_back(u);
	//ヒープを修復する
	UpHeap(m_Counter);
	return acc;
}

template
void IndexedPriorityQueue::change_priority(const ItemType& item, const Accessor& a){
	//デバグ用のチェック機構
	#if DEBUG || _DEBUG
		if(this != a->m_Parent || !a->m_isValid || a->m_Index > m_Counter) throw(std::runtime_error("不正なアクセサ") );
	#endif
	int index = a->m_Index;
	//変更前の値を保存して
	ItemType& value = m_Heap[index-1].m_Item;
	if(m_Comp(value, item)){
		//値を前と比較して前のほうが優先順位が高ければ
		m_Heap[index-1].m_Item = item;
		//ヒープを下に操作して優先順位を下げる
		DownHeap(index);
	}else{
		//そうでなければ
		m_Heap[index-1].m_Item = item;
		//ヒープを上に操作して優先順位を上げる
		UpHeap(index);
	}
}

template
void IndexedPriorityQueue::erase(const Accessor& a){
	#if DEBUG || _DEBUG
		if(this != a->m_Parent || !a->m_isValid || a->m_Index > m_Counter) throw(std::runtime_error("不正なアクセサ") );
		a->m_isValid = false;
	#endif

	//削除する要素と最後尾を入れ替えて末尾を削除。ヒープを修復する
	unsigned int index = a->m_Index;
	m_Heap[index-1] = m_Heap[--m_Counter];
	m_Heap.pop_back();
	DownHeap(index);
}

template
void IndexedPriorityQueue::pop(){
	//アルゴリズムはeraseと同じ。先頭と末尾を入れ替えて末尾を削除。その後ヒープを修復
	unsigned int index = 1;
	#if DEBUG || _DEBUG
		if(auto ptr = m_Heap[index-1].m_Accessor.lock() ) ptr->m_isValid = false;
	#endif
	m_Heap[index-1] = m_Heap[--m_Counter];
	m_Heap.pop_back();
	if(empty()) return;
	DownHeap(index);
}

template
const ItemType& IndexedPriorityQueue::top() const{
	return m_Heap[0].m_Item;
}

template
ItemType& IndexedPriorityQueue::top(){
	return m_Heap[0].m_Item;
}

template
unsigned int IndexedPriorityQueue::size() const{
	return m_Counter;
}

template
bool IndexedPriorityQueue::empty() const{
	return m_Counter == 0;
}

template
void IndexedPriorityQueue::DownHeap(unsigned int k){
	//ヒープを上から下に操作する（引数kのインデックスの要素が実際よりも低いためヒープの下層へ移動する）
	unsigned int temp = k;
	//要素を保存
	Unit u = m_Heap[k-1];
	//この要素は親の2倍のインデックスと二倍+1の二つ
	unsigned int j = k m_Index = k;
		k = j;
		j = k m_Index = k;
	}
	return;
}

template
void IndexedPriorityQueue::UpHeap(unsigned int k){
	//今度はヒープを下から上に操作する
	unsigned int temp = k;
	Unit u = m_Heap[k-1];
	//親の要素はkの半分のインデックスを持っている
	unsigned int j = k >> 1;
	while( j > 0 ){
		if(!m_Comp(u.m_Item, m_Heap[j-1].m_Item)) break;
		m_Heap[k-1] = m_Heap[j-1];
		if(auto ptr = m_Heap[k-1].m_Accessor.lock() ) ptr->m_Index = k;
		k = j;
		j = k >> 1;
	}
	if(k != temp){
		m_Heap[k-1] = u;
		if(auto ptr = m_Heap[k-1].m_Accessor.lock() ) ptr->m_Index = k;
	}
	return;
}