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

@Miskuzi · Регистрация: 16.09.2015

Студворк — интернет-сервис помощи студентам

Для списка пар pair<string,int>, где первое число - имя пользователя, второе - сумма набранных балов, с использованием heap реализовать вывод на консоль всех имён пользователей в отсортированном по убыванию баллов порядке.
В общем, саму сортировку я вроде как сделал, но вот как добавить ещё и имена? При выводе имён выводится какая-то абракадабра. Мб их нужно как-то по другому выводить, а не вот так printf("%s", v2.at(i)), как я делаю.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string.h>
int main()
{
    using namespace std;
    vector <int> v1;
    vector<string> v2;
    vector <int>::iterator Iter1, Iter2;
 
    int i, j = 0;
    for (i = 1; i <= 5; i++)
    {
        j = rand() % 100;
        v1.push_back(j);
    }
    v2.push_back("Vitya");
    v2.push_back("Kolya");
    v2.push_back("Nikita");
    v2.push_back("Jenya");
    v2.push_back("Sasha");
    make_heap(v1.begin(), v1.end());
    make_heap(v2.begin(), v2.end());
    i = 0;
    for (Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++)
    {
        printf("%s", v2.at(i));
        cout << " ";
        i++;
        cout << *Iter1 << "\n";
    }
    cout << "\n";
    for (i = 1; i <= 5; i++)
    {
        cout << v1.front() << "\n";
        pop_heap(v1.begin(), v1.end());
        v1.pop_back();
        push_heap(v1.begin(), v1.end());
    }
    system("pause");
}

@nmcf · 08.04.2018, 08:39

А где пары-то?

C++
1
cout << v2[i] << ' ' << *Iter1 << endl;

@Miskuzi · 08.04.2018, 08:54 **[ТС]**

Ну вот другая версия с парами

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <vector>
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <string>
 
using namespace std;
 
class Pair
{
    vector<string> name;
    vector<int> value;
    vector <int>::iterator Iter1;
public:
    Pair() {};
    void Add(string n, int v)
    {
        name.push_back(n);
        value.push_back(v);
    }
    void Sort()
    {
        int i;
        for (i = 1; i <= 5; i++)
        {
            cout << value.front() << "\n";
            pop_heap(value.begin(), value.end());
            value.pop_back();
            push_heap(value.begin(), value.end());
        }
}
int main()
{
    Pair Students;
    Students.Add("Vasya", 80);
    Students.Add("Misha", 70);
    Students.Add("Vova", 90);
    Students.Add("Sveta", 50);
    Students.Add("Anton", 100);
    
    Students.Sort();
    system("pause");
}

Но как сюда make_heap добавить? Куда именно нужно его пихать, чтобы не писало, что он не определён.

@nmcf · 08.04.2018, 09:12

Тебе уже в задании написали, как должно быть.

C++
1
2
3
4
5
6
7
8
9
typedef std::pair<string, int> P;
std::vector<P> Students = { {"Vasya", 80}, {"Misha", 70}, {"Anton", 100} };
std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second > b.second; });
 
std::sort_heap (Students.begin(), Students.end());
 
for (const P &i : Students)
    cout << i.first << ' ' << i.second << endl;
}

@Miskuzi · 08.04.2018, 09:48 **[ТС]**

И куда и вместо чего это запихнуть?)

Добавлено через 14 минут

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <string>
using namespace std;
int main()
{
    typedef std::pair<string, int> P;
    std::vector<P> Students = { { "Vasya", 80 }, { "Misha", 70 }, { "Anton", 100 } };
    std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second > b.second; });
 
    std::sort_heap(Students.begin(), Students.end());
 
    for (const P &i : Students)
        cout << i.first << ' ' << i.second << endl;
    system("pause");
}

Вот так вроде? Но вылезает invalid heap

@nmcf · 08.04.2018, 12:29

У меня же работает.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef std::pair<string, int> P;
 
int main()
{
  std::vector<P> Students = { {"Vasya", 80}, {"Misha", 70}, {"Anton", 100} };
  std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second > b.second; });
 
  std::sort_heap (Students.begin(), Students.end());
 
  for (const P &i : Students)
    cout << i.first << ' ' << i.second << endl;
}

@Miskuzi · 08.04.2018, 15:52 **[ТС]**

[img]https://i.**********/A7BocSy.png[/img]
У меня и так ошибка вот эта

Добавлено через 13 минут
Вроде вот так заработало все норм, но не сортирует до конца

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <cstdlib>
#include <conio.h>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef pair<string, int> P;
class Pair
{
    vector<P> Students;
public:
    Pair() {};
    void Add()
    {
        Students = { { "Vasya", 80 }, { "Misha", 70 }, { "Anton", 100 } };
    }
    void Sort()
    {
        make_heap(Students.begin(), Students.end());
         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");
}

Что нужно добавить?

@nmcf · 08.04.2018, 17:07

Так не будет работать. Смотри выше, как надо make_heap() вызывать.

@Miskuzi · 08.04.2018, 17:23 **[ТС]**

Если я так его вызываю, у меня вылезает ошибка со скрина

Добавлено через 7 минут
Так, запустил ваш код в онлайн компиляторе, с моим что-то хрень какая-то.
Но он сортирует только если будет всего 3 пары, если увеличить количество пар то опять же не до конца

Добавлено через 2 минуты
Можно ли как-то замутить вот это

C++
1
2
3
4
 cout << value.front() << "\n";
            pop_heap(value.begin(), value.end());
            value.pop_back();
            push_heap(value.begin(), value.end());

Только для пар? Чтобы по второму элементу пары вот такое делалось

@nmcf · 08.04.2018, 17:34

С любым количеством работает.
Что ты получить-то хочешь? Для упорядочивания по убывания достаточно вызова make_heap() с "меньше":

C++
1
std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second < b.second; });

@Miskuzi · 08.04.2018, 17:39 **[ТС]**

Ну вот я жахнул эту программу в компилятор

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef std::pair<string, int> P;
 
int main()
{
  std::vector<P> Students = {  { "Vasya", 80 }, { "Misha", 70 }, { "Anton", 100 }, { "Kolya", 50 }, { "Nikita", 40 }, { "Sasha", 80 } };
  std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second < b.second; });
 
  std::sort_heap (Students.begin(), Students.end());
 
  for (const P &i : Students)
    cout << i.first << ' ' << i.second << endl;
}

Вот это вывело

Kolya 50
Misha 70
Nikita 40
Sasha 80
Vasya 80
Anton 100

Чет вообще не отсортировано

@nmcf · 08.04.2018, 17:42

14-ю убери.

@Miskuzi · 08.04.2018, 17:44 **[ТС]**

Усё равно не то

Anton 100
Misha 70
Sasha 80
Kolya 50
Nikita 40
Vasya 80

@nmcf · 08.04.2018, 17:47

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
typedef std::pair<string, int> P;
 
int main()
{
  std::vector<P> Students = {  { "Vasya", 80 }, { "Misha", 70 }, { "Anton", 100 }, { "Kolya", 50 }, { "Nikita", 40 }, { "Sasha", 80 } };
  std::make_heap(Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second > b.second; });
 
  std::sort_heap (Students.begin(), Students.end(), [](const P &a, const P &b){ return a.second > b.second; });
 
  for (const P &i : Students)
    cout << i.first << ' ' << i.second << endl;
}

Anton 100
Vasya 80
Sasha 80
Misha 70
Kolya 50
Nikita 40

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	08.04.2018, 17:07
	Так не будет работать. Смотри выше, как надо make_heap() вызывать. 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	08.04.2018, 17:42
	14-ю убери. 0

@Miskuzi 0 / 0 / 0 Регистрация: 16.09.2015 Сообщений: 173
	08.04.2018, 17:44 [ТС]
	Усё равно не то Anton 100 Misha 70 Sasha 80 Kolya 50 Nikita 40 Vasya 80 0