以下内容是关于数据结构 最小堆求解的问题！请看代码~

Question

#include<iostream>
using namespace std;

template <class T>
class MinHeap{
private:
T *heapArray;
int CurrentSize;
int MaxSize;
void BuildHeap();
public:
MinHeap( int n);
bool isEmpty();
int LeftChild(int pos) ;
int Parent(int pos) ;
bool Insert( T& newNode);
T& RemoveMin();
void SiftUp(int position);
void SiftDown(int left);
};

class Dist{
public:
int index;
int length;
int pre;
};

template <class T>
MinHeap<T>::MinHeap( int n){
if(n<=0)
return;
CurrentSize=0;
MaxSize=n;
heapArray=new T[MaxSize];
BuildHeap();
}

template<class T>
bool MinHeap<T>::isEmpty(){
if(CurrentSize==0)
return true;
else
return false;
}

template <class T>
void MinHeap<T>::BuildHeap(){
for(int i=CurrentSize/2-1;i>=0;i--)
SiftDown(i);
}

template <class T>
int MinHeap<T>::LeftChild(int pos) {
return 2*pos+1;
}

template <class T>
int MinHeap<T>::Parent(int pos) {
return (pos-1)/2;
}

template <class T>
bool MinHeap<T>::Insert( T& newNode){
if(CurrentSize==MaxSize)
return false;
heapArray[CurrentSize]=newNode;
SiftUp(CurrentSize);
CurrentSize++;
return true;
}

template <class T>
T& MinHeap<T>::RemoveMin(){
if(CurrentSize==0){
cout<<"Can`t Delete";
exit(1);
}
else{
swap(0,--CurrentSize);
if(CurrentSize>1)
SiftDown(0);
return heapArray[CurrentSize];
}
}

template <class T>
void MinHeap<T>::SiftUp(int position){
int temppos=position;
T temp=heapArray[temppos];
while((temppos>0)&&(heapArray[Parent(temppos)]>temp)){
heapArray[temppos]=heapArray[Parent(temppos)];
temppos=Parent(temppos);
}
heapArray[temppos]=temp;
}

template <class T>
void MinHeap<T>::SiftDown(int left){
int i=left;
int j=LeftChild(i);
T temp=heapArray[i];
while(j<CurrentSize){
if((j<CurrentSize-1)&&(heapArray[j]>heapArray[j+1]))
j++;
if(temp>heapArray[j]){
heapArray[i]=heapArray[j];
i=j;
j=LeftChild(j);
}
else break;
}
heapArray[i]=temp;
}

void main(){
MinHeap<Dist> heap(5);
}
//MinHeap<int> heap(5)就没问题 为什么MinHeap<Dist> heap(5)把Dist类放进去就错了？
前面的都不太用看 主要看最后的main那里就好

Answer 1

heapArray[j]>heapArray[j+1]等等 比较语句int是没问题 但自定义的需要重载下运算符