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

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

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

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

12.05.2014, 02:36. Просмотров 767. Ответов 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;
}
Данная программа возвращает верный результат для тех данных, что указаны в примере (демонстрация), однако программа не производит тест (неправильный результат). Я так понимаю, что есть какой-то набор данных, на которых программа работает неправильно.
Есть какие-нибудь предположения, в чем может быть проблема?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.05.2014, 02:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Двоичная куча (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2014, 02:36
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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