整数を完全にソートするように見える独自のminHeapテンプレートを作成しましたが、Roadと呼ぶ独自のクラスをソートしようとすると、その約半分が正しくソートされます...
Road クラスは次のように定義されています。これには、cityA と cityB という 2 つの整数と、length という double があります。
2 つの道路 A と B を比較するとき、A は B より短い A の長さのメンバーが B の長さのメンバーよりも小さい、またはそれらの長さが等しく、A が 4 つの都市すべての都市で最小の整数を含む場合 (A の cityA と cityB とB の cityA と CityB)。
例: 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 があります。このシナリオでは、最小の整数 (cityA=1) を持つ都市が含まれているため、RoadB は小さくなります。
私はこれを私の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>
しかし、代わりに私のテストプログラムは次のように出力します:
<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>
関連コード:
これが私の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
以下と等しいおよび以上の演算子は、それぞれより小さいおよびより大きいと同じであることに注意してください。等しい 2 つの道路はありません (等しい可能性がある道路は除外します)。
助けてくれてありがとう、どんな意見でも大歓迎です