Добрый вечер. В задаче требуется написать приоритетную очередь, используя кучу. Вроде бы, все написал, но почему-то не работает: неправильный ответ в первом тесте, хотя вводил данные из примера, и все работало. Что не так?
ЗадачаРеализуйте приоритетную очередь. Ваша очередь должна поддерживать следующие операции:
добавить элемент, извлечь минимальный элемент, уменьшить элемент, добавленный во время одной
из операций.
Все операции нумеруются по порядку, начиная с единицы. Гарантируется, что размер очереди в
процессе выполнения команд не превысит 10^6
элементов.
Формат входного файла
Входной файл содержит описание операций с очередью. Операции могут быть следующими:
push x требуется добавить элемент x в очередь.
extract-min требуется удалить из очереди минимальный элемент и вывести его в выходной
файл. Если очередь пуста, в выходной файл требуется вывести звездочку *.
decrease-key x y требуется заменить значение элемента, добавленного в очередь операцией
push в строке входного файла номер x, на y. Гарантируется, что на строке x действительно
находится операция push, что этот элемент не был ранее удален операцией extract-min, и что
y меньше, чем предыдущее значение этого элемента.
В очередь помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.
Пример
priorityqueue.in
push 3
push 4
push 2
extract-min
decrease-key 2 1
extract-min
extract-min
extract-min
priorityqueue.out
2
1
3
*
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int full = 0;
void siftdown(pair <int, int>* A, int i)
{
int left = 2 * i + 1;
int right = 2 * i + 2;
int less = i;
if (left < full && A[left].first < A[less].first)
less = left;
if (right < full && A[right].first < A[less].first)
less = right;
if (less != i)
{
swap(A[i], A[less]);
siftdown(A, less);
}
}
void build_heap(pair <int, int>* A)
{
for (int i = full / 2 - 1; i >= 0; i--)
siftdown(A, i);
}
void push(int x, pair<int, int>* A, int i)
{
A[full].first = x;
A[full].second = i;
full++;
build_heap(A);
}
char extract_min(pair<int, int>* A)
{
char val;
if (!full)
return '*';
else
{
val = A[0].first + '0';
swap(A[0], A[full - 1]);
full--;
siftdown(A, 0);
return val;
}
}
int find(pair<int, int>* A, int x)
{
for (int i = 0; i < full; i++)
if (A[i].second == x)
return i;
return -1;
}
void decrease_key(pair <int, int>* A, int x, int y)
{
int k = find(A, x);
A[k].first = y;
for (int i = k; i > 0; i--)
{
if (A[k].first < A[(k + 1) / 2 - 1].first)
swap(A[k], A[(k + 1) / 2 - 1]);
}
}
int main()
{
int i = 0;
string str;
pair<int, int>* A = new pair <int, int>[1000000];
ifstream fin;
ofstream fout;
fin.open("priorityqueue.in");
fout.open("priotyqueue.out");
while (!fin.eof())
{
i++;
int x, y;
fin >> str;
if (str == "push")
{
fin >> x;
push(x, A, i);
}
else if (str == "extract-min")
{
fout << extract_min(A) << '\n';
}
else if (str == "decrease-key")
{
fin >> x >> y;
decrease_key(A, x, y);
}
}
fout.close();
fin.close();
return 0;
}
И еще такой вопрос: можно ли как-нибудь обойтись без "pair", и вообще правильно ли он использован?
