Двоичная куча
Andrew 10 ноя 2012
Давно здесь нечего не добовлялось и я решил добавть тему про кучу
Индекс первого потомка = индекс элемента * 2
Индекс второго потомка (если есть) = индекс элемента * 2 + 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; }
Andrew 14 ноя 2012
Но код то мой.) Просто на паскале всё это неудобно. А вообще напишу я на паскале, просто пока времени нету. К пятнице напишу.
Насчёт тырилки. С википедии наверно можно, я не написал что этл мой текст , а цитировал. Во всяком случае википедия объяснит лучше меня, на раз ты просиш, то к пятнице перепишу и это.
Насчёт тырилки. С википедии наверно можно, я не написал что этл мой текст , а цитировал. Во всяком случае википедия объяснит лучше меня, на раз ты просиш, то к пятнице перепишу и это.
Санек 16 ноя 2012
"Всплытие" и "затапливание" элементов кучи на паскале.
Допустим у нас n элементов и m запрос на изменение этих элементов. Запросы содержат два числа: pos и value, т.е. надо увеличить a[pos] на value. Но т.к. мы изменяем значение элемента, то вероятнее всего мы можем нарушить основное свойство кучи, т.е у нас может поток должен быть больше предка. Поэтому мы подымаем измененный элемент по кучи вверх, пока его предок не будет больше его или пока мы не доставим измененный элемент в вершину кучи.
Есть два способа сделать всплытие: через цикл while и рекурсией. Рассмотрим оба
Рассмотрим затапливание элемента
У нас есть то же самое, что я описал выше, только теперь надо уменьшить a[pos] на value. Тогда опять нарушится условие кучи, т.к. предок получится меньше одного или двух своих потомков. Поэтому нам надо опускать наш a[pos] до тех пор, пока мы не придем в последний элемент или наш предок не станет больше потомка.
Опять же два способа: рекурсия и цикл while
Допустим у нас 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;