Почему мои сортировки MinHeap корректно, но не мой собственный класс

Question

Я создал свой собственный шаблон minHeap, который, кажется, отлично сортирует целые числа, но когда я пытаюсь сортировать свой собственный класс, который я называю Road, он сортирует примерно половину его правильно. ..

Класс Road определяется как таковой: он имеет два целых числа, называемых cityA и cityB, а также двойную названную длину.

При сравнении двух дорог A и B мы говорим, что A меньше, чем B, член длины A меньше, чем элемент длины B, или если их длины равны и A содержит наименьшее целое число в его городах всех четырех городов (cityA и cityB в A и cityA и CityB в B).

Пример: RoadA имеет городA = 4, cityB = 5, length = 6; и RoadB имеет cityA = 1 cityB = 9, length = 2. В этом сценарии RoadB меньше, потому что его длина меньше

Пример2: RoadA имеет городA = 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> 

Но ВМЕСТО моя тестовая программа выводит следующее:

<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 

Обратите внимание, что операторы с меньшим или равным и большим или равным равны и меньше или больше, чем, соответственно, я определил их таким образом только потому, что мой minHeap использует оба типа операторов, но в этом В случае отсутствия двух дорог, которые равны (я отфильтровываю любые дороги, которые могут быть равны).

Спасибо за помощь, любой вклад высоко ценится

Answer 1

С вашим> оператор дороги (0,8,5)> дорога (2,7,5), потому что 8> 2 & 8> 7