我制作了自己的 minHeap 模板，它似乎可以很好地对整数进行排序，但是当我尝试对自己的类进行排序时，我称之为 Road，它的排序大约是正确的...
Road 类是这样定义的：它有两个整数 cityA 和 cityB 以及一个 double 称为 length。
当比较两条道路 A 和 B 时，我们说 A 小于 B 是 A 的长度成员小于 B 的长度成员，或者如果它们的长度相等并且 A 包含所有四个城市的城市中的最小整数（A 中的城市 A 和城市 B 和B 中的城市 A 和城市 B）。
示例：RoadA 有 cityA=4，cityB=5，length=6；和 RoadB 有 cityA=1 cityB=9,length=2。在这种情况下，RoadB 更小，因为它的长度更小
示例 2：RoadA 有 cityA=4，cityB=5，length=6；RoadB 的 cityA=1 cityB=9,length=6。在这种情况下，RoadB 较小，因为它包含具有最小整数 (cityA=1) 的城市。
我相信我已经在我的 road.cpp 但我的 MinHeap 中正确地实现了这一点，但它似乎没有正确地对道路进行分类。
我做了一个测试用例来举例说明它的行为，下面是代码：
#include <iostream>
#include"minHeap.h"
#include"road.h"
using namespace std;
int main()
{
minHeap<Road> roadHeap(100);
for(int i=0; i< 20; i++){
for(int j=i+1; j< 20; j++){
Road *tempRoad = new Road();
tempRoad->setCityA(i);
tempRoad->setCityB(j);
tempRoad->setLength(5);
roadHeap.push(*tempRoad);
delete tempRoad; //minHeap takes in a copy of the road so i can safely delete this
}
}
while(!roadHeap.isEmpty()){
cout << "<road>" << roadHeap.top().getCityA() << " " << roadHeap.top().getCityB() << " " << roadHeap.top().getLength() << "</road>" << endl;
roadHeap.pop();
}
return 0;
}
这应该做的是以格式打印出道路<road> [cityA] [cityB] [length] </road> [newline]
因为它们都被推到了 minHeap，所以它应该对道路进行排序，输出应该如下所示：
<road>0 1 5</road>
<road>0 2 5</road>
<road>0 3 5</road>
<road>0 4 5</road>
<road>0 5 5</road>
<road>0 6 5</road>
<road>0 7 5</road>
<road>0 8 5</road>
<road>0 9 5</road>
<road>0 10 5</road>
<road>0 11 5</road>
<road>0 12 5</road>
<road>0 13 5</road>
<road>0 14 5</road>
<road>0 15 5</road>
<road>0 16 5</road>
<road>0 17 5</road>
<road>0 18 5</road>
<road>0 19 5</road>
<road>1 2 5</road>
<road>1 3 5</road>
<road>1 4 5</road>
<road>1 5 5</road>
<road>1 6 5</road>
<road>1 7 5</road>
<road>1 8 5</road>
<road>1 9 5</road>
<road>1 10 5</road>
<road>1 11 5</road>
<road>1 12 5</road>
<road>1 13 5</road>
...
...
...
<road>18 19 5</road>
但是 INSTEAD 我的测试程序输出以下内容：
<road>0 1 5</road>
<road>0 2 5</road>
<road>1 2 5</road>
<road>2 3 5</road>
<road>1 3 5</road>
<road>0 3 5</road>
<road>0 4 5</road>
<road>2 4 5</road>
<road>1 4 5</road>
<road>3 4 5</road>
<road>4 5 5</road>
<road>2 5 5</road>
<road>0 5 5</road>
<road>1 5 5</road>
<road>3 5 5</road>
<road>4 6 5</road>
<road>2 6 5</road>
<road>5 6 5</road>
<road>1 6 5</road>
<road>0 6 5</road>
<road>3 6 5</road>
<road>4 7 5</road>
<road>2 7 5</road>
<road>1 7 5</road>
<road>6 7 5</road>
<road>0 7 5</road>
<road>3 7 5</road>
<road>0 8 5</road>
<road>4 8 5</road>
<road>6 8 5</road>
<road>1 8 5</road>
<road>4 9 5</road>
<road>0 9 5</road>
<road>6 9 5</road>
<road>1 9 5</road>
<road>9 10 5</road>
<road>4 10 5</road>
<road>6 10 5</road>
<road>9 11 5</road>
<road>0 19 5</road>
<road>10 11 5</road>
<road>4 11 5</road>
<road>6 11 5</road>
<road>8 12 5</road>
<road>9 12 5</road>
<road>10 12 5</road>
<road>4 12 5</road>
<road>0 12 5</road>
<road>6 12 5</road>
<road>1 17 5</road>
<road>3 13 5</road>
<road>3 19 5</road>
<road>8 13 5</road>
<road>9 13 5</road>
<road>10 13 5</road>
<road>2 13 5</road>
<road>0 13 5</road>
<road>6 13 5</road>
<road>1 14 5</road>
<road>3 14 5</road>
<road>8 14 5</road>
<road>2 14 5</road>
<road>6 14 5</road>
<road>2 15 5</road>
<road>6 15 5</road>
<road>3 12 5</road>
<road>1 13 5</road>
<road>7 19 5</road>
<road>7 18 5</road>
<road>7 17 5</road>
<road>7 16 5</road>
<road>7 15 5</road>
<road>7 14 5</road>
<road>8 16 5</road>
<road>5 16 5</road>
<road>7 12 5</road>
<road>7 11 5</road>
<road>7 10 5</road>
<road>8 11 5</road>
<road>6 19 5</road>
<road>6 18 5</road>
<road>11 15 5</road>
<road>11 16 5</road>
<road>2 16 5</road>
<road>6 16 5</road>
<road>5 17 5</road>
<road>2 17 5</road>
<road>9 17 5</road>
<road>11 14 5</road>
<road>6 17 5</road>
<road>4 17 5</road>
<road>7 8 5</road>
<road>3 8 5</road>
<road>9 19 5</road>
<road>10 14 5</road>
<road>10 15 5</road>
<road>5 15 5</road>
<road>5 14 5</road>
<road>5 13 5</road>
<road>8 17 5</road>
<road>5 11 5</road>
<road>5 10 5</road>
<road>9 14 5</road>
<road>0 11 5</road>
<road>8 15 5</road>
<road>1 15 5</road>
<road>3 15 5</road>
<road>4 18 5</road>
<road>9 15 5</road>
<road>0 16 5</road>
<road>4 15 5</road>
<road>4 14 5</road>
<road>4 13 5</road>
<road>10 16 5</road>
<road>3 16 5</road>
<road>10 17 5</road>
<road>11 12 5</road>
<road>12 16 5</road>
<road>0 18 5</road>
<road>12 15 5</road>
<road>13 15 5</road>
<road>13 18 5</road>
<road>3 18 5</road>
<road>0 17 5</road>
<road>14 15 5</road>
<road>12 19 5</road>
<road>11 17 5</road>
<road>14 17 5</road>
<road>8 10 5</road>
<road>3 11 5</road>
<road>1 12 5</road>
<road>0 15 5</road>
<road>7 13 5</road>
<road>12 18 5</road>
<road>15 16 5</road>
<road>1 16 5</road>
<road>9 16 5</road>
<road>2 19 5</road>
<road>2 18 5</road>
<road>3 17 5</road>
<road>1 18 5</road>
<road>8 19 5</road>
<road>5 18 5</road>
<road>9 18 5</road>
<road>2 12 5</road>
<road>5 12 5</road>
<road>2 10 5</road>
<road>5 9 5</road>
<road>10 18 5</road>
<road>11 13 5</road>
<road>4 16 5</road>
<road>12 14 5</road>
<road>12 13 5</road>
<road>13 17 5</road>
<road>1 19 5</road>
<road>13 16 5</road>
<road>13 14 5</road>
<road>15 18 5</road>
<road>16 18 5</road>
<road>13 19 5</road>
<road>8 9 5</road>
<road>3 10 5</road>
<road>1 11 5</road>
<road>0 14 5</road>
<road>14 16 5</road>
<road>14 19 5</road>
<road>11 19 5</road>
<road>14 18 5</road>
<road>2 11 5</road>
<road>2 9 5</road>
<road>2 8 5</road>
<road>0 10 5</road>
<road>16 17 5</road>
<road>17 18 5</road>
<road>15 19 5</road>
<road>15 17 5</road>
<road>3 9 5</road>
<road>1 10 5</road>
<road>11 18 5</road>
<road>12 17 5</road>
<road>5 8 5</road>
<road>5 7 5</road>
<road>10 19 5</road>
<road>16 19 5</road>
<road>7 9 5</road>
<road>8 18 5</road>
<road>4 19 5</road>
<road>17 19 5</road>
<road>5 19 5</road>
<road>18 19 5</road>
相关代码：
这是我的道路.h：
#ifndef ROAD_H
#define ROAD_H
class Road{
public:
Road();
void setCityA(int);
const int getCityA() const;
void setCityB(int);
const int getCityB() const;
void setLength(double);
const double getLength() const;
friend bool operator<(const Road&, const Road&);
friend bool operator>(const Road&, const Road&);
friend bool operator>=(const Road&, const Road&);
friend bool operator<=(const Road&, const Road&);
Road *nextRoad;
private:
int cityA;
int cityB;
double length;
};
#endif
这是我的road.cpp：
#include"road.h"
Road::Road(){
nextRoad = 0;
}
void Road::setCityA(int x){
this->cityA = x;
}
const int Road::getCityA() const{
return this->cityA;
}
void Road::setCityB(int x){
this->cityB = x;
}
const int Road::getCityB() const{
return this->cityB;
}
void Road::setLength(double x){
this->length = x;
}
const double Road::getLength() const{
return this->length;
}
bool operator<(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() < rhs.getLength()) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityA() < rhs.getCityA()) && (lhs.getCityA() < rhs.getCityB()) ) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityB() < rhs.getCityA()) && (lhs.getCityB() < rhs.getCityB()) ) return 1;
else return 0;
}
bool operator>(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() > rhs.getLength()) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityA() > rhs.getCityA()) && (lhs.getCityA() > rhs.getCityB()) ) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityB() > rhs.getCityA()) && (lhs.getCityB() > rhs.getCityB()) ) return 1;
else return 0;
}
bool operator<=(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() < rhs.getLength()) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityA() < rhs.getCityA()) && (lhs.getCityA() < rhs.getCityB()) ) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityB() < rhs.getCityA()) && (lhs.getCityB() < rhs.getCityB()) ) return 1;
else return 0;;
}
bool operator>=(const Road &lhs, const Road &rhs)
{
if(lhs.getLength() > rhs.getLength()) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityA() > rhs.getCityA()) && (lhs.getCityA() > rhs.getCityB()) ) return 1;
else if( (lhs.getLength() == rhs.getLength()) && (lhs.getCityB() > rhs.getCityA()) && (lhs.getCityB() > rhs.getCityB()) ) return 1;
else return 0;
}
这是我的 minHeap.h （其中还包括它的实现）：
#ifndef MIN_HEAP
#define MIN_HEAP
template<class T>
class minHeap{
public:
minHeap(int);
void push(const T&);
void pop();
T top();
void doubleHeapCap();
bool isEmpty();
T *heap;
int heapSize;
int capacity;
};
template<class T>
minHeap<T>::minHeap(int theCapacity = 10){
if(theCapacity < 1) throw "Capacity must be >=1.";
capacity = theCapacity;
heapSize = 0;
heap = new T[capacity + 1]; //heap [0] is not used
}
template<class T>
void minHeap<T>::push(const T& e){
//inserts e into min heap
if(heapSize == capacity){ //doubles capacity if Heap is too small
this->doubleHeapCap();
this->capacity *=2;
}
int currentNode = ++heapSize;
while(currentNode != 1 && heap[currentNode/2] > e){
//bubble up node
heap[currentNode] = heap[currentNode/2]; //moves parent down
currentNode /= 2; //moves current node
}
heap[currentNode] = e;
}
template<class T>
void minHeap<T>::pop(){
//Deletes smallest element from heap and restructures heap
if(isEmpty()) throw "Heap is empty. Cannot delete.";
//deelt smallest element
heap[1].~T();
//remove last element from heap
T lastE = heap[heapSize--];
//trickle down to restructure heap
int currentNode = 1; //root of heap
int child = 2; // first child of heap
while(child <= heapSize){
//set child to smaller child of currentNode
if(child < heapSize && heap[child] > heap[child+1]) child++;
//can we put lastE in currenNode?
if(lastE <= heap[child]) break; //yes we can
//no we can't, Obama
heap[currentNode] = heap[child]; //move child up
currentNode = child; child *= 2; // move a level down
}
//after you finally find one, place the node in the corrent position
heap[currentNode] = lastE;
}
template<class T>
T minHeap<T>::top(){
return heap[1];
}
template<class T>
bool minHeap<T>::isEmpty(){
//says whether or not hear is empty
if(heapSize == 0) return 1;
else return 0;
}
template<class T>
void minHeap<T>::doubleHeapCap(){
int newCapacity = (this->capacity)*2;
T *temp;
T *newHeap;
//create a new heap with twic the size
newHeap = new T[newCapacity + 1];
//copy elements over
for(int i=0; i<=capacity; i++){
newHeap[i] = this->heap[i];
}
//delete the old heap
temp = heap;
heap = newHeap;
newHeap = 0;
delete[] temp;
}
#endif
请注意，小于和或等于和大于或等于的运算符分别与小于和大于相同，我这样定义它们只是因为我的 minHeap 使用了这两种类型的运算符，但在这种情况下有没有两条道路相等（我过滤掉任何可能相等的道路）。
感谢您的帮助，非常感谢任何输入