Когда я захочу использовать кучу?

92

Помимо очевидного ответа Priority Queue, когда будет полезна куча в моих приключениях по программированию?

Митракс
источник
8
Здесь есть много хороших ответов, поэтому я подскажу, «когда куча недостаточно велика».
Дон Верве,

Ответы:

121

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

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

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

Куча - это дерево, в котором значение родительского узла больше, чем у любого из его дочерних узлов.

Если вы думаете о куче как о двоичном дереве, хранящемся в линейном порядке по глубине, сначала корневой узел (затем потомки этого узла, затем потомки этих узлов); тогда дочерние элементы узла с индексом N находятся в 2N + 1 и 2N + 2. Это свойство обеспечивает быстрый доступ по индексу. А поскольку кучи управляются путем перестановки узлов, это позволяет выполнять сортировку на месте.

Джо Коберг
источник
3
Обратите внимание, что это может быть удобная гарантированная сортировка NlogN, которая не требует дополнительных выделений массива
Overflown
38
Также здорово знать кучу вопросов для интервью;)
vivekian2
21
@ vivekian2 Я здесь только потому, что у меня сейчас интервью.
byxor
почему бы не использовать класс стека со вспомогательным стеком для отслеживания самого большого (или самого маленького) элемента. извлечение - O (1)
Ридхваан Шакил
@RidhwaanShakeel Если вы используете стек, ваш элемент всегда будет помещен на голову, что, если положение элемента необходимо определять на основе некоторого свойства элемента, такого как самое большое событие (на основе количества людей, участвовавших в событии).
SandeepGodara
49

Кучи - это структуры, предназначенные для быстрого доступа к минимальному или максимальному значению .

Но зачем вам это нужно? Вы можете просто проверять каждую запись при добавлении, чтобы узнать, самая маленькая она или самая большая. Таким образом, у вас всегда будет самое маленькое или самое большое за постоянное время O(1).

Ответ заключается в том, что кучи позволяют вытащить самое маленькое или самое большое и быстро узнать СЛЕДУЮЩИЙ самый маленький или самый большой . Вот почему это называется приоритетной очередью.

Пример реального мира (хотя и не очень справедливого):

Предположим, у вас есть больница, в которую принимают пациентов в зависимости от их возраста. Самый старший всегда идет первым, независимо от того, когда он / она встал в очередь.

Вы не можете просто отслеживать самого старшего, потому что, если вы вытащите его / ее, вы не узнаете следующего по возрасту. Чтобы решить эту больничную проблему, вы реализуете максимальную кучу . Эта куча по определению частично упорядочена. Это означает, что вы не можете отсортировать пациентов по их возрасту, но вы знаете, что самые старые всегда находятся наверху, поэтому вы можете вывести пациента за постоянное время O(1)и повторно сбалансировать кучу во времени журнала O(log N).

Более сложный пример:

Предположим, у вас есть последовательность целых чисел, и вы хотите отслеживать median. Медиана - это число в середине упорядоченного массива.

Пример:

[1, 2, 5, 7, 23, 27, 31]

В приведенном выше случае 7- это медиана, поскольку массив, содержащий меньшие числа, [1, 2, 5]имеет тот же размер, что и массив, содержащий большие числа [23, 27, 31]. Обычно, если в массиве нечетное количество элементов, медиана - это среднее арифметическое двух элементов в середине, например (5 + 7)/2.

А как теперь отслеживать медианное значение? Имея 2 кучи , одна минимальная куча, содержащая числа, меньшие, чем текущая медиана, и максимальная куча, содержащая числа, большие, чем текущая медиана. Теперь, если эти кучи всегда сбалансированы, 2 кучи будут содержать одинаковое количество элементов или в одной будет на 1 элемент больше, чем в другой, больше всего.

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

Андре Пена
источник
6
Более сложный пример потрясающий! Я определенно собираюсь попробовать это когда-нибудь. Однако я думаю, что в вашем примере есть небольшая ошибка. Поскольку нам нужно получить медиану, усредняя два элемента в середине. Я бы предположил, что нам нужно использовать минимальную кучу для хранения чисел, больших, чем текущая медиана, и максимальную кучу, чтобы хранить числа, меньшие, чем текущая медиана. Таким образом, мы можем извлечь два элемента посередине за постоянное время и вычислить медиану? Я прав?
Calvin Ku
12

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

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

АтикусФинч
источник
3

Также подходит для алгоритмов выбора (поиск минимума или максимума)

Дэн
источник
3

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

Хавьер
источник
0

Вы можете использовать minHeap или maxHeap, если хотите получить доступ к самым маленьким и самым большим элементам соответственно.

Квадроцикл
источник