Куча в программировании. Смотреть что такое "куча" в других словарях
Память, которую используют программы, состоит из нескольких частей — сегментов :
Сегмент кода (или ещё «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.
Сегмент 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; }
куча
ж. груда, вброх, громада, вещи горой;
толпа, сборище; *много;
новг. твер. копна сена.
Моск. количество скота, выгоняемого от одного хозяина в стадо. Саженные кучи щебня. Куча людей, народа. На мне куча забот. Муравьиная куча. муравейник. Комком да в кучку, на скорую (на крестьянскую ручку.) Велика куча (денег) не надокучит. Была кучка, стал ворошек, прикопили. На чужую кучу нечего глаза пучить. Комком да в кучку, да под леву ручку. Смотрит в кучку, а глядит врознь! Народ глуп: все в кучу лезет. По кучке, все онучки; а станешь считать, одной нет! Галичане в кучу, костромичи в кучу, ярославцы прочь, или врознь: от междоусобии Шемяки с Шуйским.
Сиб. заводе, количество уголья, выходящего в один раз из печи. Класть кучи, жечь угодье.
Сиб. последняя пора беременности. Даль вам Бог кого? Нет, еще жена в куча. Кучки мн. умалит. ниж. созвездие плеяд, утиное гнездо, бабы, стожары.
Южн. зап. еврейский праздник пасхи (см. куща). Кучный, кучевой, кучечный, к кучкам относящ. Кучный заряд портит дичь. Народ кучно стоит, густо, толпою. Кучевые облака. Кучистый, кучковатый, состоящий из куч, усеянный кучками. Кученок м. небольшая угольная куча, в которой недоспевший при первом пережиге уголь (головни) дожигается. Кучегур м. кучегуры мн. южн. песчаные бугры, сыпучие кочки, шиханы, бараканы. Кучеклад спб. угольщик. Кучить что, кучивать, сбирать, складывать, сгребать в кучи, вороха.
Кучить чем, новг. торговать по мелочи, кучить калачами, квасом.
Кучить картофель, огребать, окучивать. -ся, быть скучиваему, складываему в кучи; толпиться в кучу.
Моржи кучатся арх. вылезают юровом (стаей) на лед и сходятся.
Кому, о чем, сев. вост. просить неотступно, униженно, кланяться, умолять, конаться, домогаться, докучать (докука). Пучился, мучился, а докучился, так кинул. Кучился, мучился, а упросил, так бросил. Мучится, а никому не кучится. Вскучил волосы. Вкучился, влез в кучу. Крот выкучил землю. Докучивай картофель. Накучили много. Окучивай его. Подкучивай сбоку. Стрелки скучились. Покучься соседу. Вскучишься, как беда придет. Насилу рубля докучился. Закучился, закланялся. Накучился, накланялся. Кученье ср. действ. по глаг. на ть и на ся. Кучка ж. об. действ. по глаг. кучить и
умалит. куча. Строить кучки, у стрелков, сбегаться из рассыпного строя в кучки, при налете конницы. Кучкать что, комкать, складывать или свертывать, сминать в кучу. Кучкаться казач. толпиться, сбиваться в кучу, куриться, усаживаться тесно. Кучкаться или тул. кучать, медлить, мешкать, копаться. Что там кучаешь?
Толковый словарь русского языка. Д.Н. Ушаков
куча
Большое количество чего-н., наваленное в одном месте горкой. Куча песку. Навозну кучу разрывая, петух нашел жемчужное зерно. Крылов. Царь однажды воинам своим велел снести земли по горсти в кучу. Пушкин. Куча листьев.
Беспорядочное нагромождение, груда разных предметов. В углу была свалена в кучу всякая рухлядь. Из горевшего дома выносили пожитки и клали в одну кучу.
перен. Большое количество, много (разг. фам.). У них куча детей. Получить целую кучу неприятностей. Народу собралось - куча! Валить всё в одну кучу (разг.) - перен. без разбора, огульно, смешивать в одно различные явления. Куча мала! - восклицание, употр. в детской игре, когда устраивается общая свалка.
Толковый словарь русского языка. С.И.Ожегов, Н.Ю.Шведова.
куча
Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.
чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей. * Куча мала! - возглас в детской игре, по к-рому начинается общая свалка.
уменьш. кучка, -и, ж. (к 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МД вместе с кучей барахла, автокраном и УАЗиком.
Из этих небольших примеров видно, что сотрудники государственной полиции в Праге валили в одну кучу социал-демократов и националистов, бомбы, баллоны, рецепты и рескрипты, правящего монарха и изобретателя Эдисона, анархистов и аграрников и т.
Ее агротехнические методы год от года совершенствовались, количество мешков с лусавендрой, отправляемых на рынок в Мазадону, неуклонно возрастало, все выше становились кучи блестящих рисовых зерен в ее закромах.
Пиздвилльской долины говорят ты отплываешь на неспешном корабле в Китай строго из-за кучи денег и азотистой кинопехоты.
Когда отец Дадуса закончил сортировать рыбу, у него получилось три кучи : большая рыба предназначалась для продажи на рынке, немного оставили себе на жареху, а всевозможную мелочь Дадус и Айван должны были раздать толпившейся вокруг детворе.
Девица, лица которой за кучей съестных припасов я рассмотреть не мог, хотя ее запах и показался мне странно знакомым, не дойдя пару ступенек до старцев, уже жадно протянувших руки к еде, аккуратненько поставила ногу точно в пустоту, мимо верхней ступени.
При Лаврентии Павловиче тоже придерживались такой системы - если ты прячешь куда-то алмазик, то лучше в кучу стекол такого же размера.
Единственный намек на беспорядок виднелся на небольшой площадке перед Первым Аляскинским банком ПАП, где на козлах среди кучи инструментов и пивных бутылок лежали две недоделанные фигуры из пенополистирола.
Нет, он только будет выкрикивать бессмысленное слово и под его защитою станет сваливать в одну кучу все разнообразие аспирации человеческой мысли.
И действительно, начал Бадмаев с рассказов о своих успехах в лечении, назвал кучу пациентов с громкими именами, а затем потихонечку сполз к большой политике.
Помимо них, - проворчал Бадья, - вокруг отирается еще куча всякого дерьма.
Тогда Барбуда дождался, пока придет его очередь убирать Веселый Домик, епархию кума, выбрал момент, когда тот отвлекся, и навалил ему кучу в верхний ящик стола.
Жен. груда, вброх, громада, вещи горой; | толпа, сборище; * много; | новг., твер. копна сена. | моск. количество скота, выгоняемого от одного хозяина в стадо. Саженные кучи щебня. Куча людей, народа. На мне куча забот. Муравьиная куча. муравейник … Толковый словарь Даля
КУЧА, кучи, жен. 1. Большое количество чего нибудь, наваленное в одном месте горкой. Куча песку. «Навозну кучу разрывая, петух нашел жемчужное зерно.» Крылов. «Царь однажды воинам своим велел снести земли по горсти в кучу.» Пушкин. Куча листьев.… … Толковый словарь Ушакова
Ворох, громада, груда, горка, кипа, купа, сугроб; скирд, стог, омет. Тела лежали грудами. В этом селе избы стоят гнездами. Деревья стоят купами. Стог (скирд) сена. Кладь (одонье, одонья, зарод) хлеба. Омет соломы.. Ср. . См. возвышенность, ворох … Словарь синонимов
КУЧА, и, жен. 1. Скопление чего н. сыпучего. К. песку. Сгрести сухие листья в кучу. 2. чего. Нагромождение чего н., множество кого чего н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей. Куча мала! возглас в детской игре, по к рому… … Толковый словарь Ожегова
куча - разг. КУЧА, груда, разг. ворох, разг. гора … Словарь-тезаурус синонимов русской речи
куча - куча, гора, груда, кипа, ворох Стр. 0501 Стр. 0502 Стр. 0503 Стр. 0504 Стр. 0505 … Новый объяснительный словарь синонимов русского языка
куча - груда штабель кипа (бумаг) пачка связка пакет — Тематики нефтегазовая промышленность Синонимы грудаштабелькипа (бумаг)пачкасвязкапакет EN pile … Справочник технического переводчика
Горелая куча. Арх., Детск. То же, что куча мала. АОС 9, 341. Куча звёзд. Сиб. Созвездие Плеяд. ФСС, 102. Куча мала! Детск. Возглас в игре, являющийся сигналом к общей свалке. Ф 1, 273; ФСРЯ, 219; БТС, 483, 517. Куча с грудой. Арх. О большом… … Большой словарь русских поговорок
Куча - Большая или Ближняя (Дор), Шер (Шöр), Малая (Уудор) Куча прав, притоки Ижмы. Дл. соответственно 31 км, 33 км, 13 км. Гидроним Куча связан с рус. круча «крутой, обрывистый берег; высокий берег в излучине реки». Один из берегов Кучи возвышен,… … Топонимический словарь Республики Коми
У этого термина существуют и другие значения, см. Куча (значения). Изображение жителей Кучи на фреске в Кизиле. Куча (также Кучэ и Кучар) древнее буддийское государ … Википедия
Книги
- Куча (изд. 2015 г.) , Перец Маркиш. Перец Маркиш - еврейский поэт, драматург и романист. В его поэме `Куча`, впервые изданной на идише в 1922 году, излита горечь от увиденных последствий еврейских погромов на Украине в годы…
Представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков .
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча , поскольку корень поддерева является максимумом из значений элементов поддерева.
В качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами .
Двоичную кучу удобно хранить в виде одномерного массива, причем
- левый потомок вершины с индексом i имеет индекс 2*i+1,
- правый потомок вершины с индексом i имеет индекс 2*i+2.
Корень дерева (кучи) – элемент с индексом 0.
Высота двоичной кучи равна высоте дерева, то есть
log 2 (N+1) ,
где N – количество элементов массива, – округление в большую сторону до ближайшего целого.
Для представленной кучи
log 2 (10+1) = 3,46 = 4
Способ построить кучу из неупорядоченного массива – это по очереди добавить все его элементы. Временная оценка такого алгоритма оценивается как
N·log 2 N .
Можно построить кучу за N шагов. Для этого сначала следует построить дерево из всех элементов массива, не заботясь о соблюдении основного свойства кучи, а потом вызвать метод упорядочения для всех вершин, у которых есть хотя бы один потомок (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).
Потомки гарантированно есть у первых heapSize/2 вершин, где heapSize – размер кучи.
Реализация класса кучи
class Heap {
Static const int SIZE = 100; // максимальный размер кучи
Int *h; // указатель на массив кучи
Int
HeapSize; // размер кучи
public
:
Heap(); // конструктор кучи
Void addelem(int ); // добавление элемента кучи
Void outHeap(); // вывод элементов кучи в форме кучи
Void out(); // вывод элементов кучи в форме массива
Int getmax(); // удаление вершины (максимального элемента)
Void
heapify(int
); // упорядочение кучи
};
Конструктор кучи
h = new int ;
HeapSize = 0;
}
Новый элемент добавляется на последнее место в массиве, то есть позицию с максимальным индексом.
Возможно, что при этом будет нарушено основное свойство кучи, так как новый элемент может быть больше родителя. В таком случае новый элемент «поднимается» на один уровень (менять с вершиной-родителем) до тех пор, пока не будет соблюдено основное свойство кучи.
Сложность алгоритма не превышает высоты двоичной кучи (так как количество «подъемов» не больше высоты дерева), то есть равна log 2 N.
void Heap:: addelem(int n) {
Int i, parent;
parent = (i-1)/2;
while (parent >= 0 && i > 0) {
if (h[i] > h) {
int temp = h[i];
h[i] = h;
h = temp;
parent = (i-1)/2;
HeapSize++;
}
Вывод элементов кучи
Вывод элементов в форме кучи
void Heap:: outHeap(void ) {
Int i = 0;
Int k = 1;
While (i < HeapSize) {
while ((i < k) && (i < HeapSize)) {
cout << h[i] << » « ;
cout << endl;
Вывод элементов кучи в форме массива
void Heap:: out(void ) {
For (int i=0; i< HeapSize; i++) {
cout << h[i] << » « ; }
cout << endl;
}
Упорядочение кучи
void Heap:: heapify(int i) {
int left, right;
Int temp;
if (left < HeapSize) {
if (h[i] < h) {
if (right < HeapSize) {
if (h[i] < h) {
h[i] = h;
h = temp;
В упорядоченном max-heap максимальный элемент всегда хранится в корне. Восстановить упорядоченность двоичной кучи после удаления максимального элемента можно, поставив на его место последний элемент и вызвав метод упорядочения для корня, то есть упорядочив все дерево.
Удаление вершины кучи (максимального элемента)
int Heap:: getmax(void ) {
Int x;
Двоичная куча (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); } }