支持删除，更新任意结点的优先级队列

class HashMap
{
public:
	void init();
	void push(int key, int value);
	int get(int key);
	struct dataItem
	{
		int key;
		int value;	
	};

	struct hashItem
	{
		int bufIdx;
		int next;
	};
private:
	static const int size = 1000;

	dataItem buffer[size];

	hashItem hashBuf[size];
	
	hashItem hashTbl[1009];
	
	int bufIdx;
	int hashBufIdx;
	
};

void HashMap::init(void)
{
	hashBufIdx = 0;
	bufIdx = 0;
	for(int i = 0; i < 1009; ++i)
	{
		hashTbl[i].next = -1;
	}
}

void HashMap::push(int key, int value)
{
	int hash = key %1009;

	int iter = hashTbl[hash].next;
	
	while(iter != -1)
	{
		int bufIdx = hashBuf[iter].bufIdx;

		if( buffer[bufIdx].key == key)
		{
			buffer[bufIdx].value = value;
			return;
		}

		iter = hashBuf[iter].next;
	}
	
	int i = bufIdx++;

	buffer[i].key = key;
	buffer[i].value = value;
	
	int j = hashBufIdx++;
	
	hashBuf[j].bufIdx = i;
	hashBuf[j].next = hashTbl[hash].next;
	hashTbl[hash].next = j;	
}

int HashMap::get(int key)
{
	int hash = key%1009;
	
	int iter = hashTbl[hash].next;
	
	while(iter != -1 )
	{
		dataItem value = buffer[ hashBuf[iter].bufIdx  ];
		if(value.key == key)
		{
			return value.value;
		} 

		iter = hashBuf[iter].next;
	}

	return -1;
}

class CPrioTree
{
public:
void init(void);
void push(int data);
int pop(void);
void update(int idx, int data);
void del(int idx);
int getIndex(int data);
int top();
bool empty() { return size == 0;}
protected:

virtual bool compare(int a, int b) = 0;
private:
void downward(int idx, int value);
void upward(int idx, int value);
static const int capacity = 1000;
int queue[capacity];
int size;
HashMap hashMap;
};

void CPrioTree::init(void)
{
	size = 0;	
	hashMap.init();
}
void CPrioTree::downward(int idx, int value)
{
	int i = idx;
	while( 2 * i + 1 < size)
	{
		int a = 2 * i + 1;
		int b = a + 1;

		if( b < size && compare(queue[b], queue[a]))
		{
			a = b;
		}

		if( compare(value, queue[a]) )
		{
			break;
		}

		queue[i] = queue[a];
		hashMap.push(queue[a], i);

		i  = a;
	}

	queue[i] = value;

	hashMap.push(value, i);
}

void CPrioTree::upward(int idx, int value)
{
	int i =  idx;
	while( i > 0)
	{
		int parentIdx = (i-1)/2;
		int parent = queue[parentIdx];
		
		if( compare(parent, value))
		{
			break;
		}

		queue[i] = parent;
		hashMap.push(parent, i);

		i = parentIdx;
	}

	queue[i] = value;
	hashMap.push(value, i);
}

void CPrioTree::push(int data)
{
	int i =size++;
	upward(i, data);
}

int CPrioTree::pop(void)
{
	int ret = queue[0];
	int tmp = queue[--size];
	downward(0, tmp);

	return ret;
}


void CPrioTree::update(int idx, int newValue)
{
	queue[idx] = newValue;

	bool downFlag = false;
	if( idx == 0)
	{
		downFlag = true;
	}

	if(!downFlag)
	{
		int parentIdx = (idx -1)/2;
		
		int parent = queue[parentIdx];
		
		if(compare(parent, newValue))
		{
			downFlag = true;
		}
	}


	if(downFlag)
	{		
		downward(idx, newValue);
	}
	else
	{
		upward(idx, newValue);
	}
}

void CPrioTree::del(int idx)
{
	int tmp = queue[--size];
	bool downFlag = false;
	if( idx == 0)
	{
		downFlag = true;
	}

	if(!downFlag)
	{
		int parentIdx = (idx-1)/2;
		int parent = queue[parentIdx];
		
		if(compare(parent, tmp))
		{
			downFlag = true;
		}
	}


	if(downFlag)
	{
		downward(idx, tmp);
	}
	else
	{
		upward(idx, tmp);
	}
}

int CPrioTree::getIndex(int data)
{
	return hashMap.get(data); 
}


int CPrioTree::top()
{
	return queue[0];
}

class CMaxPrioTree : public CPrioTree
{
protected:
	bool compare(int a, int b);	
};

bool CMaxPrioTree::compare(int a, int b)
{
	return a > b;
}


class CMinPrioTree : public CPrioTree
{
protected:
	bool compare(int a, int b);
};

bool CMinPrioTree::compare(int a, int b)
{
	return a < b;
}