олимпиадники-информатики

Давно здесь нечего не добовлялось и я решил добавть тему про кучу

Куча - структура данных, дерево, элементы которых удовлетворяют некоторым условиям. Существует много разных типов куч, но самой распространённой является двоичная или бинарная куча. Все её элементы должны выполнять два условия:

• Предок больше либо равен потомку в max-куче и меньше либо равен потомку в min-куче.
  
• У всех предков два потомка, но только у одного предка в куче может быть один потомок-лист

Индекс предка = индекс элемента div 2.


Индекс первого потомка = индекс элемента * 2
Индекс второго потомка (если есть) = индекс элемента * 2 + 1

Класс кучи:

// Перечесление типов кучи
enum heapType { MaxHeap, MinHeap };
 
template <class type> class heap
{  
public:
	// Конструктор
	heap(heapType ht = MaxHeap)
	{
		length = 0;
		heapT = ht;
	}
 
	// Перегрузка оператора
	type& operator[](int index)
	{
		return data[index];
	}
  
	// Всплытие элемента под номером. Возвращает новый номер этого же элемента
	int shiftUp(int index)
	{
		while (index > 1 && data[index / 2] < data[index] && heapT == MaxHeap || index > 1 && data[index / 2] > data[index] && heapT == MinHeap)
		{
			swap(data[index], data[index / 2]);
			index = index / 2;
		}
      
		return index;
	}
  
	// Потопление элемента под номером. Возвращает новый номер этого же элемента
	int shiftDown(int index)
	{
		bool finish = false;
      
  		while (2 * index <= length && !finish)
  		{
			int temp = index;
			if (data[2 * index] > data[temp] && heapT == MaxHeap || data[2 * index] < data[temp] && heapT == MinHeap)
  				temp = 2 * index;
			if (2 * index + 1 <= length && (data[2 * index + 1] > data[temp] && heapT == MaxHeap || data[2 * index + 1] < data[temp] && heapT == MinHeap))
  				temp = 2 * index + 1;
			if (index == temp)
				finish = true;
			else
  				swap(data[index], data[temp]);
  			index = temp;
		}
      
		return index;
	}
  
	// Преобразование массива в кучу
	void build()
	{
		for (int i = length / 2; i > 0; i--)
			shiftDown(i);
	}
  
	// Сортирует кучу по неубыванию
	void sort()
	{
		build();
      
		int t = length;
      
		while (length > 1)
		{
			swap(data[1], data[length]);
			length--;
			shiftDown(1);
		}
      
		length = t;
	}
  
	// Добовляет к этой куче кучу heap
	void concat(heap heap)
	{
		for (int i = 1; i <= heap.length; i++)
			add(heap[i]);
	}
 
  	// Добовление value в кучу. Возвращает новый номер этого же элемента
	int add(int value)
	{
		length++;
		data[length] = value;
		return shiftUp(length);
	}
 
        // Удаляет элемент под номером index из кучи
        int remove(int index)
        {
              data[index] = data[1] + 1;
              shiftUp(index);
              data[1] = data[length];
              length--;
              if (length)
                  return shiftDown(1);
              return 0;
        }
 
    // Возвращает первый элемент и удаляет его
    type first()
    {
          if (length)
          {
              type temp = data[1];
              remove(1);
              return temp;
          }
          else
              return 0;
    }
  
	// Ставит элемент под номером index на своё место. Возвращает новый номер этого же элемента
	int test(int index)
	{
		int f = shiftUp(index);
		if (f != index)
			return f;
		return shiftDown(index);
	}
 
	// Массив кучи
	type data[100000];
	// Длина кучи
	int length;
	// Тип кучи
	heapType heapT;
};

В скором времени напишу и на паскале.

Пример программы:

Увеличение приоритета №1164 на informatics.mccme.ru

#include <iostream>
 
using namespace std;
 
//ЗДЕСЬ КЛАСС КУЧИ
 
int main()
{
	heap<int> heap;
	int n;
 
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int t;
		cin >> t;
		heap.add(t);
	}
  
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		heap[a] += b;
		cout << heap.test(a) << "\n";
	}
  
	for (int i = 1; i <= heap.length; i++)
		cout << heap[i] << " ";
 
	system("pause > nul");
	return 0;
}

.

Но код то мой.) Просто на паскале всё это неудобно. А вообще напишу я на паскале, просто пока времени нету. К пятнице напишу.
Насчёт тырилки. С википедии наверно можно, я не написал что этл мой текст , а цитировал. Во всяком случае википедия объяснит лучше меня, на раз ты просиш, то к пятнице перепишу и это.

"Всплытие" и "затапливание" элементов кучи на паскале.

Допустим у нас n элементов и m запрос на изменение этих элементов. Запросы содержат два числа: pos и value, т.е. надо увеличить a[pos] на value. Но т.к. мы изменяем значение элемента, то вероятнее всего мы можем нарушить основное свойство кучи, т.е у нас может поток должен быть больше предка. Поэтому мы подымаем измененный элемент по кучи вверх, пока его предок не будет больше его или пока мы не доставим измененный элемент в вершину кучи.

Есть два способа сделать всплытие: через цикл while и рекурсией. Рассмотрим оба

 
procedure shift_up(pos:longint);
begin
  while (pos<>1) and (a[pos div 2] < a[pos]) do //пока не дошли до предка и потомок больше предка
    begin
      x:=a[pos div 2]; //меняем их местами
      a[pos div 2]:=a[pos];
      a[pos]:=x;
      pos:=pos div 2; //теперь мы в предке вершины pos
    end;
end;

 
procedure shift_up(pos:longint);
var x:longint;
begin
  if pos=1 then exit; //если мы в самом вверху, то вылетаем
  if a[pos div 2] < a[pos] //если потомок больше предка
    then //то меняем их местами
      begin 
        x:=a[pos div 2];
        a[pos div 2]:=a[pos];
        a[pos]:=x;
        shift_up(pos div 2); //подымаем предка наверх
      end;
end;

Рассмотрим затапливание элемента

У нас есть то же самое, что я описал выше, только теперь надо уменьшить a[pos] на value. Тогда опять нарушится условие кучи, т.к. предок получится меньше одного или двух своих потомков. Поэтому нам надо опускать наш a[pos] до тех пор, пока мы не придем в последний элемент или наш предок не станет больше потомка.

Опять же два способа: рекурсия и цикл while

 
procedure shift_down(pos:longint);
var pos2,x:longint;
begin
  while (2*pos<=n) do //пока мы не пришли в последний элемент
    begin
      pos2:=pos; 
      if (a[2*pos]>a[pos2]) //если левый потомок больше предка
        then pos2:=2*pos; //номеру предка присваем номер потомка
      if (2*pos+1<=n) and (a[2*pos+1]>a[pos2]) //если правый потомок есть и он больше предка
        then pos2:=2*pos+1; //номеру предка присваем номер потомка
      if (pos=pos2) then break; //если предок это потомок тогда вылетаем
      x:=a[pos]; //меняем местами предка и потомка
      a[pos]:=a[pos2];
      a[pos2]:=x;
      pos:=pos2; //номеру потомка присваем номер предка
    end;
end;

 
procedure shift_down(pos:longint);
var pos2:longint;
begin
  pos2:=pos; 
  if pos*2>n  then exit; //если пришли в последний элемент то вылетаем
  if a[pos*2]>a[pos2] //если левый потомок больше предка
    then pos2:=pos*2; //номеру предка присваем номер потомка
  if (pos*2+1<=n) and (a[pos*2+1]>a[pos2]) //если правый потомок есть и он больше предка 
    then pos2:=pos*2+1; //номеру предка присваем номер потомка
  if pos=pos2 then exit; //если предок это потомок тогда вылетаем
  x:=a[pos]; //меняем местами предка и потомка
  a[pos]:=a[pos2];
  a[pos2]:=x;
  shift_down(pos2);//топим потомка
end;