Рандомизированная куча. Смотреть что такое "куча" в других словарях Куча в программировании

Введение

После всего изученного нами остался небольшой неизученный "должок" — "быстрые" сортировки. Мы уже разбирали несколько алгоритмов, работающих за квадратичное время — сортировка пузырьком, выбором, вставкой. Эти алгоритмы просты, но требуют оптимизации, когда дело доходит до больших массивов. Для каждого из них существуют оптимизации, делающие их "быстрыми" — то есть работающими за время n log n .

Начнём с того, что "вспомним" старые сортировки. Да, мы уже решали эти задачи, но, пожалуйста, напишите код для них заново. Это будет хорошим упражнением для начала года.

01: Сортировка пузырьком

Дан список целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный список на экран.

пузырьковой сортировки . Решение оформите в виде функции bubble_sort(A) .

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

02: Сортировка выбором

Дан список целых чисел. Выведите все элементы этого списка в порядке невозрастания значений. Выведите новый список на экран.

Решите эту задачу при помощи алгоритма сортировки выбором . Решение оформите в виде функции selection_sort(A) .

В алгоритме сортировки выбором начальная часть списка уже отсортирована. Мы находим наибольший элемент в оставшейся части списка полным перебором и ставим его в конец отсортированной части (просто обменом).

Вспомогательным списком пользоваться нельзя.

03: Сортировка вставкой

Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.

Решите эту задачу при помощи алгоритма сортировки вставкой . Решение оформите в виде функции insertion_sort(A) .

В этой задаче нельзя пользоваться дополнительным списком и операциями удаления и вставки элементов.

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть списка уже отсортирована. Далее первый элемент из неотсортированной части добавляется в отсортированную часть списка. Для этого находится позиция, в которую необходимо вставить элемент, затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

Обратите внимание, на почти отсортированном массиве ваш алгоритм не должен работать за квадратичное время.

Поиск подходящего места для вставки можно сделать бинарным поиском. При этом можно пользоваться модулем bisect (см. документацию и по-русски).

От сортировки выбором к пирамидальной сортировке

Для определённости будем сортировать массив по возрастанию. (Точнее, по неубыванию, так как в массиве могут быть совпадающие элементы).

Основная схема сортировки выбором сохраняется. Массив разделен на две части, одна из которых (правая) уже отсортирована, причем любой элемент отсортированной части не меньше любого элемента неотсортированной:

Пока размер неотсортированной части > 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 для этого элемента.

Однако при реализации полезно сделать два усовершенствования. Во-первых, нетрудно избавиться от рекурсии. Во-вторых, нет необходимости на каждом шаге просеивания действительно копировать просеиваемый элемент на место его родителя – его можно записать лишь в самом конце просеивания на его окончательное место.

Полезно заметить сходство этого алгоритма с вставкой очередного элемента в подходящее место отсортированной части массива, которая происходит при простой сортировке вставками.

Для оценки времени работы заметим, что число шагов просеивания не превышает высоты кучи, а время выполнения каждого шага ограничено константой.

Вывод кучи

05: Просеивание вниз

Реализуйте функцию sift_down , выполняющую просеивание вниз элемента кучи, который оказался меньше положенного.

Входные данные даются в формате из предыдущей задачи.
Запрос задаётся двумя целыми числами i и x . Требуется уменьшить значение i -го элемента кучи на x и выполнить sift_down для восстановления кучи.
В качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент после выполнения sift_down . (Вывести в отдельной строке одно число – соответствующий индекс). Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

Лучше после:)

Это точно трудности?

Проще всего алгоритм описать так. Если у A[i] нет сыновей в дереве или если они не превосходят его по величине, то ничего делать не надо. В противном случае надо поменять местами его с максимальным из сыновей. (Если эти сыновья равны, то, вообще говоря, менять можно с любым из них. Но чтобы все последующие задачи были приняты тестирующей системой, надо менять непременно с левым). После чего снова получим «немого испорченную кучу», но теперь элемент, который, возможно, имеет меньше значение, чем требуется, находится на новом месте. Соответственно надо выполнить sift_down для этого элемента. При реализации можно избавиться от рекурсии. Оценка времени работы такая же, как для sift_up . Типичная ошибка – неправильная обработка ситуации, когда имеется только левый сын.

06: Извлечение максимального

Реализуйте функцию extract_max , извлекающую из кучи максимальный элемент и восстанавливающую её структуру. (см. раздел "Операции с кучей" выше)

На вход даётся куча в формате из предыдущей задачи.
Требуется вывести N -1 строку, в каждой – два числа. Первое – индекс конечного положения последнего элемента кучи после перестановки его на нулевое место и просеивания; второе – значение извлечённого элемента (который раньше был на нулевом месте).

Просеивание и равенство элементов

07: Приоритетная очередь

Требуется реализовать с помощью кучи приоритетную очередь, поддерживающую две операции: добавить элемент heappush и извлечь максимальный элемент heappop .

В первой строке вводятся два числа – максимальный размер приоритетной очереди N и количество запросов M . (1 ≤ M , N ≤ 10 5).
Далее идут M строк, в каждой строке – по одному запросу. Первое число в запросе задаёт его тип, остальные числа (если есть) – параметры запроса.
Тип 1 – извлечь максимальный (без параметров),
Тип 2 – добавить данный элемент в очередь.

В ответ на запрос типа 1 следует вывести:
Если извлекать было нечего (очередь пуста), то -1.
Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного положения элемента после его просеивания (если же удалён был последний элемент и просеивать осталось нечего, вывести -1); второе – значение извлечённого элемента.
В ответ на запрос типа 2 следует вывести:
Если добавить нельзя (нет места, поскольку в очереди уже N элементов), то вывести -1. (При этом куча не должна измениться).
Иначе – индекс добавленного элемента.
Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

08: Приоритетная очередь с удалением

Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса – запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа 3 с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.

В ответ на запрос типа 3 следует вывести:
-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 целых чисел.
Преобразуйте массив в кучу и выведите их по порядку.

Лучше после:)

Это точно трудности?

Основная идея состоит в следующем. Мы можем сразу вызвать sift_down для любой вершины, чьи сыновья являются листьями. Вызвав её для всех таких вершин, получим поддеревья высоты 2, в каждом из которых выполняется основное свойство кучи. И так далее – новые вызовы sift_down будут обеспечивать выполнение основного свойства кучи в поддеревьях всё большего и большего размера. Реализовать это проще всего с помощью цикла for, который вызывает sift_down для всех элементов массива, кроме листьев дерева, справа налево.

Что быстрее?

(Для хорошо знающих математику) Довольно очевидно, что каждая из реализаций 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

От сортировки пузырьком к быстрой сортировке Хоара и поиску медианы

В сортировке пузырьком мы переставляем элемент только на соседнюю позицию, "всплывая" его, насколько это возможно. При этом после "всплытия" мы ещё много раз будем выполнять сравнения с этим элементом. В быстрой сортировке мы берём элемент и максимально быстро "топим" элементы, меньшие его, и "всплываем" элементы, большие. Тем самым элемент оказывается на необходимой для него в отсортированном массиве позиции. После этого рекурсивно сортируем всё меньшее и отдельно большее, необходимости сравнивать с данным элементом при этом уже никогда не будет.

Точнее, основа алгоритма — рекурсивная функция, принимающая на вход список, а также позиции от и до которой необходимо отсортировать список. При сортировке всего списка используются значения по умолчанию — сортировать от начала и до конца.

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 , а после него элементы, больше либо равные опорному.

Подсказка

Я — овощ, и не хочу думать

Операция переупорядочивания массива:
Два индекса - 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 строках даны отсортированные по неубыванию массивы.

Выведите объединение этих последовательностей, отсортированную по неубыванию. При этом разрешается только однократный проход по каждому из массивов.

Подсказка

Я — овощ, и не хочу думать

Никто не видит, как я подглядываю...

Необходимо собрать кучу из N троек (начальный элемент i -го массива, i , 0). После этого нужно последовательно извлекать из кучи минимальную тройку. Первый элемент тройки — минимальный ещё не выведенный элемент, его нужно отправить на вывод. А второй элемент тройки — номер массива, из которого нужно взять элемент и назад добавить в кучу, а третий — индекс последнего взятого элемента из этого массива.

19: Формирование серий для внешней сортировки

В этой задаче мы представим себе, что у нас есть оперативной памяти на P чисел, и последовательность целых чисел, которую необходимо отсортировать. Её длина существенно больше P .

Необходимо создать список, в которым исходная последовательность разбита на серии неубывающих чисел, причём длина каждой серии не меньше P . В простейшем случае мы могли бы считывать по P чисел, сортировать их и записывать назад на диск (записать в стандартный вывод). Однако есть красивый алгоритм, позволяющий сразу создавать серии длиной в среднем 2P .

Считаем первые P чисел и сформируем из них минимальную кучу. Дальше извлекаем минимальный элемент из кучи и сразу же добавляем его в текущую серию. После этого считываем очередной элемент последовательности. Если он равен элементу, который мы только что вывели, то его тоже можно добавить в серию (вывести) и продолжить дальше. Если он больше текущего, то он может быть добавлен в серию в будущем. Для этого его нужно включить в кучу и продолжить работу. Однако если новый элемент меньше текущего, то его нельзя добавить в текущую серию. Тогда добавим его во вторую кучу. Размер первой кучи при этом уменьшится на 1, а размер второй — увеличится на 1, в сумме мы по-прежнему храним P элементов. Будет продолжаться до тех пор, пока все P элементов станут непригодными для добавления в текущую серию (и окажутся во второй куче, тогда как первая станет пустой). Это значит, что текущую серию нужно закончить, поменять кучи местами и начать новую серию.

Оказывается, что при таком подходе длина получающихся серий будет в среднем 2P , и уж точно не меньше P каждая. При этом если в исходных данных есть много отсортированных кусков, то длины серий будут гораздо больше, вплоть до ровно одной серии на полностью отсортированных данных!

В первой строке даны два числа P и N — количество элементов, помещающихся в оперативную память, и длина последовательности для сортировки соответственно. Во второй строке дана последовательность целых чисел длины N .

Выведите эту последовательность, упорядоченную в серии по описанному алгоритму. Кроме списка с последовательностью из условия, запрещается использовать списки суммарной длиной больше P .

Следующей строчкой выведите среднюю длину серий, округлённую до двух знаков после запятой.

20: Внешняя сортировка

Достаточно эффективная внешняя сортировка может быть реализована следующим образом: сначала мы формируем начальные серии (так как делали это в предыдущей задаче) и записываем их последовательно в N различных "файлов" (первую серию в первый файл, вторую — во второй и т.д.). После этого, мы начинаем сливать N -ки отсортированных серий вместе, получающиеся серии при этом записывать в другие N различных "файлов". После того, как все N -ки серий будут слиты, мы начинаем сливать N -ки серий второго порядка и записывать их в первые N файлов. Будем продолжать операцию до тех пор, пока весь массив не будет отсортирован.

В первой строке даны три числа P , N и L — количество элементов, помещающихся в оперативную память, количество пар файлов, которые должны использоваться при сортировке, и длина последовательности для сортировки соответственно. В качестве файлов можно использовать обычные списки.

Выполните внешнюю сортировку данных по описанному алгоритму.

Перепишите вашу программу так, чтобы использовались реальные файлы. При каком N достигается максимальная производительность сортировки на вашем компьютере?

Алгоритм Дейкстры с кучей

Пусть длины всех рёбер — натуральные числа. Тогда задачу поиска кратчайшего пути можно свести к случаю рёбер длины 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. Результаты нужно выводить в порядке следования запросов во входных данных

24: Тупики

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

Дано расписание движения электричек, в котором для каждой электрички указано время ее прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал - конечная станция, то электричка может стоять на нем довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.

Тупики пронумерованы числами от 1 до K . Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого- то тупика отправилась в момент времени X , то электричку, которая прибывает в момент времени X , в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 - можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные Сначала вводятся число K - количество тупиков и число N - количество электропоездов (1≤K≤100000 , 1≤N≤100000 ). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 10 9 . Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая- нибудь электричка (или даже несколько) отправляются в момент прибытия какой- нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

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

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 чисел. Результат должен быть выведен с двумя знаками после десятичной точки.

26: Поиск максимума в скользящем окне за O(n)

На вход даётся ширина окна — натуральное число, и последовательность целых чисел.

Необходимо вывести максимальное число на каждом отрезке длиной в ширину окна.

В первой строке даны два числа W и N — шинира окна и длина последовательности. Во второй строчке даны N целых чисел. Гарантируется, что N не меньше W .

Окно скользит по последовательности с шагом 1. На каждом шаге надо найти максимальный элемент попавший в окно.

Наивное решение этой задачи имеет асимптотику O(NW) . У этой задачи существует решение за O(N) , однако решение за время O(N log W) тоже пойдёт.

КУЧА

1. Большое количество чего-нибудь, наваленное в одном месте горкой. Куча песку. «Навозну кучу разрывая, петух нашел жемчужное зерно.» Крылов . «Царь однажды воинам своим велел снести земли по горсти в кучу.» Пушкин . Куча листьев.

|| Беспорядочное нагромождение, груда разных предметов. В углу была свалена в кучу всякая рухлядь. Из горевшего дома выносили пожитки и клали в одну кучу.

❖ Валить всё в одну кучу (разг.) - перен. без разбора, огульно, смешивать в одно различные явления. Куча мала! - восклицание, употр. в детской игре, когда устраивается общая свалка.

Толковый словарь Ушакова . Д.Н. Ушаков. 1935-1940 .

Смотреть что такое "КУЧА" в других словарях:

Жен. груда, вброх, громада, вещи горой; | толпа, сборище; * много; | новг., твер. копна сена. | моск. количество скота, выгоняемого от одного хозяина в стадо. Саженные кучи щебня. Куча людей, народа. На мне куча забот. Муравьиная куча. муравейник … Толковый словарь Даля

Ворох, громада, груда, горка, кипа, купа, сугроб; скирд, стог, омет. Тела лежали грудами. В этом селе избы стоят гнездами. Деревья стоят купами. Стог (скирд) сена. Кладь (одонье, одонья, зарод) хлеба. Омет соломы.. Ср. . См. возвышенность, ворох … Словарь синонимов

КУЧА, и, жен. 1. Скопление чего н. сыпучего. К. песку. Сгрести сухие листья в кучу. 2. чего. Нагромождение чего н., множество кого чего н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей. Куча мала! возглас в детской игре, по к рому… … Толковый словарь Ожегова

куча - разг. КУЧА, груда, разг. ворох, разг. гора … Словарь-тезаурус синонимов русской речи

куча - куча, гора, груда, кипа, ворох Стр. 0501 Стр. 0502 Стр. 0503 Стр. 0504 Стр. 0505 … Новый объяснительный словарь синонимов русского языка

куча - груда штабель кипа (бумаг) пачка связка пакет — Тематики нефтегазовая промышленность Синонимы грудаштабелькипа (бумаг)пачкасвязкапакет EN pile … Справочник технического переводчика

Горелая куча. Арх., Детск. То же, что куча мала. АОС 9, 341. Куча звёзд. Сиб. Созвездие Плеяд. ФСС, 102. Куча мала! Детск. Возглас в игре, являющийся сигналом к общей свалке. Ф 1, 273; ФСРЯ, 219; БТС, 483, 517. Куча с грудой. Арх. О большом… … Большой словарь русских поговорок

Сущ., ж., употр. часто Морфология: (нет) чего? кучи, чему? куче, (вижу) что? кучу, чем? кучей, о чём? о куче; мн. что? кучи, (нет) чего? куч, чему? кучам, (вижу) что? кучи, чем? кучами, о чём? о кучах 1. Кучей каких либо вещей, материалов и т. п … Толковый словарь Дмитриева

Куча - Большая или Ближняя (Дор), Шер (Шöр), Малая (Уудор) Куча прав, притоки Ижмы. Дл. соответственно 31 км, 33 км, 13 км. Гидроним Куча связан с рус. круча «крутой, обрывистый берег; высокий берег в излучине реки». Один из берегов Кучи возвышен,… … Топонимический словарь Республики Коми

У этого термина существуют и другие значения, см. Куча (значения). Изображение жителей Кучи на фреске в Кизиле. Куча (также Кучэ и Кучар) древнее буддийское государ … Википедия

Книги

• Куча (изд. 2015 г.) , Перец Маркиш. Перец Маркиш - еврейский поэт, драматург и романист. В его поэме `Куча`, впервые изданной на идише в 1922 году, излита горечь от увиденных последствий еврейских погромов на Украине в годы…

Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).

Для дальнейшего чтения необходимо иметь представление о деревьях , а также желательно знать об оценке сложности алгоритмов . Алгоритмы в этой статье будут сопровождаться кодом на C#.

Введение

Двоичную кучу удобно хранить в виде одномерного массива, причем левый потомок вершины с индексом i имеет индекс 2*i+1 , а правый 2*i+2 . Корень дерева – элемент с индексом 0. Высота двоичной кучи равна высоте дерева, то есть log 2 N, где N – количество элементов массива.

Приведу заготовку класса на C#:

Public class BinaryHeap { private List list; public int heapSize { get { return this.list.Count(); } } }

Добавление элемента

Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае следует «поднимать» новый элемент на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи:

Иначе говоря, новый элемент «всплывает», «проталкивается» вверх, пока не займет свое место. Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна O(log 2 N).

Public void add(int value) { list.Add(value); int i = heapSize - 1; int parent = (i - 1) / 2; while (i > 0 && list < list[i]) { int temp = list[i]; list[i] = list; list = temp; i = parent; parent = (i - 1) / 2; } }

Упорядочение двоичной кучи

Метод heapify восстанавливает основное свойство кучи для дерева с корнем в i-ой вершине при условии, что оба поддерева ему удовлетворяют. Для этого необходимо «опускать» i-ую вершину (менять местами с наибольшим из потомков), пока основное свойство не будет восстановлено (процесс завершится, когда не найдется потомка, большего своего родителя). Нетрудно понять, что сложность этого алгоритма также равна O(log 2 N).

Public void heapify(int i) { int leftChild; int rightChild; int largestChild; for (; ;) { leftChild = 2 * i + 1; rightChild = 2 * i + 2; largestChild = i; if (leftChild < heapSize && list > list) { largestChild = leftChild; } if (rightChild < heapSize && list > list) { largestChild = rightChild; } if (largestChild == i) { break; } int temp = list[i]; list[i] = list; list = temp; i = largestChild; } }

Построение двоичной кучи

Public void buildHeap(int sourceArray) { list = sourceArray.ToList(); for (int i = heapSize / 2; i >= 0; i--) { heapify(i); } }

Извлечение (удаление) максимального элемента

Public int getMax() { int result = list; list = list; list.RemoveAt(heapSize - 1); return result; }

Сортировка с применением двоичной кучи

Public void heapSort(int array) { buildHeap(array); for (int i = array.Length - 1; i >= 0; i--) { array[i] = getMax(); heapify(0); } }

Заключение

Синонимы:

Ворох, громада, груда, горка, кипа, купа, сугроб; скирд, стог, омет.

Тела лежали грудами. В этом селе избы стоят гнездами. Деревья стоят купами. Стог (скирд) сена. Кладь (одонье, одонья, зарод) хлеба. Омет соломы..

Ср. . См. возвышенность, ворох, много

высыпать кучу новостей, собрать в кучу... ..

Словарь русских синонимов 4

куча

Синонимы:

бездна, бесчисленность, бунт, вагон, воз, ворох, гибель, гора, груда, купа, кучка, масса, множество, навал, нагромождение, пропасть, прорва, руно, сила, скопление, сорус, спод, стог, сугроб, тьма, тьма тем, тьма-тьмущая, уйма, уймища

КУЧА значение

Т.Ф. Ефремова Новый словарь русского языка. Толково- словообразовательный

куча

Значение:

ку ́ча

а) Что-л., сваленное горкой, грудой.

б) разг. Большое количество, скопление чего-л.

2) разг. Толпа, скопление (людей, животных).

3) разг. Большое количество, множество.

С.И. Ожегов, Н.Ю. Шведова Толковый словарь русского языка

куча

Значение:

КУ́ЧА, -и, ж.

1. Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.

2. чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей.

Куча мала! возглас в детской игре, по к-рому начинается общая свалка.

| уменьш. кучка , -и, ж. (к 1 знач. ).

Малый академический словарь русского языка

куча

Значение:

И, ж.

Большое количество чего-л., обычно сыпучего, мелкого, наваленное, насыпанное в одном месте.

Куча песку. Куча камней.

У хижин, на рогожках, кучами лежали овощи и сушились на солнце.

Большое количество каких-л. предметов, нагроможденных в беспорядке один на другой; груда.

Комната отделялась от улицы широкими сенями, где были свалены в кучу корзины, сети --- и всякая хозяйственная утварь. Кетлинская, Мужество.

2. Разг.

Беспорядочное скопление людей, животных.

На берегу теснилась куча негров и негритянок. И. Гончаров, Фрегат «Паллада».

От Вязьмы французские войска, прежде шедшие тремя колоннами, шли теперь одною кучей. Л. Толстой, Война и мир.

{Овцы} неподвижно стоят, сбившись в кучу, спасаясь от жары и оводов. Серафимович, Лихорадка.

кого-чего. Разг. Большое количество; множество.

Покупателей этих произведений {лубочных картин} обыкновенно немного, но зато зрителей - куча. Гоголь, Портрет.

Мы видели в предыдущей главе, что добродетельная женщина наделала кучу глупостей. Писарев, Кукольная трагедия с букетом гражданской скорби.

- У меня куча дел накопилась в управлении, - сказал он весело. Крымов, Танкер «Дербент».

Чего-либо, обычно сыпучего, мелкого, наваленного, насыпанного в одном местечего-либо.

• Куча песка.
• Его одежда валялась на полу бесформенной кучей .

Синонимы к слову куча

• • груда
  • масса
  • скопище
  • толпа

Гиперонимы к слову куча

Однокоренные слова для куча

• прилагательные

  • кучный

  умласк

  • кучка

Фразеологизмы для слова куча

• • куча мала