Структуры данных: двоичная куча (binary heap). Куча синонимы Сортировка пузырьком
Здравствуйте, Хабросообщество!
На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат! В своем цикле статей я рассмотрю разные виды куч и способы их применения на практике:
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
Почитать более подробно можно в Т.Кормен «Алгоритмы: построение и анализ.».
Всем спасибо за внимание, и до новых встреч!
куча
ж. груда, вброх, громада, вещи горой;
толпа, сборище; *много;
новг. твер. копна сена.
Моск. количество скота, выгоняемого от одного хозяина в стадо. Саженные кучи щебня. Куча людей, народа. На мне куча забот. Муравьиная куча. муравейник. Комком да в кучку, на скорую (на крестьянскую ручку.) Велика куча (денег) не надокучит. Была кучка, стал ворошек, прикопили. На чужую кучу нечего глаза пучить. Комком да в кучку, да под леву ручку. Смотрит в кучку, а глядит врознь! Народ глуп: все в кучу лезет. По кучке, все онучки; а станешь считать, одной нет! Галичане в кучу, костромичи в кучу, ярославцы прочь, или врознь: от междоусобии Шемяки с Шуйским.
Сиб. заводе, количество уголья, выходящего в один раз из печи. Класть кучи, жечь угодье.
Сиб. последняя пора беременности. Даль вам Бог кого? Нет, еще жена в куча. Кучки мн. умалит. ниж. созвездие плеяд, утиное гнездо, бабы, стожары.
Южн. зап. еврейский праздник пасхи (см. куща). Кучный, кучевой, кучечный, к кучкам относящ. Кучный заряд портит дичь. Народ кучно стоит, густо, толпою. Кучевые облака. Кучистый, кучковатый, состоящий из куч, усеянный кучками. Кученок м. небольшая угольная куча, в которой недоспевший при первом пережиге уголь (головни) дожигается. Кучегур м. кучегуры мн. южн. песчаные бугры, сыпучие кочки, шиханы, бараканы. Кучеклад спб. угольщик. Кучить что, кучивать, сбирать, складывать, сгребать в кучи, вороха.
Кучить чем, новг. торговать по мелочи, кучить калачами, квасом.
Кучить картофель, огребать, окучивать. -ся, быть скучиваему, складываему в кучи; толпиться в кучу.
Моржи кучатся арх. вылезают юровом (стаей) на лед и сходятся.
Кому, о чем, сев. вост. просить неотступно, униженно, кланяться, умолять, конаться, домогаться, докучать (докука). Пучился, мучился, а докучился, так кинул. Кучился, мучился, а упросил, так бросил. Мучится, а никому не кучится. Вскучил волосы. Вкучился, влез в кучу. Крот выкучил землю. Докучивай картофель. Накучили много. Окучивай его. Подкучивай сбоку. Стрелки скучились. Покучься соседу. Вскучишься, как беда придет. Насилу рубля докучился. Закучился, закланялся. Накучился, накланялся. Кученье ср. действ. по глаг. на ть и на ся. Кучка ж. об. действ. по глаг. кучить и
умалит. куча. Строить кучки, у стрелков, сбегаться из рассыпного строя в кучки, при налете конницы. Кучкать что, комкать, складывать или свертывать, сминать в кучу. Кучкаться казач. толпиться, сбиваться в кучу, куриться, усаживаться тесно. Кучкаться или тул. кучать, медлить, мешкать, копаться. Что там кучаешь?
Толковый словарь русского языка. Д.Н. Ушаков
куча
Большое количество чего-н., наваленное в одном месте горкой. Куча песку. Навозну кучу разрывая, петух нашел жемчужное зерно. Крылов. Царь однажды воинам своим велел снести земли по горсти в кучу. Пушкин. Куча листьев.
Беспорядочное нагромождение, груда разных предметов. В углу была свалена в кучу всякая рухлядь. Из горевшего дома выносили пожитки и клали в одну кучу.
перен. Большое количество, много (разг. фам.). У них куча детей. Получить целую кучу неприятностей. Народу собралось - куча! Валить всё в одну кучу (разг.) - перен. без разбора, огульно, смешивать в одно различные явления. Куча мала! - восклицание, употр. в детской игре, когда устраивается общая свалка.
Толковый словарь русского языка. С.И.Ожегов, Н.Ю.Шведова.
куча
Скопление чего-н. сыпучего. К. песку. Сгрести сухие листья в кучу.
чего. Нагромождение чего-н., множество кого-чего-н. К. книг. К. дел. К. денег (очень много). Толпа валит кучей. * Куча мала! - возглас в детской игре, по к-рому начинается общая свалка.
уменьш. кучка, -и, ж. (к 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МД вместе с кучей барахла, автокраном и УАЗиком.
Из этих небольших примеров видно, что сотрудники государственной полиции в Праге валили в одну кучу социал-демократов и националистов, бомбы, баллоны, рецепты и рескрипты, правящего монарха и изобретателя Эдисона, анархистов и аграрников и т.
Ее агротехнические методы год от года совершенствовались, количество мешков с лусавендрой, отправляемых на рынок в Мазадону, неуклонно возрастало, все выше становились кучи блестящих рисовых зерен в ее закромах.
Пиздвилльской долины говорят ты отплываешь на неспешном корабле в Китай строго из-за кучи денег и азотистой кинопехоты.
Когда отец Дадуса закончил сортировать рыбу, у него получилось три кучи : большая рыба предназначалась для продажи на рынке, немного оставили себе на жареху, а всевозможную мелочь Дадус и Айван должны были раздать толпившейся вокруг детворе.
Девица, лица которой за кучей съестных припасов я рассмотреть не мог, хотя ее запах и показался мне странно знакомым, не дойдя пару ступенек до старцев, уже жадно протянувших руки к еде, аккуратненько поставила ногу точно в пустоту, мимо верхней ступени.
При Лаврентии Павловиче тоже придерживались такой системы - если ты прячешь куда-то алмазик, то лучше в кучу стекол такого же размера.
Единственный намек на беспорядок виднелся на небольшой площадке перед Первым Аляскинским банком ПАП, где на козлах среди кучи инструментов и пивных бутылок лежали две недоделанные фигуры из пенополистирола.
Нет, он только будет выкрикивать бессмысленное слово и под его защитою станет сваливать в одну кучу все разнообразие аспирации человеческой мысли.
И действительно, начал Бадмаев с рассказов о своих успехах в лечении, назвал кучу пациентов с громкими именами, а затем потихонечку сполз к большой политике.
Помимо них, - проворчал Бадья, - вокруг отирается еще куча всякого дерьма.
Тогда Барбуда дождался, пока придет его очередь убирать Веселый Домик, епархию кума, выбрал момент, когда тот отвлекся, и навалил ему кучу в верхний ящик стола.
Рандомизированная куча (randomized heap) — это куча, которая за счёт применения генератора случайных чисел позволяет выполнять все необходимые операции за логарифмическое ожидаемое время.
Кучей называется бинарное дерево, для любой вершины которого справедливо, что значение в этой вершине меньше либо равно значений во всех её потомках (это куча для минимума; разумеется, симметрично можно определить кучу для максимума). Таким образом, в корне кучи всегда находится минимум.
Стандартный набор операций, определяемый для куч, следующий:
- Добавление элемента
- Нахождение минимума
- Извлечение минимума (удаление его из дерева и возврат его значения)
- Слияние двух куч (возвращается куча, содержащая элементы обеих куч; дубликаты не удаляются)
- Удаление произвольного элемента (при известной позиции в дереве)
Рандомизированная куча позволяет выполнять все эти операции за ожидаемое время при очень простой реализации.
Структура данных
Сразу опишем структуру данных, описывающую бинарную кучу:
struct tree { T value; tree * l, * r; } ; В вершине дерева хранится значение некоторого типа , для которого определён оператор сравнения (). Кроме того, хранятся указатели на левого и правого сыновей (которые равны 0, если соответствующий сын отсутствует).Выполнение операций
Нетрудно понять, что все операции над кучей сводятся к одной операции: слиянию двух куч в одну. Действительно, добавление элемента в кучу равносильно слиянию этой кучи с кучей, состоящей из единственного добавляемого элемента. Нахождение минимума вообще не требует никаких действий — минимумом просто является корень кучи. Извлечение минимума эквивалентно тому, что куча заменяется результатом слияния левого и правого поддерева корня. Наконец, удаление произвольного элемента аналогично удалению минимума: всё поддерево с корнем в этой вершине заменяется результатом слияния двух поддеревьев-сыновей этой вершины.
Итак, нам фактически надо реализовать только операцию слияния двух куч, все остальные операции тривиально сводятся к этой операции.
Пусть даны две кучи и , требуется вернуть их объединение. Понятно, что в корне каждой из этих куч находятся их минимумы, поэтому в корне результирующей кучи будет находиться минимум из этих двух значений. Итак, мы сравниваем, в корне какой из куч находится меньшее значение, его помещаем в корень результата, а теперь мы должны объединить сыновей выбранной вершины с оставшейся кучей. Если мы по какому-то признаку выберем одного из двух сыновей, то тогда нам надо будет просто объединить поддерево в корне с этим сыном с кучей. Таким образом, мы снова пришли к операции слияния. Рано или поздно этот процесс остановится (на это понадобится, понятно, не более чем сумма высот куч).
Таким образом, чтобы достичь логарифмической асимптотики в среднем, нам надо указать способ выбора одного из двух сыновей с тем, чтобы в среднем длина проходимого пути получалась бы порядка логарифма от количества элементов в куче. Нетрудно догадаться, что производить этот выбор мы будем случайно , таким образом, реализация операции слияния получается такой:
Tree * merge (tree * t1, tree * t2) { if (! t1 || ! t2) return t1 ? t1 : t2; if (t2- > value < t1- > value) swap (t1, t2) ; if (rand () & 1 ) swap (t1- > l, t1- > r) ; t1- > l = merge (t1- > l, t2) ; return t1; }
Здесь сначала проверяется, если хотя бы одна из куч пуста, то никаких действий по слиянию производить не надо. Иначе, мы делаем, чтобы куча была кучей с меньшим значением в корне (для чего обмениваем и , если надо). Наконец, мы считаем, что вторую кучу будем сливать с левым сыном корня кучи , поэтому мы случайным образом обмениваем левого и правого сыновей, а затем выполняем слияние левого сына и второй кучи.
Асимптотика
Введём случайную величину , обозначающую длину случайного пути от корня до листа (длина в числе рёбер). Понятно, что алгоритм выполняется за операций. Поэтому для исследования асимптотики алгоритма надо исследовать случайную величину .
Математическое ожидание
Утверждается, что математическое ожидание оценивается сверху логарифмом от числа вершин в этой куче:
Доказывается это легко по индукции. Пусть и — соответственно левое и правое поддеревья корня кучи , а и — количества вершин в них (понятно, что ).
Тогда справедливо.
Чего-либо, обычно сыпучего, мелкого, наваленного, насыпанного в одном местечего-либо.
- Куча песка.
- Его одежда валялась на полу бесформенной кучей .
- Не представляю, как люди жили в коммуналках в одной куче , дети, однако же, были, и много детей, все делали в спешке, где уж тут до взаимной психотерапии, подготовки, ласк, слов.
- Эта шуба кучу денег стоит!
- Моего друга зовут Куча .
- Мою подругу зовут Куча .
Синонимы к слову куча
- груда
- масса
- скопище
- толпа
Гиперонимы к слову куча
Однокоренные слова для куча
Прилагательные
- кучный
Умласк
- кучка
Фразеологизмы для слова куча
- куча мала
Представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков .
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется 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;
