Куча примеры. Двоичная куча. Синонимы к слову куча
Память, которую используют программы, состоит из нескольких частей — сегментов :
Сегмент кода (или ещё «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.
Сегмент bss (или ещё «неинициализированный сегмент данных»), где хранятся глобальные и , инициализированные нулём.
Сегмент данных (или ещё «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.
К уча , откуда выделяются динамические переменные.
Стек вызовов , где хранятся , локальные переменные и другая информация, связанная с функциями.
В этом уроке мы рассмотрим только кучу и стек, поскольку всё самое интересное происходит именно здесь.
Куча
Сегмент кучи (или просто «куча ») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче в .
В C++, при использовании оператора new для выделения динамической памяти, эта память выделяется в сегменте кучи самой программы:
int *ptr = new int; // для ptr выделяется 4 байта из кучи int *array = new int; // для array выделяется 40 байт из кучи
Адрес выделяемой памяти передаётся обратно оператором new и затем он может быть сохранён в . О механизме хранения и выделения свободной памяти нам сейчас беспокоиться незачем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!
int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не иметь последовательных адресов
При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, а просто приводит к возврату памяти по этому адресу обратно в операционную систему.
Куча имеет свои преимущества и недостатки:
Выделение памяти в куче сравнительно медленное.
Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока программа не завершит своё выполнение.
Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.
Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших , или классов.
Стек вызовов
Стек вызовов (или просто «стек ») отслеживает все активные функции (те, которые были вызваны, но ещё не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных.
Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных.
Стек как структура данных
Структура данных в программировании - это механизм организации данных для их эффективного использования. Вы уже видели несколько типов структур данных, таких как массивы и структуры. Существует ещё много других структур данных, которые обычно используются в программировании. Некоторые из них реализованы в стандартной библиотеке C++, и стек является одним из таковых.
Например, рассмотрим стопку (аналогия - стек) тарелок на столе. Поскольку каждая тарелка тяжёлая, а они ещё сложены друг на друге, то вы сможете сделать что-то одно из следующего:
Посмотреть на поверхность первой тарелки (которая находится на самом верху).
Взять верхнюю тарелку из стопки (обнажая таким образом следующую тарелку, которая находится под ней - если она вообще есть).
Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку — если она вообще была).
В компьютерном программировании стек представляет собой контейнер, как структуру данных, который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ »), стек более ограничен. Операции, которые могут выполняться в стеке, соответствуют трём перечисленным выше. В стеке вы можете :
Посмотреть на верхний элемент стека (используя функцию top () или peek () ).
Вытянуть верхний элемент стека (используя функцию pop () ).
Добавить новый элемент поверх стека (используя функцию push () ).
Стек - это структура данных типа LIFO (англ. «L ast I n, F irst O ut» - «Последним пришёл, первым ушёл»). Последний элемент, который будет находиться на вершине стека, первым и уйдёт из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмёте. По мере того, как элементы помещаются в стек - стек растёт, по мере того, как элементы удаляются со стека - стек уменьшается.
Например, рассмотрим коротенькую последовательность, показывающую, как работает добавление и удаление в стеке:
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1
Стопка тарелок довольно-таки хорошая аналогия работы стека, но есть аналогия и получше. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздём к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?
Во-первых, мы используем наклейку для обозначения того, где находится самый нижний пустой почтовый ящик. Вначале это будет первый почтовый ящик, который находится на полу. Когда мы добавим элемент в наш стек почтовых ящиков, то мы поместим этот элемент в почтовый ящик, на котором будет наклейка (т.е. в самый первый пустой почтовый ящик на полу), а затем переместим наклейку на один почтовый ящик выше. Когда мы вытаскиваем элемент из стека, то мы перемещаем наклейку на один почтовый ящик ниже и удаляем элемент из почтового ящика. Всё, что находится ниже наклейки — находится в стеке. Всё, что находится в ящике с наклейкой и выше - находится вне стека.
Сегмент стека вызовов
Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает своё выполнение.
Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения.
Наша аналогия с почтовыми ящиками - это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем и вытягиваем из стека, называются фреймами (или еще «кадрами ») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.
Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, то нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находится в стеке.
Стек вызовов на практике
Давайте рассмотрим более подробно, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции :
Программа сталкивается с вызовом функции.
Фрейм стека создаётся и помещается в стек. Он состоит из:
Адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес »). Так процессор запоминает, куда возвращаться после выполнения функции.
Аргументов функции.
Памяти для локальных переменных.
Сохранённых копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит своё выполнение.
Процессор переходит к точке начала выполнения функции.
Инструкции внутри функции начинают выполняться.
После завершения функции, выполняются следующие шаги :
Регистры восстанавливаются из стека вызовов.
Фрейм стека вытягивается из стека. Освобождается память, которая была выделена для всех локальных переменных и аргументов.
Обрабатывается возвращаемое значение.
ЦП возобновляет выполнение кода (исходя из обратного адреса).
Возвращаемые значения могут обрабатываться разными способами, в зависимости от архитектуры компьютера. Некоторые архитектуры считают возвращаемое значение частью фрейма стека. Другие используют регистры процессора.
Знать все детали работы стека вызовов не так уж и важно. Однако понимание того, что функции при вызове добавляются в стек, а при завершении выполнения - удаляются из стека, даёт основы, необходимые для понимания рекурсии, а также некоторых других концепций, которые полезны при программ.
Пример стека вызовов
Рассмотрим следующий фрагмент кода:
Стек вызовов этой программы выглядит следующим образом:
boo() (включая параметр b)
main()
Переполнение стека
Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объём информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых других Unix-системах этот размер может достигать и 8 МБ. Если программа пытается поместить в стек слишком много информации, то это приведёт к переполнению стека. Переполнение стека (англ. «stack overflow» ) происходит, когда запрашиваемой памяти нет в наличии (вся память уже занята).
Переполнение стека является результатом добавления слишком большого количества переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, где функция A вызывает функцию B, которая, в свою очередь, вызывает функцию C, а та вызывает функцию D и т.д.). Переполнение стека обычно приводит к сбою в программе. Например:
int main() { int stack; return 0; }
int main () int stack [ 1000000000 ] ; return 0 ; |
Эта программа пытается добавить огромный массив в стек вызовов. Поскольку размера стека недостаточно для обработки такого массива, то его добавление переходит и на другие части памяти, которые программа использовать не может. Следовательно, получаем сбой.
Вот ещё одна программа, которая вызовет переполнение стека, но уже по другой причине:
void boo() { boo(); } int main() { boo(); return 0; }
Синонимы:
Ворох, громада, груда, горка, кипа, купа, сугроб; скирд, стог, омет.
Тела лежали грудами. В этом селе избы стоят гнездами. Деревья стоят купами. Стог (скирд) сена. Кладь (одонье, одонья, зарод) хлеба. Омет соломы..
Ср. . См. возвышенность, ворох, много
высыпать кучу новостей, собрать в кучу... ..
Словарь русских синонимов 4
куча
Синонимы:
бездна, бесчисленность, бунт, вагон, воз, ворох, гибель, гора, груда, купа, кучка, масса, множество, навал, нагромождение, пропасть, прорва, руно, сила, скопление, сорус, спод, стог, сугроб, тьма, тьма тем, тьма-тьмущая, уйма, уймища
КУЧА значение
Т.Ф. Ефремова Новый словарь русского языка. Толково- словообразовательный
куча
Значение:
ку ́ча
ж.а) Что-л., сваленное горкой, грудой.
б) разг. Большое количество, скопление чего-л.
2) разг. Толпа, скопление (людей, животных).
3) разг. Большое количество, множество.
С.И. Ожегов, Н.Ю. Шведова Толковый словарь русского языка
куча
Значение:
КУ́ЧА, -и, ж.
1. Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.
2. чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей.
Куча мала! возглас в детской игре, по к-рому начинается общая свалка.
| уменьш. кучка , -и, ж. (к 1 знач. ).
Малый академический словарь русского языка
куча
Значение:
И, ж.
Большое количество чего-л., обычно сыпучего, мелкого, наваленное, насыпанное в одном месте.
Куча песку. Куча камней.
У хижин, на рогожках, кучами лежали овощи и сушились на солнце.
Большое количество каких-л. предметов, нагроможденных в беспорядке один на другой; груда.
Комната отделялась от улицы широкими сенями, где были свалены в кучу корзины, сети --- и всякая хозяйственная утварь. Кетлинская, Мужество.
2. Разг.
Беспорядочное скопление людей, животных.
На берегу теснилась куча негров и негритянок. И. Гончаров, Фрегат «Паллада».
От Вязьмы французские войска, прежде шедшие тремя колоннами, шли теперь одною кучей. Л. Толстой, Война и мир.
{Овцы} неподвижно стоят, сбившись в кучу, спасаясь от жары и оводов. Серафимович, Лихорадка.
кого-чего. Разг. Большое количество; множество.
Покупателей этих произведений {лубочных картин} обыкновенно немного, но зато зрителей - куча. Гоголь, Портрет.
Мы видели в предыдущей главе, что добродетельная женщина наделала кучу глупостей. Писарев, Кукольная трагедия с букетом гражданской скорби.
- У меня куча дел накопилась в управлении, - сказал он весело. Крымов, Танкер «Дербент».
Так как листок пишется с нуля, то в нём хватает опечаток, неточностей и ошибок. Если вы заметили опечатку или ошибку, выделите её, нажмите Ctrl+Enter и опишите проблему. Желательно также написать ещё и её решение.Точно также можно поступить, если какой-то кусок текста совсем непонятен. А если вы можете предложить замену некоторой части на гораздо более понятный текст — то будет просто замечательно!
Введение
После всего изученного нами остался небольшой неизученный "должок" — "быстрые" сортировки. Мы уже разбирали несколько алгоритмов, работающих за квадратичное время — сортировка пузырьком, выбором, вставкой. Эти алгоритмы просты, но требуют оптимизации, когда дело доходит до больших массивов. Для каждого из них существуют оптимизации, делающие их "быстрыми" — то есть работающими за время n log n .
Начнём с того, что "вспомним" старые сортировки. Да, мы уже решали эти задачи, но, пожалуйста, напишите код для них заново. Это будет хорошим упражнением для начала года.
01: Сортировка пузырьком
Дан список целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный список на экран.
пузырьковой сортировки . Решение оформите в виде функции bubble_sort(A) .
В алгоритме пузырьковой сортировки осуществляется проход по списку от начала к концу, и если два соседних элемента списка стоят в неверном порядке, то они переставляются в правильном порядке. В результате минимальный элемент списка окажется на последнем месте. Будем повторять эту операцию до тех пор, пока приходится хоть что-то менять местами.
| Ввод | Вывод |
|---|---|
| 1 4 2 3 4 | 4 4 3 2 1 |
02: Сортировка выбором
Дан список целых чисел. Выведите все элементы этого списка в порядке невозрастания значений. Выведите новый список на экран.
Решите эту задачу при помощи алгоритма сортировки выбором . Решение оформите в виде функции selection_sort(A) .
В алгоритме сортировки выбором начальная часть списка уже отсортирована. Мы находим наибольший элемент в оставшейся части списка полным перебором и ставим его в конец отсортированной части (просто обменом).
Вспомогательным списком пользоваться нельзя.
| Ввод | Вывод |
|---|---|
| 1 4 2 3 4 | 4 4 3 2 1 |
03: Сортировка вставкой
Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.
Решите эту задачу при помощи алгоритма сортировки вставкой . Решение оформите в виде функции insertion_sort(A) .
В этой задаче нельзя пользоваться дополнительным списком и операциями удаления и вставки элементов.
В алгоритме сортировки вставкой в каждый произвольный момент начальная часть списка уже отсортирована. Далее первый элемент из неотсортированной части добавляется в отсортированную часть списка. Для этого находится позиция, в которую необходимо вставить элемент, затем осуществляется циклический сдвиг фрагмента уже отсортированной части.
Обратите внимание, на почти отсортированном массиве ваш алгоритм не должен работать за квадратичное время.
Поиск подходящего места для вставки можно сделать бинарным поиском. При этом можно пользоваться модулем bisect (см. документацию и по-русски).
| Ввод | Вывод |
|---|---|
| 1 4 2 3 4 | 1 2 3 4 4 |
От сортировки выбором к пирамидальной сортировке
Для определённости будем сортировать массив по возрастанию. (Точнее, по неубыванию, так как в массиве могут быть совпадающие элементы).
Основная схема сортировки выбором сохраняется. Массив разделен на две части, одна из которых (правая) уже отсортирована, причем любой элемент отсортированной части не меньше любого элемента неотсортированной:
Пока размер неотсортированной части > 1 выполнять | найти максимальный элемент | переставить его в конец отсортированной части конец Что здесь можно ускорить? Только поиск максимального элемента: ведь перенос элемента и так занимает O(1) (в расчёте на весь массив – O(n) ).
В простой сортировке выбором мы за k-1 сравнение (где k – длина неотсортированной части) всего лишь находили максимальный (минимальный) элемент. При этом мы часто получали информацию про относительные величины некоторых пар элементов, но «забывали» её. В пирамидальной сортировке эта информация будет сохраняться. Другими словами: неотсортированная часть будет не совсем беспорядочной - она будет иметь внутреннюю структуру, которая позволит каждый раз быстро выбирать максимальный элемент.
Для его реализации этого "сохранения" понадобится структура данных, называемая двоичной (бинарной) кучей или пирамидой (По-английски эта структура данных называется heap , дословный перевод – куча, но термин пирамида , который тоже иногда используется, лучше соответствует сути дела. Рассматриваемый здесь алгоритм сортировки называют сортировкой с помощью кучи, пирамидальной сортировкой или, реже, сортировкой деревом.). Одновременно с этим окажется удобно изучить также основанную на куче приоритетную очередь. Как быстро нужно уметь извлекать из кучи максимальный элемент? Чтобы сложность сортировки была O(n log n) , достаточно, чтобы время выбора было O(log n) ). Основная идея кучи состоит в том, что мы рассматриваем массив как представление двоичного дерева и вводим некоторый порядок на узлах этого дерева.
Итак, если мы реализуем такую структуру, то алгоритм сортировки приобретёт следующий вид:
Преобразовать массив в кучу (пирамиду) пока размер кучи > 1 выполнять | выбрать максимальный элемент и перенести его в отсортированную часть конец
Приоритетная очередь
Легко заметить, что задача реализации кучи родственна задаче эффективной реализации приоритетной очереди. (Это очередь, в которой важно не то, кто «встал» раньше, а кто «главнее». Более точно: при помещении в очередь указывается приоритет помещаемого элемента, а при взятии из очереди выбирается один из элементов с наибольшим приоритетом. В учебных задачах для простоты приоритетом обычно служит само значение элемента).
Ведь и в сортировке выбором, и в реализации приоритетной очереди требуется быстро извлекать максимальный элемент. Однако приоритетная очередь, сверх того, должна уметь быстро добавлять новый элемент, не нарушая своей внутренней структуры.
Будет удобно на время отвлечься от сортировки и разобрать подробно реализацию приоритетной очереди на основе кучи.
Двоичная куча (пирамида)
Следующая картинка показывает, как можно отобразить элементы массива A на вершины двоичного дерева:
A / \ A A / \ / \ A A A A / A Заметим, что при этом получается дерево вполне определённой формы: все его уровни, кроме, возможно, самого нижнего, заполнены целиком. А на самом нижнем уровне все пустые места, если они есть, располагаются правее имеющихся вершин. Будем называть такое двоичное дерево почти полным . Из рисунка нетрудно видеть, что родитель вершины с индексом i имеет индекс (i-1)//2 , а левая и правая дочерние вершины имеют индексы 2i+1 и 2i+2 соответственно.
Высотой дерева будем называть число уровней в дереве (или, что то же самое, длину пути от корня до самого дальнего листа плюс один). Так, для дерева на рисунке длина пути от корня до листа A равна 3, а высота равна 4. Полезно установить связь между высотой h и числом вершин дерева s .
Упражнение. Сколько вершин может иметь почти полное двоичное дерево высоты h ? Выразите высоту почти полного двоичного дерева через число вершин.
Чтобы быстро искать максимум в этом дереве, расположим элементы массива так, чтобы значение любого элемента было не меньше значений всех его потомков (если они существуют). Для этого достаточно, чтобы для каждого i выполнялись два неравенства: A[i] ≥ A (если 2i+1 ≤ s ), и A[i] ≥ A (если 2i + 2 ≤ s ). Вообще говоря, часто будет удобно, чтобы этому правилу подчинялись не обязательно все элементы массива, а лишь элементы его некоторого начального участка. Этот участок и будем называть кучей. Будем обозначать размер всего массива n , а размер кучи – s . Размер кучи может меняться от 0 до n включительно.
Итак, двоичной максимальной кучей будем называть некоторое начало A…A массива A…A , (0 ≤ s ≤ n ) если каждый его элемент обладает основным свойством максимальной кучи: его значение не меньше значений всех его потомков.
Нетрудно доказать, что максимальный элемент в такой куче имеет индекс 0 в массиве (находится в корне дерева). Если потребовать, чтобы элемент был не больше своих потомков, получим минимальную кучу . (Мы будем рассматривать, в основном, максимальные кучи). Обратите внимание, что «физически» куча – это участок массива. А «логически» её удобно рассматривать как двоичное дерево.
Операции с кучей
С кучей нам будет необходимо делать две основные операции: извлекать максимальный элемент, а также добавлять новый элемент. Для извлечения максимального элемента (который находится по нулевому индексу) мы поставим на его место последний элемент. А для добавления — просто припишем его в конец. Но после этого куча станет немного "испорченной". В обоих случаях есть не больше одного «неправильного» элемента. В первом случае это A , а во втором – A . В первом случае его значение слишком мало для занимаемого им места, а во втором – слишком велико. В первом случае «неправильный» элемент нужно спустить вниз, а во втором – поднять вверх. Некоторым другим элементам при этом, естественно, тоже придётся подвинуться, но нам будет удобно следить, в первую очередь, именно за перемещением «неправильного» элемента.
Соответственно, нам понадобятся две процедуры для «починки» кучи, которые назовём sift_down (просеивание вниз) и sift_up (просеивание вверх). Каждую из них будем реализовывать для более общего случая, чем вроде бы требуется. А именно, будем считать, что «неправильным» может оказаться любой элемент кучи, а не только первый или последний (зачем это нужно, станет ясно из дальнейшего). Однако по-прежнему будем требовать, чтобы такой элемент был только один.
04: Просеивание вверх
Реализуйте функцию sift_up , выполняющую просеивание вверх элемента кучи, который оказался больше положенного.
В первой сточке задан размер кучи N (натуральное число от 1 до 10 5).
Во второй строке вводится сама куча – N различных целых чисел.
Гарантируется, что эти числа составляют корректную максимальную кучу).
В третьей строке вводится число M – количество запросов.
В следующих M строках вводятся сами запросы – по одному в строке.
Запрос задаётся двумя целыми числами i и x .
Требуется увеличить значение i -го элемента кучи на x и выполнить sift_up для восстановления кучи.
В качестве ответа на запрос требуется вывести
одно число: сообщить, на каком месте массива оказался изменённый элемент
после выполнения sift_up . (Вывести в отдельной строке одно число – соответствующий индекс).
Кроме того, после выполнения всех запросов требуется вывести кучу в её
конечном состоянии.
Лучше после:)
Это точно трудности?
Проще всего алгоритм описать так. Если A[i] является корнем дерева или не превосходит своего родителя, то ничего делать не надо. В противном случае надо поменять местами его с родителем, после чего снова получим «немного испорченную кучу», но теперь элемент, который, возможно, имеет большее значение, чем требуется на его месте, находится по индексу (i-1)//2 . Соответственно надо выполнить sift_up для этого элемента.
Однако при реализации полезно сделать два усовершенствования. Во-первых, нетрудно избавиться от рекурсии. Во-вторых, нет необходимости на каждом шаге просеивания действительно копировать просеиваемый элемент на место его родителя – его можно записать лишь в самом конце просеивания на его окончательное место.
Полезно заметить сходство этого алгоритма с вставкой очередного элемента в подходящее место отсортированной части массива, которая происходит при простой сортировке вставками.
Для оценки времени работы заметим, что число шагов просеивания не превышает высоты кучи, а время выполнения каждого шага ограничено константой.
Вывод кучи
Для вывода кучи в виде дерева можно использовать следующую функцию: def print_heap(ar): ml = max(len(str(x)) for x in ar) ars = [("{:0"+str(ml)+"}").format(x) for x in ar] dp = len(bin(len(ar))) - 1 print("*" * 2**(dp-2) * (ml + 1)) for i in range(1, dp + 1): str_space = " " * max(0, 2**(dp-i-2) * (ml + 1) - 1 - ml // 2) sep_space = " " * max(0, 2**(dp-i-1) * (ml + 1) - ml) print(str_space + sep_space.join(ars)) print("*" * 2**(dp-2) * (ml + 1)) print_heap(list(range(8)))05: Просеивание вниз
Реализуйте функцию sift_down , выполняющую просеивание вниз элемента кучи, который оказался меньше положенного.
Входные данные даются в формате из предыдущей задачи.
Запрос задаётся двумя целыми числами i и x .
Требуется уменьшить значение i -го элемента кучи на x и выполнить sift_down для восстановления кучи.
В качестве ответа на запрос требуется вывести
одно число: сообщить, на каком месте массива оказался изменённый элемент
после выполнения sift_down . (Вывести в отдельной строке одно число – соответствующий индекс).
Кроме того, после выполнения всех запросов требуется вывести кучу в её
конечном состоянии.
Лучше после:)
Это точно трудности?
Проще всего алгоритм описать так. Если у A[i] нет сыновей в дереве или если они не превосходят его по величине, то ничего делать не надо. В противном случае надо поменять местами его с максимальным из сыновей. (Если эти сыновья равны, то, вообще говоря, менять можно с любым из них. Но чтобы все последующие задачи были приняты тестирующей системой, надо менять непременно с левым). После чего снова получим «немого испорченную кучу», но теперь элемент, который, возможно, имеет меньше значение, чем требуется, находится на новом месте. Соответственно надо выполнить sift_down для этого элемента. При реализации можно избавиться от рекурсии. Оценка времени работы такая же, как для sift_up . Типичная ошибка – неправильная обработка ситуации, когда имеется только левый сын.
06: Извлечение максимального
Реализуйте функцию extract_max , извлекающую из кучи максимальный элемент и восстанавливающую её структуру. (см. раздел "Операции с кучей" выше)
На вход даётся куча в формате из предыдущей задачи.
Требуется вывести N -1 строку, в каждой – два числа.
Первое – индекс конечного положения последнего элемента кучи после перестановки его на нулевое место и просеивания; второе – значение извлечённого элемента (который раньше был на нулевом месте).
| Ввод | Вывод | |
|---|---|---|
| 6 12 6 8 3 4 7 | 2 12 2 8 1 7 0 6 0 4 | 12 8 7 6 4 3 / \ / \ / \ / \ / 6 8 6 7 6 4 3 4 3 / \ / / \ / 3 4 7 3 4 3 |
Просеивание и равенство элементов
В следующих задачах в куче могут встречаться равные элементы. Это создаёт некоторый произвол при выполнении процедур sift_up и sift_down. Для однозначности ответа его придётся ограничить. Поэтому введём два правила:1) Процедуры просеивания не должны перемещать элемент дальше, чем это действительно необходимо. Например, если A[i]=A , то вызов sift_up(2*i+1) не должен менять местами эти два элемента (хотя их обмен и не испортит кучу, он бесполезен).
2) Если при просеивании вниз можно перемещать рассматриваемый элемент как влево вниз, так и вправо вниз (это бывает, когда он меньше двух равных дочерних), то следует выбирать направление влево.
Второе правило довольно произвольно и введено лишь для обеспечения однозначности ответа. Первому правилу, напротив, должна удовлетворять любая разумная реализация кучи.
07: Приоритетная очередь
Требуется реализовать с помощью кучи приоритетную очередь, поддерживающую две операции: добавить элемент heappush и извлечь максимальный элемент heappop .
В первой строке вводятся два числа – максимальный размер приоритетной
очереди N и количество запросов M . (1 ≤ M , N ≤ 10 5).
Далее идут M строк, в каждой строке – по одному запросу.
Первое число в запросе задаёт его тип, остальные числа (если есть) – параметры запроса.
Тип 1 – извлечь максимальный (без параметров),
Тип 2 – добавить данный элемент в очередь.
В ответ на запрос типа 1 следует вывести:
Если извлекать было нечего (очередь пуста), то -1.
Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного положения элемента после его просеивания (если же удалён был
последний элемент и просеивать осталось нечего, вывести -1); второе –
значение извлечённого элемента.
В ответ на запрос типа 2 следует вывести:
Если добавить нельзя (нет места, поскольку в очереди уже N элементов), то вывести -1. (При этом куча не должна измениться).
Иначе – индекс добавленного элемента.
Кроме того, после выполнения всех запросов требуется вывести кучу в её
конечном состоянии.
| Ввод | Вывод | Куча в виде дерева в процессе |
|---|---|---|
| 4 7 1 2 9 2 4 2 9 2 9 2 7 1 | -1 0 1 2 1 -1 1 9 9 4 9 | 9 9 9 9 9 9 / / \ / \ / \ / \ 4 4 9 9 9 9 9 4 9 / / 4 4 |
08: Приоритетная очередь с удалением
Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса – запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа 3 с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.
В ответ на запрос типа 3 следует вывести:
-1, если элемента с таким индексом нет и удаление невозможно. (При
этом куча не должна измениться).
Иначе – значение удаленного элемента.
| Ввод | Вывод | Куча в виде дерева в процессе |
|---|---|---|
| 4 10 1 2 9 2 4 2 9 2 9 2 7 1 3 3 2 1 3 2 | -1 0 1 2 1 -1 1 9 -1 3 9 9 4 1 | 9 9 9 9 9 9 9 9 / / \ / \ / \ / \ / \ / \ 4 4 9 9 9 9 9 4 9 4 9 4 1 / / / 4 4 1 |
Построение кучи из массива
Напомним, что первый этап сортировки с помощью кучи состоит в преобразовании всего массива в кучу. Не исключено, что эта же операция может оказаться полезной и для начального построения приоритетной очереди, если требуется сразу поместить в очередь много элементов: вместо многократного повторения операции heappush можно записать все эти элементы в начальный участок массива и преобразовать его в кучу. Вопрос в том, можно ли это преобразование выполнить быстрее, чем выполняется простое многократное повторение heappush ?
До сих пор все операции с кучей были основаны на двух базовых – просеивании вверх (sift_up) и просеивании вниз (sift_down). Давайте попробуем с помощью каждой из них написать и процедуру heapify . Построение кучи просеиванием вверх (Build_Heap1) Дан массив. Требуется преобразовать его в кучу с помощью процедуры просеивания вверх. Формат входных данных. В первой строке вводится длина массива N. В следующей строке идут элементы массива – N целых чисел. Формат выходных данных. N целых чисел – элементы кучи по порядку.
09: Построение кучи просеиванием вверх
Реализуйте функцию heapify1 , формирующую кучу с помощью процедуры просеивания вверх.
Преобразуйте массив в кучу и выведите её элементы по порядку.
Лучше после:)
Это точно трудности?
Можно считать, что с самого начала имеется «немного испорченная куча» размером s = 2 , в которой последний элемент, возможно, имеет большее значение, чем требуется для занимаемого им места. Исправив её вызовом sift_up(1) , получим «немного испорченную кучу» размером s = 3 , которая, в свою очередь, тоже может быть исправлена вызовом sift_up(2) . И так далее. Заметим, что это, по существу, ничем не отличается от последовательного добавления элементов A, A, … A по одному в приоритетную очередь.
10: Построение кучи просеиванием вниз
Реализуйте функцию heapify2 , формирующую кучу с помощью процедуры просеивания вниз.
В первой строке вводится длина массива N . В следующей строке идут элементы массива – N целых чисел.
Преобразуйте массив в кучу и выведите их по порядку.
| Ввод | Вывод |
|---|---|
| 6 1 2 3 4 5 6 | 6 5 3 4 2 1 |
Лучше после:)
Это точно трудности?
Основная идея состоит в следующем. Мы можем сразу вызвать sift_down для любой вершины, чьи сыновья являются листьями. Вызвав её для всех таких вершин, получим поддеревья высоты 2, в каждом из которых выполняется основное свойство кучи. И так далее – новые вызовы sift_down будут обеспечивать выполнение основного свойства кучи в поддеревьях всё большего и большего размера. Реализовать это проще всего с помощью цикла for, который вызывает sift_down для всех элементов массива, кроме листьев дерева, справа налево.
Что быстрее?
Какая из этих реализаций heapify работает быстрее? Почему? (Качественно это можно понять, даже если ваши знания математики не позволяют количественно оценить разницу в их времени работы).(Для хорошо знающих математику) Довольно очевидно, что
каждая из реализаций heapify работает не дольше, чем за O(n
log n)
, поскольку выполняется O(n)
вызовов, каждый из которых работает за O(h)
.
Однако не исключено, что если посчитать точнее, то можно найти лучшую
оценку времени – ведь только последние вызовы происходят на куче размера, близкого к n
, а первые выполняются на куче меньшего размера и, соответственно, занимают меньше времени.
Чтобы это выяснить, надо для каждой реализации сделать одно из двух:
Доказать, что, по крайней мере в некоторых случаях, время работы действительно имеет порядок n
log n
(Это принято записывать O(n
log n)
).
Найти и доказать более точную оценку времени, которая меньше, чем O(n
log n)
.
Лучше после:)
Это точно трудности?
В первой реализации (на основе sift_up) выполняется много просеиваний на большую глубину, и мало просеиваний на маленькую глубину. Во второй реализации, наоборот, просеиваний на большую глубину выполняется мало, а на маленькую – много. Поэтому разумно предположить (и можно доказать), что вторая реализация работает быстрее.
Можно доказать (см. например, книгу Кормена и др.), что вторая реализация (на основе sift_down) всегда работает за время O(n) , а первая в худшем случае – за O(n log n) .
11: Сортировка кучей - подробно
Требуется отсортировать по неубыванию с помощью изученного алгоритма целочисленный массив размера N, выводя также некоторые промежуточные
результаты работы. А именно, должны быть выведены:
первоначальная куча, построенная вызовом heapify2 ;
куча после удаления каждого элемента (то есть после каждой итерации
внешнего цикла);
отсортированный массив.
Пакет heapq
Конечно же, столь важная вещь, как работа с кучей, реализована в стандартной библиотеке питона. Во всех задачах ниже можно (и даже желательно) использовать эту библиотеку. Ознакомиться с ним можно на странице с документацией . Хорошего русскоязычного текста я не нашёл, поделитесь ссылкой, если вдруг найдёте:)От сортировки пузырьком к быстрой сортировке Хоара и поиску медианы
Итак, теперь будем оптимизировать сортировку пузырьком. То, что получится в результате, называется быстрой сортировкой или сортировкой Хоара (quicksort ). Мы реализуем лишь самую "наивную" версию этого алгоритма.В сортировке пузырьком мы переставляем элемент только на соседнюю позицию, "всплывая" его, насколько это возможно. При этом после "всплытия" мы ещё много раз будем выполнять сравнения с этим элементом. В быстрой сортировке мы берём элемент и максимально быстро "топим" элементы, меньшие его, и "всплываем" элементы, большие. Тем самым элемент оказывается на необходимой для него в отсортированном массиве позиции. После этого рекурсивно сортируем всё меньшее и отдельно большее, необходимости сравнивать с данным элементом при этом уже никогда не будет.
Точнее, основа алгоритма — рекурсивная функция, принимающая на вход список, а также позиции от и до которой необходимо отсортировать список. При сортировке всего списка используются значения по умолчанию — сортировать от начала и до конца.
Def quicksort(A, begin=0, end=-1): pass Содержимое функции достаточно просто: сначала выбираем опорный элемент — либо самый первый элемент в списке, либо (лучше) случайный. Далее за один проход по списку переупорядочиваем нашу часть массива так, чтобы сначала шли элементы, строго меньшие опорного, затем больше или равные опорному. При этом сохраняем индекс какого-нибудь опорного элемента. После разделения останется переставить этот опорный элемент так, чтобы до него были только строго меньшие элементы, а после него — больше либо равные. Далее рекурсивно сортируем то, что слева от него, и то, что справа.
Этот алгоритм обладает достаточно забавным свойством: если мы каждый раз будем выпирать опорный элемент очень неудачно (например строго минимальным или максимальным), то время его работы будет порядка n+(n-1)+...+1 , то есть O(n 2) . Однако обычно такого не происходит, и данный алгоритм часто оказывается быстрее некоторых других, гарантирующих работу за n log n .
Процедура разделения массива оказывается полезной ещё и для нахождения медианы (элемента, который в отсортированном массиве стоит посередине), и более обще: k -й порядковой статистики (элемента, который в отсортированном массиве идёт k -ым). Если наш массив имеет длину n , то статистики с номерами 0.05n , 0.25n , 0.5n , 0.75n и 0.95n могут многое рассказать о распределении чисел в массиве. Например, если взять зарплаты в России в 2007 году, то эти статистики получатся примерно такими: 2000, 5000, 9000, 15000, 35000. Заметим, что при таком распределении средняя заработная плата может быть сколь угодно велика (в 2007 она была примерно 15000). Хотя 75% населения получали зарплату не большую 15000р, и более половины населения — вообще менее 10000р.
Идея поиска k -й порядковой статистики в следующем. Выберем случайный опорный элемент и переупорядочим массив так, чтобы сначала шли элементы, строго меньшие опорного, затем равные опорному, и наконец строго большие опорного. Заметим, что сделать такую разбивку чуть сложнее, чем более простую, необходимую для сортировки Хоара. Пусть элементов, строго меньших опорного S < , равных опорному — S = . Тогда сравнивая число k с S < и S < +S = легко понять, в какой части массива нужно искать ответ.
Этот алгоритм снова вероятностный, и если очень не повезёт, то он будет работать за время O(n 2) , что гораздо хуже, чем отсортировать массив и взять k -й элемент. Однако обычно он работает за время порядка O(n) , и именно поэтому оказывается очень полезен.
13: Разделение массива
Реализуйте процедуру разделения массива.
В первой строке даются числа N — длина массива, и x — опорный элемент. Во второй строке дана последовательность из N целых чисел, среди которых есть x .
Переупорядочьте массив так, чтобы сначала шли элементы, строго меньшие опорного x , затем элемент x , а после него элементы, больше либо равные опорному.
| Ввод | Вывод |
|---|---|
| 7 3 1 7 2 4 3 2 3 |
1 2 2 3 4 7 3 |
Подсказка
Я — овощ, и не хочу думать
Операция переупорядочивания массива:
Два индекса - l
и r
, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
Вычисляется индекс m
опорного элемента;
Индекс l
последовательно увеличивается до тех пор, пока l
-й элемент не окажется больше или равен опорному.
Индекс r
последовательно уменьшается до тех пор, пока r
-й элемент не окажется меньше опорного. Если при этом встречается элемент, равный опорному, то его индекс заносится в переменную m
;
Если l
r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l
и r
, которые были достигнуты (заметим, что если l
-й элемент был равен опорному, то после обмена r
-й элемент окажется равен опорному, после чего будет обновлён индекс m
)
Если r
= l
- найдена середина массива - операция разделения почти закончена.
Теперь в эту "середину" нужно поместить опорный элемент. Для этого нужно поменять местами опорный элемент с индексом m
, а также элемент с индексом l
или l+1
в зависимости от того, больше ли l
-ый элемент опорного.
14: Быстрая сортировка
Реализуйте быструю сортировку Хоара.
От сортировки вставками до сортировки слиянием
В алгоритме сортировки вставкой в каждый произвольный момент начальная часть списка уже отсортирована. Далее первый элемент из неотсортированной части добавляется в отсортированную часть списка. Таким образом, мы n раз подряд производим слияние двух отсортированных списков: одного длины 1, 2, и так далее до n-1 , и второго — каждый раз длины 1.
Однако же мы знаем, что два списка длин n и m можно слить вместе в один отсортированный список за время порядка n+m . Если мы сначала разобьём элементы на пары, которые сольём в списки длины 2, затем их сольём в списки длины 4, и так далее, то потратим как раз O(n log n) операций.
Проще всего описать это при помощи рекурсии. Если длина массива не превосходит 1, то он уже отсортирован. В противном случае отсортируем первую половину массива, отдельно отсортируем вторую половину, после чего сольём всё вместе.
16: Слияние двух отсортированных массивов
Реализуйте функцию для слияния двух отсортированных массивов.
В первой строке даются числа N и M — длины массивов. Во второй строке дана последовательность из N целых чисел, а в третьей — из M целых чисел. При этом каждая последовательность отсортирована по неубыванию.
Выведите объединение этих последовательностей, отсортированную по неубыванию.
Что делать, если данные не помещаются в оперативную память
Если данных очень много, то они не поместятся в оперативную память, и стандартные методы сортировки применить будет невозможно. Отличительной особенностью внешних носителей данных является скорость доступа. Скажем, время на получение информации из оперативной памяти в современном компьютере составляет порядка 50нс, а из жёсткого диска — порядка 5мс. Это в сто раз больше. Скорость последовательного чтения с жёсткого диска составляет примерно 200МБ/с, в то время как скорость чтения из оперативной памяти имеет порядок 20ГБ/с, снова в 100 раз быстрее. При непоследовательном доступе к жёсткому диску задержки увеличиваются, скорость сильно падает.
Сортировки данных, хранящихся на периферийных устройствах (например, жёстких дисках) и не вмещающихся в оперативную память, называются внешними . Для того, чтобы внешняя сортировка была быстрой, необходимо минимизировать количество доступов к периферийных устройствам, при этом максимально использовать только длительные последовательные доступы. Большинство способов внешних сортировок так или иначе связана с сортировкой слиянием.
Например, можно взять исходную последовательность и разбить на серии, которые помещаются в оперативную память. Каждую серию отсортировать стандартным образом и записать на жёсткий диск. После этого нужно будет производить слияния до тех пор, пока весь массив не будет отсортирован.
Предположим, что оперативная память вмещает P элементов, а нам нужно отсортировать P×2 k элементов. Тогда мы первый раз прочитаем и запишем каждый элемент при подготовке серий. В результате P×2 k чтений-записей получатся серии длины P . После первого слияния мы получим серии длины P×2 1 , затем P×2 2 и так далее. В результате потребуется (k+1) полных прочтений и записей данных на диск.
Для увеличения скорости необходимо уменьшить количество чтений-записей. И здесь можно двигаться в двух направлениях: увеличивать длину отсортированных серий, которые получаются при первом проходе, и уменьшать количество чтений-записей при последующих слияниях.
Существует красивая идея, которая позволяет после первого прохода получить отсортированные серии длиной не P , а в среднем 2P . Если же при этом данные будут частично отсортированы, то длины серий будут ещё больше. Об этой идее есть задача ниже.
Теперь представим себе, что мы можем выполнять эффективное слияние не 2-х массивов, а сразу 4-х. Тогда после первого слияния мы получим серии длиной сразу P×2 2 , а итоговое количество чтений-записей данных станет почти в два раза меньше!
А если сливать не 4-е массива, а сразу, скажем, 1024? Или даже 1048576 (если P >1048576)? Тогда чтений-записей будет почти в 10 раз меньше (или даже в 20)! Однако здесь есть некоторая проблема: если сливаемых массивов станет слишком много, и доступ к информации на диске станет по большей части случайным, а не последовательным. И время доступа увеличится. Раз в 10-100. И мы потеряем всё, чего добились. Лучше всего, если у нас будет несколько жёстких дисков, тогда мы сможем взаимодействовать с ними параллельно, и увеличить количество одновременно сливаемых серий без потери скорости.
18: Слияние нескольких упорядоченных массивов
Реализуйте функцию для слияния нескольких отсортированных массивов.
В первой строке даётся натуральное число N — количество массивов. В следующих N строках даны отсортированные по неубыванию массивы.
Выведите объединение этих последовательностей, отсортированную по неубыванию. При этом разрешается только однократный проход по каждому из массивов.
| Ввод | Вывод |
|---|---|
| 3 1 4 5 1 3 5 1 2 5 |
1 1 1 2 3 4 5 5 5 |
Подсказка
Я — овощ, и не хочу думать
Никто не видит, как я подглядываю...
Необходимо собрать кучу из N троек (начальный элемент i -го массива, i , 0). После этого нужно последовательно извлекать из кучи минимальную тройку. Первый элемент тройки — минимальный ещё не выведенный элемент, его нужно отправить на вывод. А второй элемент тройки — номер массива, из которого нужно взять элемент и назад добавить в кучу, а третий — индекс последнего взятого элемента из этого массива.
19: Формирование серий для внешней сортировки
В этой задаче мы представим себе, что у нас есть оперативной памяти на P чисел, и последовательность целых чисел, которую необходимо отсортировать. Её длина существенно больше P .
Необходимо создать список, в которым исходная последовательность разбита на серии неубывающих чисел, причём длина каждой серии не меньше P . В простейшем случае мы могли бы считывать по P чисел, сортировать их и записывать назад на диск (записать в стандартный вывод). Однако есть красивый алгоритм, позволяющий сразу создавать серии длиной в среднем 2P .
Считаем первые P чисел и сформируем из них минимальную кучу. Дальше извлекаем минимальный элемент из кучи и сразу же добавляем его в текущую серию. После этого считываем очередной элемент последовательности. Если он равен элементу, который мы только что вывели, то его тоже можно добавить в серию (вывести) и продолжить дальше. Если он больше текущего, то он может быть добавлен в серию в будущем. Для этого его нужно включить в кучу и продолжить работу. Однако если новый элемент меньше текущего, то его нельзя добавить в текущую серию. Тогда добавим его во вторую кучу. Размер первой кучи при этом уменьшится на 1, а размер второй — увеличится на 1, в сумме мы по-прежнему храним P элементов. Будет продолжаться до тех пор, пока все P элементов станут непригодными для добавления в текущую серию (и окажутся во второй куче, тогда как первая станет пустой). Это значит, что текущую серию нужно закончить, поменять кучи местами и начать новую серию.
Оказывается, что при таком подходе длина получающихся серий будет в среднем 2P , и уж точно не меньше P каждая. При этом если в исходных данных есть много отсортированных кусков, то длины серий будут гораздо больше, вплоть до ровно одной серии на полностью отсортированных данных!
В первой строке даны два числа P и N — количество элементов, помещающихся в оперативную память, и длина последовательности для сортировки соответственно. Во второй строке дана последовательность целых чисел длины N .
Выведите эту последовательность, упорядоченную в серии по описанному алгоритму. Кроме списка с последовательностью из условия, запрещается использовать списки суммарной длиной больше P .
Следующей строчкой выведите среднюю длину серий, округлённую до двух знаков после запятой.
| Ввод | Вывод |
|---|---|
| 4 21 31 12 50 14 8 59 9 43 91 93 32 81 67 52 41 52 63 67 77 74 65 | 12 14 31 50 59 91 93 8 9 32 43 52 52 63 67 67 74 77 81 41 65 7.0 |
20: Внешняя сортировка
Достаточно эффективная внешняя сортировка может быть реализована следующим образом: сначала мы формируем начальные серии (так как делали это в предыдущей задаче) и записываем их последовательно в N различных "файлов" (первую серию в первый файл, вторую — во второй и т.д.). После этого, мы начинаем сливать N -ки отсортированных серий вместе, получающиеся серии при этом записывать в другие N различных "файлов". После того, как все N -ки серий будут слиты, мы начинаем сливать N -ки серий второго порядка и записывать их в первые N файлов. Будем продолжать операцию до тех пор, пока весь массив не будет отсортирован.
В первой строке даны три числа P , N и L — количество элементов, помещающихся в оперативную память, количество пар файлов, которые должны использоваться при сортировке, и длина последовательности для сортировки соответственно. В качестве файлов можно использовать обычные списки.
Выполните внешнюю сортировку данных по описанному алгоритму.
Перепишите вашу программу так, чтобы использовались реальные файлы. При каком N достигается максимальная производительность сортировки на вашем компьютере?
| Ввод | Вывод |
|---|---|
| 4 2 21 31 12 50 14 8 59 9 43 91 93 32 81 67 52 41 52 63 67 77 74 65 | 8 9 12 14 31 32 41 43 50 52 52 59 63 65 67 67 74 77 81 91 93 |
Алгоритм Дейкстры с кучей
Пусть длины всех рёбер — натуральные числа. Тогда задачу поиска кратчайшего пути можно свести к случаю рёбер длины 1, расставив на всех дорогах «верстовые столбы» и объявив их новыми вершинами (соответственно разбиваются и рёбра). Старые вершины и расстояния междуними останутся без изменений, так что можно найти эти расстояния, запустив поиск в ширину на новом графе. Очевидный недостаток такого решения состоит в том, что при длинных рёбрах нужно много вспомогательных вершин, и алгоритм будет тратить много времени, двигаясь от одного столба до другого.
Для примера рассмотрим граф G и граф G" с добавленными вершинами, показанные на рисунке выше. Запустим из S поиск в ширину (со скоростью ребро за минуту). Тогда первые 99 минут он будет двигаться вдоль S –A и S –B от столба к столбу. На это и смотреть скучно, так что мы лучше поспим до того момента, когда произойдёт что- то интересное (мы дойдём до настоящей вершины). Поставим два будильника: один на время 100 для вершины A , второй–– на 200 для B. Первый сработает раньше: поиск дойдёт сначала до вершины A. Из A начнётся новое движение, которое дойдёт до B в момент 150 (раньше, чем движение из S ).
Опишем ситуацию в общем виде: поиск в ширину продвигается по рёбрам графа G
, и для каждой вершины установлен будильник на ожидаемое
время прибытия уже запущенного движения. (Реально поиск может прийти
туда и раньше, пройдя через другую вершину, как это было в примере.) Главное: пока не сработает хотя бы один будильник, ничего интересного не будет (движение будет продолжаться по рёбрам). Звонок будильника означает,
что поиск в ширину добрался до некоторой вершины исходного графа u
∈ V.
В этот момент начинаются движения по рёбрам, исходящим из u
, и это надо учесть в их концевых вершинах и перезавести будильники на концах этих
рёбер (если новое время прибытия раньше прежнего). Вот схема алгоритма:
- Завести будильник для s
на время 0.
- Пока есть заведённые, но не сработавшие будильники:
--- Взять самый ранний из них (пусть он в вершине u
на момент T
).
--- Констатировать, что расстояние от s
до u
равно T.
--- Для каждой вершины v
, смежной с u
в G
:
если для вершины v
будильник ещё не заведён, завести его на время
T + l
(u
, v
);
если будильник заведён на время, большее чем T + l
(u
, v
), то переставить его на это меньшее время (а иначе оставить как было).
Алгоритм с будильниками находит кратчайшие пути в графах с положительными целыми весами. Он практически готов к использованию, осталось только как-нибудь реализовать механизм будильников. Подходящая для этих целей структура данных называется очередью с приоритетами; обычно её реализуют с помощью кучи.
21: Длина кратчайшего пути (Алгоритм Дейкстры)
Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.
Входные данные . Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1≤N≤100000 , 0≤K≤300000 ), где K – количество дорог. Каждая из следующих K строк содержит описание дороги с двусторонним движением – три целых числа a i , b i и l i (1≤a i ,b i ≤N , 1≤l i ≤10 6 ). Это означает, что имеется дорога длины l i , которая ведет из города a i в город b i . В последней строке находятся два числа А и В – номера городов, между которыми надо посчитать кратчайшее расстояние (1≤A,B≤N ).
Выходные данные . Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города А 1 до N . Задача менеджера - обрабатывать запросы приложений на выделение и освобождение памяти.
Запрос на выделение памяти имеет один параметр K . Такой запрос означает, что приложение просит выделить ему K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.
Запрос на освобождение памяти имеет один параметр T . Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T . Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T - запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.
Требуется написать менеджер памяти, удовлетворяющий приведенным критериям. Входные данные
В первой строке входных данных задаются числа N и M 1 ≤ N ≤ 2 31 – 1 ; 1 ≤ M ≤ 10 5 ). Каждая из следующих M i+1 )- я строка входных данных (1 ≤ i ≤ M K , если i- K (1 ≤ K ≤ N ), либо отрицательное число –T , если i- T (1 ≤ T). Выходные данные
Для каждого запроса на выделение памяти выведите результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число –1 . Результаты нужно выводить в порядке следования запросов во входных данных
Входные данные В первой строке входных данных задаются числа N и M - количество ячеек памяти и количество запросов, соответственно (1 ≤ N ≤ 2 31 – 1 ; 1 ≤ M ≤ 10 5 ). Каждая из следующих M строк содержит по одному числу: (i+1 )- я строка входных данных (1 ≤ i ≤ M ) содержит либо положительное число K , если i- й запрос - запрос на выделение с параметром K (1 ≤ K ≤ N ), либо отрицательное число –T , если i- й запрос - запрос на освобождение с параметром T (1 ≤ T).
Выходные данные Для каждого запроса на выделение памяти выведите результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число –1. Результаты нужно выводить в порядке следования запросов во входных данных
| Ввод | Вывод |
|---|---|
| 42 9 7 3 8 -2 6 5 -5 9 4 | 1 8 11 19 25 30 19 |
24: Тупики
На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).
Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал - конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.
Тупики пронумерованы числами от 1 до K . Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого- то тупика отправилась в момент времени X , то электричку, которая прибывает в момент времени X , в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 - можно.
Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.
Входные данные Сначала вводятся число K - количество тупиков и число N - количество электропоездов (1≤K≤100000 , 1≤N≤100000 ). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 10 9 . Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая- нибудь электричка (или даже несколько) отправляются в момент прибытия какой- нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.
Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.
Выходные данные Выведите N чисел - по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.
| Ввод | Вывод |
|---|---|
| 1 1 2 5 | 1 |
| 1 2 2 5 5 6 | 0 2 |
| 2 3 1 3 2 6 4 5 | 1 2 1 |
25: Коммерческий калькулятор
Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5 % от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10 , 11 , 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.
Входные данные Первая строка входных данных содержит число N (2 ≤ N ≤ 10 5 ). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.
Выходные данные Определите, сколько денег нам потребуется на нахождения суммы этих N чисел. Результат должен быть выведен с двумя знаками после десятичной точки.
| Ввод | Вывод |
|---|---|
| 4 10 11 12 13 | 4.60 |
| 2 1 1 | 0.10 |
26: Поиск максимума в скользящем окне за O(n)
На вход даётся ширина окна — натуральное число, и последовательность целых чисел.
Необходимо вывести максимальное число на каждом отрезке длиной в ширину окна.
В первой строке даны два числа W и N — шинира окна и длина последовательности. Во второй строчке даны N целых чисел. Гарантируется, что N не меньше W .
Окно скользит по последовательности с шагом 1. На каждом шаге надо найти максимальный элемент попавший в окно.
Наивное решение этой задачи имеет асимптотику O(NW) . У этой задачи существует решение за O(N) , однако решение за время O(N log W) тоже пойдёт.
| Ввод | Вывод |
|---|---|
| 3 8 1 2 3 4 5 4 3 2 | 3 4 5 5 5 4 |
Рандомизированная куча (randomized heap) — это куча, которая за счёт применения генератора случайных чисел позволяет выполнять все необходимые операции за логарифмическое ожидаемое время.
Кучей называется бинарное дерево, для любой вершины которого справедливо, что значение в этой вершине меньше либо равно значений во всех её потомках (это куча для минимума; разумеется, симметрично можно определить кучу для максимума). Таким образом, в корне кучи всегда находится минимум.
Стандартный набор операций, определяемый для куч, следующий:
- Добавление элемента
- Нахождение минимума
- Извлечение минимума (удаление его из дерева и возврат его значения)
- Слияние двух куч (возвращается куча, содержащая элементы обеих куч; дубликаты не удаляются)
- Удаление произвольного элемента (при известной позиции в дереве)
Рандомизированная куча позволяет выполнять все эти операции за ожидаемое время при очень простой реализации.
Структура данных
Сразу опишем структуру данных, описывающую бинарную кучу:
struct tree { T value; tree * l, * r; } ; В вершине дерева хранится значение некоторого типа , для которого определён оператор сравнения (). Кроме того, хранятся указатели на левого и правого сыновей (которые равны 0, если соответствующий сын отсутствует).Выполнение операций
Нетрудно понять, что все операции над кучей сводятся к одной операции: слиянию двух куч в одну. Действительно, добавление элемента в кучу равносильно слиянию этой кучи с кучей, состоящей из единственного добавляемого элемента. Нахождение минимума вообще не требует никаких действий — минимумом просто является корень кучи. Извлечение минимума эквивалентно тому, что куча заменяется результатом слияния левого и правого поддерева корня. Наконец, удаление произвольного элемента аналогично удалению минимума: всё поддерево с корнем в этой вершине заменяется результатом слияния двух поддеревьев-сыновей этой вершины.
Итак, нам фактически надо реализовать только операцию слияния двух куч, все остальные операции тривиально сводятся к этой операции.
Пусть даны две кучи и , требуется вернуть их объединение. Понятно, что в корне каждой из этих куч находятся их минимумы, поэтому в корне результирующей кучи будет находиться минимум из этих двух значений. Итак, мы сравниваем, в корне какой из куч находится меньшее значение, его помещаем в корень результата, а теперь мы должны объединить сыновей выбранной вершины с оставшейся кучей. Если мы по какому-то признаку выберем одного из двух сыновей, то тогда нам надо будет просто объединить поддерево в корне с этим сыном с кучей. Таким образом, мы снова пришли к операции слияния. Рано или поздно этот процесс остановится (на это понадобится, понятно, не более чем сумма высот куч).
Таким образом, чтобы достичь логарифмической асимптотики в среднем, нам надо указать способ выбора одного из двух сыновей с тем, чтобы в среднем длина проходимого пути получалась бы порядка логарифма от количества элементов в куче. Нетрудно догадаться, что производить этот выбор мы будем случайно , таким образом, реализация операции слияния получается такой:
Tree * merge (tree * t1, tree * t2) { if (! t1 || ! t2) return t1 ? t1 : t2; if (t2- > value < t1- > value) swap (t1, t2) ; if (rand () & 1 ) swap (t1- > l, t1- > r) ; t1- > l = merge (t1- > l, t2) ; return t1; }
Здесь сначала проверяется, если хотя бы одна из куч пуста, то никаких действий по слиянию производить не надо. Иначе, мы делаем, чтобы куча была кучей с меньшим значением в корне (для чего обмениваем и , если надо). Наконец, мы считаем, что вторую кучу будем сливать с левым сыном корня кучи , поэтому мы случайным образом обмениваем левого и правого сыновей, а затем выполняем слияние левого сына и второй кучи.
Асимптотика
Введём случайную величину , обозначающую длину случайного пути от корня до листа (длина в числе рёбер). Понятно, что алгоритм выполняется за операций. Поэтому для исследования асимптотики алгоритма надо исследовать случайную величину .
Математическое ожидание
Утверждается, что математическое ожидание оценивается сверху логарифмом от числа вершин в этой куче:
Доказывается это легко по индукции. Пусть и — соответственно левое и правое поддеревья корня кучи , а и — количества вершин в них (понятно, что ).
Тогда справедливо.
куча
ж. груда, вброх, громада, вещи горой;
толпа, сборище; *много;
новг. твер. копна сена.
Моск. количество скота, выгоняемого от одного хозяина в стадо. Саженные кучи щебня. Куча людей, народа. На мне куча забот. Муравьиная куча. муравейник. Комком да в кучку, на скорую (на крестьянскую ручку.) Велика куча (денег) не надокучит. Была кучка, стал ворошек, прикопили. На чужую кучу нечего глаза пучить. Комком да в кучку, да под леву ручку. Смотрит в кучку, а глядит врознь! Народ глуп: все в кучу лезет. По кучке, все онучки; а станешь считать, одной нет! Галичане в кучу, костромичи в кучу, ярославцы прочь, или врознь: от междоусобии Шемяки с Шуйским.
Сиб. заводе, количество уголья, выходящего в один раз из печи. Класть кучи, жечь угодье.
Сиб. последняя пора беременности. Даль вам Бог кого? Нет, еще жена в куча. Кучки мн. умалит. ниж. созвездие плеяд, утиное гнездо, бабы, стожары.
Южн. зап. еврейский праздник пасхи (см. куща). Кучный, кучевой, кучечный, к кучкам относящ. Кучный заряд портит дичь. Народ кучно стоит, густо, толпою. Кучевые облака. Кучистый, кучковатый, состоящий из куч, усеянный кучками. Кученок м. небольшая угольная куча, в которой недоспевший при первом пережиге уголь (головни) дожигается. Кучегур м. кучегуры мн. южн. песчаные бугры, сыпучие кочки, шиханы, бараканы. Кучеклад спб. угольщик. Кучить что, кучивать, сбирать, складывать, сгребать в кучи, вороха.
Кучить чем, новг. торговать по мелочи, кучить калачами, квасом.
Кучить картофель, огребать, окучивать. -ся, быть скучиваему, складываему в кучи; толпиться в кучу.
Моржи кучатся арх. вылезают юровом (стаей) на лед и сходятся.
Кому, о чем, сев. вост. просить неотступно, униженно, кланяться, умолять, конаться, домогаться, докучать (докука). Пучился, мучился, а докучился, так кинул. Кучился, мучился, а упросил, так бросил. Мучится, а никому не кучится. Вскучил волосы. Вкучился, влез в кучу. Крот выкучил землю. Докучивай картофель. Накучили много. Окучивай его. Подкучивай сбоку. Стрелки скучились. Покучься соседу. Вскучишься, как беда придет. Насилу рубля докучился. Закучился, закланялся. Накучился, накланялся. Кученье ср. действ. по глаг. на ть и на ся. Кучка ж. об. действ. по глаг. кучить и
умалит. куча. Строить кучки, у стрелков, сбегаться из рассыпного строя в кучки, при налете конницы. Кучкать что, комкать, складывать или свертывать, сминать в кучу. Кучкаться казач. толпиться, сбиваться в кучу, куриться, усаживаться тесно. Кучкаться или тул. кучать, медлить, мешкать, копаться. Что там кучаешь?
Толковый словарь русского языка. Д.Н. Ушаков
куча
Большое количество чего-н., наваленное в одном месте горкой. Куча песку. Навозну кучу разрывая, петух нашел жемчужное зерно. Крылов. Царь однажды воинам своим велел снести земли по горсти в кучу. Пушкин. Куча листьев.
Беспорядочное нагромождение, груда разных предметов. В углу была свалена в кучу всякая рухлядь. Из горевшего дома выносили пожитки и клали в одну кучу.
перен. Большое количество, много (разг. фам.). У них куча детей. Получить целую кучу неприятностей. Народу собралось - куча! Валить всё в одну кучу (разг.) - перен. без разбора, огульно, смешивать в одно различные явления. Куча мала! - восклицание, употр. в детской игре, когда устраивается общая свалка.
Толковый словарь русского языка. С.И.Ожегов, Н.Ю.Шведова.
куча
Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.
чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей. * Куча мала! - возглас в детской игре, по к-рому начинается общая свалка.
уменьш. кучка, -и, ж. (к 1 знач.).
Новый толково-словообразовательный словарь русского языка, Т. Ф. Ефремова.
куча
Что-л., сваленное горкой, грудой.
разг. Большое количество, скопление чего-л.
разг. Толпа, скопление (людей, животных).
разг. Большое количество, множество.
Куча (память)
Ку́ча в информатике и программировании - название структуры данных, с помощью которой реализована динамически распределяемая память приложения.
Размер кучи - размер памяти, выделенной операционной системой для хранения кучи.
Куча
Ку́ча - нагромождение большого количества объектов, по форме обычно похожее на конус . В переносном смысле - большое количество чего-либо. См. Парадокс кучи.
Куча (город)
Куча - оазис в округе Аксу Синьцзян-Уйгурского автономного района КНР, административный центр уезда Куча. Население - 70.305 чел. (2007). Расположен на высоте 1057 м над уровнем моря, у подножия Тянь-шаня.
Куча (структура данных)
ку́ча - это специализированная структура данных типа дерево , которая удовлетворяет свойству кучи: если B является узлом-потомком узла A , то ключ(A ) ≥ ключ(B ). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами ). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух. Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом. Кучи имеют решающее значение в некоторых эффективных алгоритмах на графах, таких, как алгоритм Дейкстры на d-кучах и сортировка методом пирамиды.
Структуру данных куча не следует путать с понятием куча в динамическом распределении памяти. Впервые термин использовался именно для структур данных. В некоторых ранних популярных языках программирования типа ЛИСП обеспечивалось динамическое распределение памяти с использованием структуры данных «куча», которая и дала своё имя выделяемому объёму памяти..
Кучи обычно реализуются в виде массивов, что исключает наличие указателей между её элементами.
Над кучами обычно проводятся следующие операции:
- найти максимум или найти минимум : найти максимальный элемент в max-куче или минимальный элемент в min-куче, соответственно
- удалить максимум или удалить минимум : удалить корневой узел в max- или min-куче, соответственно
- увеличить ключ или уменьшить ключ : обновить ключ в max- или min-куче, соответственно
- добавить : добавление нового ключа в кучу.
- слияние : соединение двух куч с целью создания новой кучи, содержащей все элементы обеих исходных.
Куча (село)
Ку́ча - село в Новоушицком районе Хмельницкой области Украины.
Население по переписи 2001 года составляло 1446 человек. Почтовый индекс - 32645. Телефонный код - 3847. Занимает площадь 5,828 км². Код КОАТУУ - 6823385001.
Куча (государство)
Куча (также Кучэ и Кучар ) - древнее буддийское государство, протягивавшееся вдоль северной кромки пустыни Такла-Макан по северному маршруту Великого шёлкового пути между Карашаром к востоку и Аксу к западу.
Конец существованию этого политического образования положило расширение Танской империи на запад в VII веке. Результатом стала ассимиляция индоевропейцев тюркоязычными соседями. О современном городе см. Куча.
Куча (река)
Куча - река в России, протекает в Юсьвинском районе Пермского края. Устье реки находится в 54 км по правому берегу реки Иньва. Длина реки составляет 12 км.
Исток реки на Верхнекамской возвышенности близ границы с Ильинским районом. Исток расположен в урочище Верхняя Куча в 8 км к юго-западу от села Крохалево. Река течёт на север, в среднем течении протекает деревню Алямово. Впадает в Иньву ниже села Аксеново.
Примеры употребления слова куча в литературе.
Гольдберг виду не подает, что проведал, какие чудеса творятся с его лошадью, но, как подозревает Абрамович, он наверняка многое знает, только умело скрывает, и, очнувшись на куче навоза и грязной соломы от своих опасных видений, лошадь прислушивается к сонному бормотанию глухонемого хозяина.
Гольдберг, дремавший на куче опилок, пока Абрамович исполнял свою сольную партию, проснулся как раз вовремя, чтобы раскланяться вместе с ним.
Еще один аварийщик, вооружившись совком и неторопливо орудуя веником, сметал в кучу рассыпанные по полу осколки хрустальной гадюки.
После стольких суток ожиданий и матерков мы в военно-транспортном ИЛ-72МД вместе с кучей барахла, автокраном и УАЗиком.
Из этих небольших примеров видно, что сотрудники государственной полиции в Праге валили в одну кучу социал-демократов и националистов, бомбы, баллоны, рецепты и рескрипты, правящего монарха и изобретателя Эдисона, анархистов и аграрников и т.
Ее агротехнические методы год от года совершенствовались, количество мешков с лусавендрой, отправляемых на рынок в Мазадону, неуклонно возрастало, все выше становились кучи блестящих рисовых зерен в ее закромах.
Пиздвилльской долины говорят ты отплываешь на неспешном корабле в Китай строго из-за кучи денег и азотистой кинопехоты.
Когда отец Дадуса закончил сортировать рыбу, у него получилось три кучи : большая рыба предназначалась для продажи на рынке, немного оставили себе на жареху, а всевозможную мелочь Дадус и Айван должны были раздать толпившейся вокруг детворе.
Девица, лица которой за кучей съестных припасов я рассмотреть не мог, хотя ее запах и показался мне странно знакомым, не дойдя пару ступенек до старцев, уже жадно протянувших руки к еде, аккуратненько поставила ногу точно в пустоту, мимо верхней ступени.
При Лаврентии Павловиче тоже придерживались такой системы - если ты прячешь куда-то алмазик, то лучше в кучу стекол такого же размера.
Единственный намек на беспорядок виднелся на небольшой площадке перед Первым Аляскинским банком ПАП, где на козлах среди кучи инструментов и пивных бутылок лежали две недоделанные фигуры из пенополистирола.
Нет, он только будет выкрикивать бессмысленное слово и под его защитою станет сваливать в одну кучу все разнообразие аспирации человеческой мысли.
И действительно, начал Бадмаев с рассказов о своих успехах в лечении, назвал кучу пациентов с громкими именами, а затем потихонечку сполз к большой политике.
Помимо них, - проворчал Бадья, - вокруг отирается еще куча всякого дерьма.
Тогда Барбуда дождался, пока придет его очередь убирать Веселый Домик, епархию кума, выбрал момент, когда тот отвлекся, и навалил ему кучу в верхний ящик стола.
