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

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

Восстановить пароль Регистрация
 
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
12.05.2014, 02:36     Двоичная куча #1
Доброго времени суток. Выполняю зачетное задание, которое звучит так:
Данная задача состоит в реализации двоичной кучи. В первой строке ввода задаётся число 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++
C++ Двоичная быстрая сортировка
C++ двоичная система
алгоритм двоичная вставка C++
C++ Двоичная система счисления!
C++ двоичная система счисления
Двоичная(бинарная) сортировка C++
Двоичная обработка данных C++

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

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

Метки
куча
Опции темы

Текущее время: 03:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru