@Nikitos2002

Как реализовать приоритетную очередь?

Добрый вечер. В задаче требуется написать приоритетную очередь, используя кучу. Вроде бы, все написал, но почему-то не работает: неправильный ответ в первом тесте, хотя вводил данные из примера, и все работало. Что не так?
Задача
Реализуйте приоритетную очередь. Ваша очередь должна поддерживать следующие операции:
добавить элемент, извлечь минимальный элемент, уменьшить элемент, добавленный во время одной
из операций.
Все операции нумеруются по порядку, начиная с единицы. Гарантируется, что размер очереди в
процессе выполнения команд не превысит 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", и вообще правильно ли он использован?
  • Вопрос задан
  • 98 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Пока вижу проблему, которая 100% приведет к тайм-лимиту. Вы при изменении приоритета ищите по всей очереди. Если вам дадут 500000 добавлений в очередь, а потом 500000 уменьшений случаного элемента, то ждать вы завершения программы будете очень долго.

Надо поддерживать массив позиций по по всем айдишникам. При любом перемещении пары элементов в массиве в очереди надо обновлять этот массив позиций.

При изменении приоретета уже не надо никакого find, потому что позиция уже будет доступна в массиве.

При добавлении нового элемента не надо вызывать build_heap. достаточно только shift_up от нового элемента. У вас в программе отдельно этой функции нет, но она фактически реализована в decrease_key. Только нужно, опять же, проходится не по всей очереди, а только по отцам. В цикле надо делать не i--, а i = (i+1)/2-1.

И ошибка как раз в decrease_key, У вас цикл по i, а внутри все время используется k.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
06 мар. 2021, в 02:23
120000 руб./за проект
06 мар. 2021, в 00:29
500 руб./за проект
05 мар. 2021, в 23:28
1200 руб./за проект