Question

利用大顶堆实现一个优先队列。

7. 利用大顶堆实现一个优先队列。对于队列的操作应该至少支持下列几种指令：
Void enqueue(int ObjectID, int Priority);
Int dequeue();
Void changeweight(int ObjectID, int newPriority);
函数enqueue向优先队列中插入一个ID号为ObjectID,优先级为priority的新对象。函数dequeue从优先队列中删除优先级最高的对象，并返回该对象的ID号。函数changeweight将ID号为ObjectID的对象的优先级改为newPriority。你需要一种机制，以便获取所需要对象在堆中的位置。你还需要对堆的实现进行修改，以存储对象在数组中的位置，使得堆中对象的修改可以在辅助数组结构中记录下来。

Answer 1

怎么感觉是考研难度的复习题了~~写了一点， #include <iostream>
#include <string>
#define MAX 100
using namespace std;
class Elem{
public:
int id;
int pri;
};
class Comp{
public:
static bool It(Elem x,Elem y){
return x.pri<y.pri;
}
static bool eq(Elem x,Elem y){
return x.pri==y.pri;
}
static bool gt(Elem x,Elem y){
return x.pri>y.pri;
}
};
template <class Elem,class Comp> class maxheap{
Elem* Heap;
int size;
int n;
char bk[MAX];
void siftdown(int);
public:
void enqueue(int id,int pri);
int dequeue();
void changeweight(int id,int pri);
maxheap(Elem* h,int num,int max)
{
Heap=h;
n=num;
size=max;
buildHeap();
}
int heapsize() const
{
return n;
}
bool isLeaf(int pos) const
{
return (pos>=n/2)&&(pos<n);
}
int leftchild(int pos) const
{
return 2*pos+1;
}
int rightchild(int pos) const
{
return 2*pos+2;
}
int parent(int pos) const
{
return (pos-1)/2;
}
bool insert(const Elem&);
bool removemax(Elem&);
bool remove(int,Elem&);
void buildHeap()
{
for(int i=n/2-1;i>=0;i--)
siftdown(i);
}
};
前半段我看应该是没问题的。
太晚了，睡觉！我也怕写错，300分！！！如果写完发你邮