Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 1
#1

Двоичная куча - C++

12.05.2014, 02:36. Просмотров 734. Ответов 0

Доброго времени суток. Выполняю зачетное задание, которое звучит так:
Данная задача состоит в реализации двоичной кучи. В первой строке ввода задаётся число n (1≤n≤10^5), далее n строк вида Insert X, где X — натуральное число, не превосходящее 109, или Extract. Первая операция должна добавлять в кучу число X, вторая должна извлекать максимум из кучи и выводить его в очередной строке вывода.
Sample Input:
6
Insert 100
Insert 10
Extract
Insert 5
Insert 50
Extract

Sample Output:

100
50
Написал следующее:
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
 
using namespace std;
 
class SimpleBinaryHeap {
 
    vector<int> heap_data;
 
public:
 
    void insert(int value) {
 
        heap_data.push_back(value);
 
        int index = heap_data.size() - 1;
        int parent = (index - 1) / 2;
 
        while(index > 0 && heap_data[parent] < heap_data[index]) {
 
            swap(heap_data[parent], heap_data[index]);
 
            index =  parent;
            parent = (index - 1) / 2;
 
        } //while
 
    } //insert
 
    int extract() {
 
        int res = heap_data[0];
        heap_data[0] = heap_data[heap_data.size()-1];
 
        int index = 0;
 
        while(index < heap_data.size() - 1) {
 
            if(heap_data[index] > heap_data[index / 2]) {
                swap(heap_data[index], heap_data[index / 2]);
                index *= 2;
            } else {
                swap(heap_data[index], heap_data[index / 2 + 1]);
                index = index * 2 + 1;
            }
 
        } //while
 
        heap_data.pop_back();
 
        return res;
 
    } //extract
 
    void print() {
 
        for(register int i = 0; i < heap_data.size(); i++) {
 
            cout << heap_data[i] << " ";
 
        }
 
        cout << endl;
 
    }
 
};
 
int main() {
 
    SimpleBinaryHeap bh;
 
    string command;
    const char* com_insert = "Insert";
    const char* com_extract = "Extract";
 
    short num;
    cin >> num;
 
    for(short int i = 0; i < num; i++) {
 
        cin >> command;
        if(command == com_insert) {
            int value;
            cin >> value;
            bh.insert(value);
        }
        if(command == com_extract) {
            cout << bh.extract() << endl;
        }
 
    }
 
    return 0;
}
Данная программа возвращает верный результат для тех данных, что указаны в примере (демонстрация), однако программа не производит тест (неправильный результат). Я так понимаю, что есть какой-то набор данных, на которых программа работает неправильно.
Есть какие-нибудь предположения, в чем может быть проблема?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2014, 02:36     Двоичная куча
Посмотрите здесь:

двоичная система - C++
перевод из десятичной в двоичную скажите как записать результат в обратном порядке!! #include &lt;iostream&gt; #include &lt;string&gt; using...

Двоичная система - C++
Нужно написать программу на СИ(не на си++), чтоб та Представляла заданное число в двоичной системе . Заранее спасибо

Двоичная обработка данных - C++
Есть такая программа по двоичной обработке массива. Я не совсем понимаю, как здесь менять биты местами, к примеру наложением маски...

Двоичная быстрая сортировка - C++
всем здарасте) В общем мне задали курсовую работу написать на С++, тема очень странная &quot;Двоичная быстрая сортировка&quot;((((.... Я пошустрил...

алгоритм двоичная вставка - C++
Приведите программную реализацию алгоритма сортировки методом двоичной вставки. Получите для неё эмпирические оценки функции роста...

Двоичная система счисления - C++
как написать програму которая переводить цифру в двоичну систему счисления.c++

Двоичная система счисления - C++
Всем привет.Нужна помощь.Осваиваю язык. Пытаюсь написать программу перевода в двоичную систему счисления. Что делаю не так? ...

Двоичная(бинарная) сортировка - C++
Бегло прочел про эту сортировку и понял что она ориентирована на числовые заранее отсортированные массивы. А возможно ли ней например...

рекурсия + двоичная система + Фибоначчи - C++
Написать рекурсивную функцию перевода десятичного числа в двоичное и используя ее найти и вывести на печать двоичные коды первых 100 чисел...

Найти все натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром - C++
Пожалуйста решите эту задачу, никак не могу!( Найти все натуральные числа, не превосходящие n, двоичная запись которых представляет...

Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром - C++
Найти все простые натуральные числа, не превосходящие n, двоичная запись которых представляет собой палиндром, т.е. читается одинаково...

Куча вопросов.. - C++
В связи с последовательным изучением С++ и с параллельным при этом отсутствием рабочего подключения к Интернету у меня накопилась куча...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru