Куча - структура данных, дерево, элементы которых удовлетворяют некоторым условиям. Существует много разных типов куч, но самой распространённой является двоичная или бинарная куча. Все её элементы должны выполнять два условия:
- Предок больше либо равен потомку в 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; }