Работа с кучей.

[iCaesy]

Вот имеется задачка такого вида:



Есть немного кода:

var
  heap, place : array[1 .. MaxN] of integer; 
  hs : integer;

//"Всплывание" n-ого элемента кучи

procedure siftup(n : integer);
var
  t : integer;
begin
  if n = 1 then exit;
  if heap[n] > heap[n div 2] then begin
    t := heap[n];
    heap[n] := heap[n div 2];
    heap[n div 2] := t;
    place[heap[n]] := n;
    place[heap[n div 2]] := n div 2;
    siftup(n div 2);
  end;
end;

//Добавление элемента x в кучу

procedure ins(x : integer);
begin
  inc(hs);
  heap[hs] := x;
  place[x] := hs;
  siftup(hs);
end;

А дальше тупик, не пойму общую суть задачи, и входные / выходные данные тоже... Разъясните плиз.

[Poma][a]

Дается куча.. Где 6 элементов.. Вы загоняете эти 6 элементов в массив.. Далее Вы читаете кол-во элементов, приоритет которых нужно изменить (пусть их будет N) Далее крутим цикл от 1 до N. Читаем 2 числа : elem и key и Inc (a[elem], key). Далее Sift_Up'пим.. вуаля.. (не забываем после этого запомнить новое место)

[iCaesy]

Ну теперь хоть что-то понятно.
А что за числа elem key ?

И по поводу входных данных, первые две строчки понятно, первая это размер массива, вторая его элементы, а 3,4,5 не пойму ...

[Poma][a]

3 - N кол-во элементов приоритет которых надо изменить
Далее идет elem key ... elem - индекс кучи (см. рисунок - красненькое) key - значение на которое нужно увеличить..

[iCaesy]

Ужс.. Ладно спасибо, будем разбираться...

[iCaesy]

Пошаманил немного, вот что получилось, гляньте плз, вроде все верно но выводит не в том порядке как нужно...

const
  MaxN = MaxByte;

var
  heap, place: array[1.. MaxN] of integer; 
  hs: integer;
  index, znach, kol, i, size: byte;


//"Всплывание" n-ого элемента кучи

procedure siftup(n: integer);
var
  t: integer;
begin
  if n = 1 then exit;
  if heap[n] > heap[n div 2] then begin
    t := heap[n];
    heap[n] := heap[n div 2];
    heap[n div 2] := t;
    place[heap[n]] := n;
    place[heap[n div 2]] := n div 2;
    siftup(n div 2);
  end;
end;

//Добавление элемента x в кучу

procedure ins(x: integer);
begin
  inc(hs);
  heap[hs] := x;
  place[x] := hs;
  siftup(hs);
end;

procedure update(pos: byte; value: byte);
var
  temp: byte;
begin
  temp := heap[pos];
  heap[pos] := heap[pos] + value;
  siftup(hs);
end;

begin
  
  writeln('Введите кол-во элементов кучи: ');
  readln(size);
  for i := 1 to size do
  begin
    writeln('Введите ', i, '-й элемент');
    ins(ReadInteger());
  end;
  
  writeln('Сколько чисел будем менять: ');
  readln(kol);
  
  for i := 1 to kol do
  begin
    writeln('Введите индекс ', i, ' го элемента');
    readln(index);
    writeln('Введите значение для изменения');
    readln(znach);
    update(index,znach);
  end;
  
  for i := 1 to size do 
  begin
  writeln(heap[i])
  end;
end.

[Poma][a]

const
  MaxN = 100;

var
  heap : array[1.. MaxN] of integer; 
  hs: integer;
  index, znach, kol, i, size: byte;


//"Всплывание" n-ого элемента кучи

procedure siftup(n: integer);
var
  t: integer;
begin
	if n = 1 then
		Exit;
  if heap[n] > heap[n div 2] then begin
    t := heap[n];
    heap[n] := heap[n div 2];
    heap[n div 2] := t;
    siftup(n div 2);
  end;
end;

//Добавление элемента x в кучу

procedure ins(x: integer);
begin
  inc(hs);
  heap[hs] := x;
  siftup(hs);
end;

procedure update(pos: byte; value: byte);
begin
  heap[pos] := heap[pos] + value;
  siftup(pos); 
end;

var
	t : Integer;
begin

	hs := 0;
  writeln('Введите кол-во элементов кучи: ');
  readln(size);
  for i := 1 to size do
  begin
    ReadLn (t);
    ins(t);
  end; 

  
  writeln('Сколько чисел будем менять: ');
  readln(kol);
  
  for i := 1 to kol do
  begin
    writeln('Введите индекс ', i, ' го элемента');
    readln(index);
    writeln('Введите значение для изменения');
    readln(znach);
    update(index,znach);
  end;
  
  for i := 1 to hs do 
  begin
  writeln(heap[i])
  end;
end.

[iCaesy]

Понял спасибо.