1
Куча - структура данных, дерево, элементы которых удовлетворяют некоторым условиям. Существует много разных типов куч, но самой распространённой является двоичная или бинарная куча. Все её элементы должны выполнять два условия:
- Предок больше либо равен потомку в max-куче и меньше либо равен потомку в min-куче.
- У всех предков два потомка, но только у одного предка в куче может быть один потомок-лист
Индекс первого потомка = индекс элемента * 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
Запрос задаётся двумя целыми числами i и x. Требуется увеличить значение i-го элемента кучи на x. Гаран-тируется, что i ∈ [1; N], x ≥ 0, новое значение A[i]+x не превышает 10^9 и отличается от текущих значений всех остальных элементов кучи.
Формат входных данных: см. выше.
Формат выходных данных: в качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент. Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
http://informatics.m...hapterid=1164#1
Формат входных данных: см. выше.
Формат выходных данных: в качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент. Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
http://informatics.m...hapterid=1164#1
#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;
}
