How to implement a priority queue?

Question

C++ / C#

Good evening. The task needs to write a priority queue using a heap. It seems that I wrote everything, but for some reason it does not work: the wrong answer in the first test, although I entered the data from the example, and everything worked. What's wrong?

Task

Реализуйте приоритетную очередь. Ваша очередь должна поддерживать следующие операции:
добавить элемент, извлечь минимальный элемент, уменьшить элемент, добавленный во время одной
из операций.
Все операции нумеруются по порядку, начиная с единицы. Гарантируется, что размер очереди в
процессе выполнения команд не превысит 10^6
элементов.
Формат входного файла
Входной файл содержит описание операций с очередью. Операции могут быть следующими:
push x требуется добавить элемент x в очередь.
extract-min требуется удалить из очереди минимальный элемент и вывести его в выходной
файл. Если очередь пуста, в выходной файл требуется вывести звездочку *.
decrease-key x y требуется заменить значение элемента, добавленного в очередь операцией
push в строке входного файла номер x, на y. Гарантируется, что на строке x действительно
находится операция push, что этот элемент не был ранее удален операцией extract-min, и что
y меньше, чем предыдущее значение этого элемента.
В очередь помещаются и извлекаются только целые числа, не превышающие по модулю 10^9.

Example
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;
}

And another question: is it possible to somehow do without "pair", and is it generally used correctly?

Answer 1

So far I see a problem that 100% will lead to a time limit. When you change the priority, you search the entire queue. If you are given 500,000 additions to the queue, and then 500,000 decrements of a random element, then you will wait a very long time for the program to complete.
It is necessary to maintain an array of positions for all IDs. With any movement of a pair of elements in an array in the queue, this array of positions must be updated.
When changing the priority, no find is needed anymore, because the position will already be available in the array.
When adding a new element, you don't need to call build_heap. just shift_up from the new element is enough. You do not have this function separately in the program, but it is actually implemented in decrease_key. Only it is necessary, again, it is not passed through the entire queue, but only through the fathers. In the loop, you need to do not i--, but i = (i + 1) / 2-1.
And the error is just in decrease_key. You have a loop on i, and k is used all the time inside.