优先级队列,该怎么解决

优先级队列
队列定义：
1.元素按优先级排队，优先级高者居前，优先级相同的则按严格按到达的顺序先到者居前；
2.元素出队时居前者先出队；

基本操作：
1.元素入队
2.元素出队

其它要求：
1.防止“饿死”
2.快速判断指定元素是否存在于队列中、防止元素重复进入队列
3.满足频繁执行删除队列中指定元素的要求
4.保证是线程安全的

基本任务：
1.根据定义设计队列的数据结构
2.实现基本操作中要求两个操作
3.以随机数作为优先级，编写20个元素的入队与出队演示
4.分析算法的时间及空间复杂度

其他任务：
1.针对“其它要求”的要求（1.   ~   4.）对上面的实现进行调整，并写出演示
2.利用C#的面向对象编程的特性，使队列支持抽象的队列元素
3.实现线程安全的优先级队列，并写出3个线程并发执行入队/出队操作的演示
 


[解决办法]
//给你一个满足你的要求的
/*=====================================================
*********************基于堆的优先队列********************
=====================================================*/
//priQueue.h

#ifndef _PRIQUEUE_H_
#define _PRIQUEUE_H_

#include <exception>
using namespace std;


//优先队列类的定义
template <typename T>
class PriQueue
{
public:
PriQueue(int maxHeapSize=10);
~PriQueue()
{
delete [] heap;
}
int size() const
{
return heap_size;
}

void Initialize(T a[], int Size, int ArraySize);
//通过递归将第i个节点的值插入到堆的合适位置
void heapify(int i);
T HeapExtract();
void HeapInsert(T key);

//自定义的异常处理成员类
public:
class NoMem:public std::exception
{
public:
virtual const char* what() const throw()
{
return "there is no memory! ";
}
};

class OutOfBounds:public std::exception
{
public:
virtual const char* what() const throw()
{
return "out of bound! ";
}
};
private:

//返回左孩子
int left(int i) const
{
return i*2;
}
//返回右孩子
int right(int i) const
{
return i*2 + 1;
}

private:
//heap_size 为堆实际数组大小
//MaxSize 为最大容量
int heap_size, MaxSize;
T *heap; // 元素数组
};
//-------------------------------------------------------

//构造函数完成初始化工作
template <typename T>
PriQueue <T> ::PriQueue(int maxHeapSize=10)
{
heap_size = 0;
MaxSize = maxHeapSize;
heap = new T[MaxSize];
}
//-------------------------------------------------------

//heapify成员函数定义
template <typename T>
void PriQueue <T> ::heapify(int i)
{
T temp;
int lIndex, rIndex, largest;
lIndex = left(i); //取节点i的左孩子索引
rIndex = right(i);//取节点i的右孩子索引
//largest保存父节点,与左右两个节点中的较大值的索引
if(lIndex <=heap_size && heap[lIndex-1]> heap[i-1])
largest = lIndex;
else
largest = i;

if(rIndex <=heap_size && heap[rIndex-1]> heap[largest-1])
largest = rIndex;

if(largest !=i)
{
temp = heap[largest-1];
heap[largest-1] = heap[i-1];
heap[i-1] = temp;

//左孩子为空时返回,达最大递归深度
if(2*largest > heap_size)
return;
}
else //largest等于i时不需要在进行递归
return;
//递归调用
heapify(largest);
}
//----------------------

//在数组中进行堆的初始化
template <typename T>
void PriQueue <T> ::Initialize(T a[], int size, int ArraySize)
{
delete [] heap;
heap = a;
heap_size = size;
MaxSize = ArraySize;

for(int i= size/2+1; i> =1; --i)
heapify(heap, size, i);
}
//----------------------

//优先队列提取元素

template <typename T>
T PriQueue <T> ::HeapExtract()
{
T max;
if(heap_size < 1)
throw OutOfBounds(); // 队列空

max = heap[0];
heap[0] = heap[heap_size-1];
heap_size = heap_size -1;
heapify(1);
return max;
}
//-----------------------

//向优先队列中插入新的元素
template <typename T>
void PriQueue <T> ::HeapInsert(T key)
{
if(heap_size > = MaxSize)
throw NoMem(); // 没有足够空间
heap_size = heap_size + 1;
int i = heap_size;
int iParent = i/2;
while(i> 1 && heap[iParent-1] <key)
{
heap[i-1] = heap[iParent-1];
i = iParent;
iParent = i/2;
}
heap[i-1] = key;
}
//----------------------

#endif

//===================================================
//功能:基于堆结构的优先队列测试程序
//时间:2007\3\12
//===================================================
//priQueue.cpp
#include <cstdio>
#include <ctime>

#include <iostream>
#include "priQueue.h "

using namespace std;

const int NUM_SIZE = 20;

void main()
{
try
{
clock_t start,finish;
int temp;
PriQueue <int> myQueue(NUM_SIZE);

srand((unsigned)time(NULL));

start= clock();
for(int i=1;i <=NUM_SIZE;i++)
{
myQueue.HeapInsert(rand());
}
finish=clock();

cout < < "the total times: " < <finish-start < <endl;
for(i=1;i <=NUM_SIZE;i++)
{
temp = myQueue.HeapExtract();
cout < <temp < < " ";
}

finish=clock();

cout < < "the total times: " < <finish-start < <endl;
}

catch (const exception & e)
{
cerr < < "exception: " < <e.what() < <endl;
}
}