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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Динамическая память в ООП http://www.cyberforum.ru/cpp-beginners/thread1172843.html
Здравствуйте, программа должна находить площадь и определять равносторонний ли треугольник. Площадь ищется только в случае равенства трех сторон треугольника. Значения вводятся с клавиатуры. Однако чего бы я не ввел, выводятся одни и те же неверные значения. Найдите пожалуйста в чем ошибка. #include "stdafx.h" #include "iostream" using namespace std; class triangle { int* A; ...
C++ Найти номер элемента массива модуль разности справа от которого наименьший ввести массив чисел без знака, количество которых заранее неизвестно.Ввод массива заканчивается вводом числа, уже имеющегося в массиве. Найти номер элемента массива модуль разности справа от которого наименьший.Значение элемента с этим номером при суммировании не учитывается. #include <iostream> #include <stdio.h> #include <conio.h> #include <malloc.h> #include <stdlib.h> int main() { http://www.cyberforum.ru/cpp-beginners/thread1172806.html
Упорядочить элементы одномерного массива по убыванию модулей элементов C++
Упорядочить элементы одномерного массива по убыванию модулей элементов.
C++ Зашифровать строку, выполнив циклическую замену каждой буквы
Перевести программу с паскаля на с++ // Дана строка-предложение на русском языке и число K (0 < K < 10). // Зашифровать строку, // выполнив циклическую замену каждой буквы на букву того же регистра, // расположенную в алфавите на K-й позиции после шифруемой буквы // (например, для K = 2 «А» перейдет в «В», «а» — в «в», «Б» — в «Г», «я» — в «б» и т. д.). // Букву «ё» в алфавите не...
C++ Структура "Автобус" http://www.cyberforum.ru/cpp-beginners/thread1172683.html
Как исправить зацикливание при неверном вводе данных в этой программе? Цель программы заключается в:составить программу которая содержит динамическую информацию о наличии автобусов в автобусном парке! #include <string.h> #include <dos.h> #include <iostream.h> #include <iomanip.h> #include <vcl.h> #include <stdlib.h> #include <conio.h>
C++ Машина Тьюринга: программа для преобразования десятичных чисел в унарную запись Помогите с выполнением. Тема машина Тьюринга. Задание:Составить программу для преобразования десятичных чисел {0,1,2,3,4,5,6,7,8,9} в унарную запись подробнее

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

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

12.05.2014, 02:36. Просмотров 735. Ответов 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;
}
Данная программа возвращает верный результат для тех данных, что указаны в примере (демонстрация), однако программа не производит тест (неправильный результат). Я так понимаю, что есть какой-то набор данных, на которых программа работает неправильно.
Есть какие-нибудь предположения, в чем может быть проблема?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru