С помощью heap реализовать сортировку

204

10 апреля 2018, 05:29

Задача

Для списка пар pair<string,int>, где первое число — имя пользователя, второе — сумма набранных балов, с использованием heap реализовать вывод на консоль всех имён пользователей в отсортированном по убыванию баллов порядке.

Есть программа, но сортирует она не до конца:

#include <vector>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<string, int> P;
struct comparator
{
    bool operator()(const P &i, const P &j)
    {
        return i.second > j.second;
    }
};
class Pair
{
    vector<P> Students;
public:
    Pair() {};
    void Add()
    {
        Students = { { "Vasya", 10 }, { "Misha", 20 }, { "Anton", 30 }, { "Kolya", 40 }, { "Nikita", 50 }, { "Sasha", 60 } };
    }
    void Sort()
    {
        make_heap(Students.begin(), Students.end(), comparator());
        for (const P &i : Students)
            cout << i.first << ' ' << i.second << endl;
        cout << "\n";
        sort_heap(Students.begin(), Students.end());
        for (const P &i : Students)
            cout << i.first << ' ' << i.second << endl;
    }
};
int main()
{
    Pair Students;
    Students.Add();
    Students.Sort();
    system("pause");
}

Answer 1

Определять какие то структуры для данной задачи является излишной тратой времени и источником ошибок. Я не внимательно изучил, что вы написали, так как можно просто изменить условие компаратора и затем просто создать кучу:

typedef pair<string, int> P;
struct comparator
{
    bool operator()(const P &i, const P &j)
    {
        return i.second < j.second;
    }
};
int main()
{
    vector<P>  Students = { { "Vasya", 10 }, { "Misha", 20 }, { "Anton", 30 }, { "Kolya", 40 }, { "Nikita", 50 }, { "Sasha", 60 } };
    make_heap(Students.begin(), Students.end(), comparator());
    for (const P &i : Students)
               cout << i.first << ' ' << i.second << endl;
           cout << "\n";
    return 0;
}

Я использовал ваш код, доводя до состояния "попроще"