Чего-либо, обычно сыпучего, мелкого, наваленного, насыпанного в одном местечего-либо.
- Куча песка.
- Его одежда валялась на полу бесформенной кучей .
- Не представляю, как люди жили в коммуналках в одной куче , дети, однако же, были, и много детей, все делали в спешке, где уж тут до взаимной психотерапии, подготовки, ласк, слов.
- Эта шуба кучу денег стоит!
- Моего друга зовут Куча .
- Мою подругу зовут Куча .
Синонимы к слову куча
- груда
- масса
- скопище
- толпа
Гиперонимы к слову куча
Однокоренные слова для куча
прилагательные
- кучный
умласк
- кучка
Фразеологизмы для слова куча
- куча мала
Синонимы:
Ворох, громада, груда, горка, кипа, купа, сугроб; скирд, стог, омет.
Тела лежали грудами. В этом селе избы стоят гнездами. Деревья стоят купами. Стог (скирд) сена. Кладь (одонье, одонья, зарод) хлеба. Омет соломы..
Ср. . См. возвышенность, ворох, много
высыпать кучу новостей, собрать в кучу... ..
Словарь русских синонимов 4
куча
Синонимы:
бездна, бесчисленность, бунт, вагон, воз, ворох, гибель, гора, груда, купа, кучка, масса, множество, навал, нагромождение, пропасть, прорва, руно, сила, скопление, сорус, спод, стог, сугроб, тьма, тьма тем, тьма-тьмущая, уйма, уймища
КУЧА значение
Т.Ф. Ефремова Новый словарь русского языка. Толково- словообразовательный
куча
Значение:
ку ́ча
ж.а) Что-л., сваленное горкой, грудой.
б) разг. Большое количество, скопление чего-л.
2) разг. Толпа, скопление (людей, животных).
3) разг. Большое количество, множество.
С.И. Ожегов, Н.Ю. Шведова Толковый словарь русского языка
куча
Значение:
КУ́ЧА, -и, ж.
1. Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.
2. чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей.
Куча мала! возглас в детской игре, по к-рому начинается общая свалка.
| уменьш. кучка , -и, ж. (к 1 знач. ).
Малый академический словарь русского языка
куча
Значение:
И, ж.
Большое количество чего-л., обычно сыпучего, мелкого, наваленное, насыпанное в одном месте.
Куча песку. Куча камней.
У хижин, на рогожках, кучами лежали овощи и сушились на солнце.
Большое количество каких-л. предметов, нагроможденных в беспорядке один на другой; груда.
Комната отделялась от улицы широкими сенями, где были свалены в кучу корзины, сети --- и всякая хозяйственная утварь. Кетлинская, Мужество.
2. Разг.
Беспорядочное скопление людей, животных.
На берегу теснилась куча негров и негритянок. И. Гончаров, Фрегат «Паллада».
От Вязьмы французские войска, прежде шедшие тремя колоннами, шли теперь одною кучей. Л. Толстой, Война и мир.
{Овцы} неподвижно стоят, сбившись в кучу, спасаясь от жары и оводов. Серафимович, Лихорадка.
кого-чего. Разг. Большое количество; множество.
Покупателей этих произведений {лубочных картин} обыкновенно немного, но зато зрителей - куча. Гоголь, Портрет.
Мы видели в предыдущей главе, что добродетельная женщина наделала кучу глупостей. Писарев, Кукольная трагедия с букетом гражданской скорби.
- У меня куча дел накопилась в управлении, - сказал он весело. Крымов, Танкер «Дербент».
КУЧА
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 году, излита горечь от увиденных последствий еврейских погромов на Украине в годы…
Здравствуйте, Хабросообщество!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат! В своем цикле статей я рассмотрю разные виды куч и способы их применения на практике:
1) Биномиальную кучу
2) Левую кучу
3) Фибоначчиеву кучу
4) Применение этих структур данных на практике
Постановка задачи:
Построить структуру данных, в которой будет храниться множество наших объектов (разных в зависимости от задачи), у каждого объекта будет поле ключ, по которому мы быстро сможем находить минимальный элемент. Для этой структуры должны бать возможны операции:
Make – создание новой пустой кучи,
Insert – вставка нового элемента в кучу,
Minimum – минимальный ключ,
ExtractMin – извлечение минимума,
Merge – слияние 2-х куч,
Decrease – уменьшение ключа,
Delete – удаление объекта.
Многие знакомы с простейшими способами реализации этой структуры, такими как массив:) и двоичная куча. На них я не буду подробно останавливаться ввиду их простоты и общеизвестности.
Как известно, для двоичной кучи
асимптотика перечисленных выше операций такова:
Make – O(1)
Merge – O(N)
Insert – O(log N) – где N – количество элементов в куче.
Minimum – O(1)
ExtractMin – O(log N)
Decrease – O(log N)
Delete – O(log N)
Описывать алгоритм работы двоичной кучи я не буду, так как он неоднократно описывался везде, в том числе и на Хабре. Для тех, кто не знаком с двоичной кучей, я бы порекомендовал прежде, чем продолжать чтение ознакомиться с ней.
Биномиальная куча
Биномиальная куча
– это множество биномиальных деревьев
с некоторыми ограничениями. Мы их введем чуть позже.
Биномиальное дерево
– дерево, которое задается рекуррентно:
B i – это B i – 1 , в котором левым сыном корня сделали дерево B i – 1 .
B 0 - это просто вершина.
Примеры для B 0 , B 2 , B 3:
У биномиального дерева(B k) есть ряд интересных свойств
:
T.1.
2 k вершин
T.2.
Высота дерева k
T.3.
C i k вершин глубины i (вот почему они называются биномиальными: C i k биномиальный коэффициент).
T.4.
Дети корня – это B, B k – 2 , …, B 0 – именно в этом порядке.
T.5.
Максимальная высота вершины в биномиальном дереве O(log N)
Доказываются
свойства по индукции. Предлагаю читателям самим провести доказательство, для лучшего понимания деревьев.
Итак, теперь вернемся к биномиальным кучам
. Биномиальная куча
– множество биномиальных деревьев, со следующими ограничениями:
1) В каждом из биномиальных деревьев сохраняется свойство кучи.
2) Нет двух деревьев одинакового размера
3) Деревья упорядочены по размеру.
Поговорим о том, как биномиальная куча будет храниться в программе. Мы будем использовать метод “левый сын – правый брат”. Будем хранить корневой список(root_list , его длина root_list.length), в котором будут корни биномиальных деревьев, в порядке возрастания высоты. У каждой вершины будут следующие поля:
data – данные, которые хранятся в вершине(по ним мы и находим минимум)
right – правый брат
child – левый сын
degree – степень вершины(очевидно деревья в биномиальной куче упорядоченны по этому полю)
Сразу же заметим:
Свойство
H.1:
Длина root_list.length = O(log N), где N - количество элементов в куче.
Для доказательства достаточно заметить, что из-за T.1, наличие дерева B k в двоичной записи числа.
Перейдем к описанию операций, которые можно проводить с биномиальными кучами:
Make
Задача
: создать пустую кучу.
Алгоритм
: создаем пустой список root_list .
Сложность
: очевидно, время работы O(1).
Merge
Задача
: объединить 2 кучи в 1.
Алгоритм
: сначала объединим корневые списки куч в 1 корневой список, поддерживая упорядоченность по degree. Алгоритм аналогичен слиянию 2-х массивов в mergeSort:
Храним по указателю на начало списков и в результирующий список записываем минимальный из них, тот откуда только что записали сдвигаем на следующий. Далее проходимся от начала до конца нового полученного корневого списка и сливаем деревья одинакового размера в 1. Могут быть случаи:
1) Только 2 дерева одинакового размера. Тогда объединяем их.
2) 3 дерева одинакового размера. Объединяем 2 последних.
При объединении двух деревьев нужно лишь посмотреть в корне какого из них меньший ключ и сделать другое дерево левым сыном корня этого дерева.
Пример, того, что получается после объединения двух куч:
Сложность
: Время работы O(root_list1.length) + O(root_list2.length) = (по свойству H.1) = O(log N).
За один проход (O(log N)) мы получим объединенное биномиальное дерево. Получаем, что общая сложность O(log N).
Insert
Задача
: вставить новый элемент в кучу.
Алгоритм
: Создаем кучу из одного элемента и объединяем с нашей кучей.
Сложность
: O(1) + O(log(N)) = O(log(N)).
Minimum
Задача
: найти минимум в куче.
Алгоритм
: очевидно, минимум находится в корневом списке, то есть, чтобы его найти нужно пройтись по корневому списку.
Сложность
: O(root_list.length) = O(log(N)).
ExtractMin
Задача
: удалить минимальный элемент.
Алгоритм
: находим его при помощи Minimum . Удаляем его из корневого списка. Из перевернутого списка его детей делаем root_list для новой кучи (H 1) и объединяем исходную кучу с H 1 .
Сложность
: так как каждая операция в извлечении минимума работает за O(log N): O(log N) + O(log N) + O(log N) = O(log N)
Decrease
Задача
: уменьшить значение data в данной вершине.
Алгоритм
: уменьшаем значение в вершине. Тогда свойство кучи будет возможно нарушено для нашей вершины и ее предка, тогда меняем их местами. Продолжаем процесс, пока наша вершина не “всплывет” на свое место. Алгоритм работает также, как аналогичный в двоичной куче.
Сложность
: В худшем случае наша вершина будет всплывать до корня, то есть мы совершим O(log N) действий (вершина на каждом шаге “всплывает” на уровень выше, а высота биномиального дерева по T.5 O(log N))
Delete
Задача
: удалить произвольный элемент.
Алгоритм
: сначала уменьшим при помощи Decrease значение в вершине до минимально возможного. А затем удалим минимальный в куче (ExtractMin).
Сложность
: O(log N) + O(log N) = O(log N)
Заключение.
Мы рассмотрели структуру данных биномиальная куча и доказали ее асимптотику.
В следующей статье на основе биномиальной кучи мы построим чуть более сложную структуру данных, а именно Фибоначчиеву кучу.
Поиграться с биномиальными кучами можно на rain.ifmo.ru/cat/view.php/vis/heaps/binomial-2001
Почитать более подробно можно в Т.Кормен «Алгоритмы: построение и анализ.».
Всем спасибо за внимание, и до новых встреч!
Двоичная куча (binary heap) – просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).
Для дальнейшего чтения необходимо иметь представление о деревьях , а также желательно знать об оценке сложности алгоритмов . Алгоритмы в этой статье будут сопровождаться кодом на C#.
Введение
Двоичная куча представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи : приоритет каждой вершины больше приоритетов её потомков. В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-heap , поскольку корень поддерева является максимумом из значений элементов поддерева. В этой статье для простоты используется именно такое представление. Напомню также, что дерево называется полным бинарным , если у каждой вершины есть не более двух потомков, а заполнение уровней вершин идет сверху вниз (в пределах одного уровня – слева направо).Двоичную кучу удобно хранить в виде одномерного массива, причем левый потомок вершины с индексом i имеет индекс 2*i+1 , а правый 2*i+2 . Корень дерева – элемент с индексом 0. Высота двоичной кучи равна высоте дерева, то есть log 2 N, где N – количество элементов массива.
Приведу заготовку класса на C#:
Public class BinaryHeap
{
private List
Добавление элемента
Новый элемент добавляется на последнее место в массиве, то есть позицию с индексом heapSize :
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае следует «поднимать» новый элемент на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи:
Иначе говоря, новый элемент «всплывает», «проталкивается» вверх, пока не займет свое место. Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна 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; } }
Построение двоичной кучи
Наиболее очевидный способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма O(N log 2 N). Однако можно построить кучу еще быстрее - за О(N). Сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод heapify для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены). Потомки гарантированно есть у первых heapSize/2 вершин.Public void buildHeap(int sourceArray) { list = sourceArray.ToList(); for (int i = heapSize / 2; i >= 0; i--) { heapify(i); } }
Извлечение (удаление) максимального элемента
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав heapify для корня, то есть упорядочив все дерево.Public int getMax() { int result = list; list = list; list.RemoveAt(heapSize - 1); return result; }
Сортировка с применением двоичной кучи
Заметим, что можно отсортировать массив, сначала построив из него двоичную кучу, а потом последовательно извлекая максимальные элементы. Оценим временную сложность такого элемента: построение кучи – O(N), извлечение N элементов – O(N log 2 N). Следовательно, итоговая оценка O(N log 2 N). При этом дополнительная память для массива не используется.Public void heapSort(int array) { buildHeap(array); for (int i = array.Length - 1; i >= 0; i--) { array[i] = getMax(); heapify(0); } }