Я сделал свой собственный шаблон minHeap, который, кажется, прекрасно сортирует целые числа, но когда я пытаюсь отсортировать свой собственный класс, который я называю Road, он правильно сортирует примерно половину его …
Класс Road определяется так: он имеет два целых числа, называемых cityA и cityB, а также двойное число, называемое length.
При сравнении двух дорог A и B мы говорим, что A меньше, чем B, член длины A меньше, чем член длины B ИЛИ, если их длины равны, и A содержит наименьшее целое число в его городах из всех четырех городов (cityA и cityB в A и cityA и CityB в B).
Пример: RoadA имеет cityA = 4, cityB = 5, длина = 6; и RoadB имеет cityA = 1 cityB = 9, длина = 2. В этом сценарии RoadB меньше, потому что его длина меньше
Пример 2: RoadA имеет cityA = 4, cityB = 5, длина = 6; и RoadB имеет cityA = 1 cityB = 9, длина = 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>
СООТВЕТСТВУЮЩИЙ КОД:
Вот моя дорога.
#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 использует оба типа операторов, но в этом случае есть нет двух равных дорог (я отфильтрую все равные дороги).
Спасибо за помощь, любой вклад с благодарностью
С вашим> оператором дороги (0,8,5)> дороги (2,7,5), потому что 8> 2 & 8> 7
Других решений пока нет …