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

Ответ 1

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

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

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

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

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

Ответ 2

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

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

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

Пример реального мира (не очень справедливый мир):

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

Вы не можете просто следить за самым старым, потому что, если вы вытащите его, вы не знаете следующий самый старый. Чтобы решить эту проблему больницы, вы реализуете максимальную кучу. Эта куча, по определению, частично упорядочена. Это означает, что вы не можете сортировать пациентов по их возрасту, но вы знаете, что самые старые из них всегда находятся в верхней части, поэтому вы можете вытащить пациента в постоянное время 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 элемент больше, чем другой), вы тянете элемент из самой большой кучи и добавьте к самому маленькому. Теперь они сбалансированы.

Ответ 3

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

Еще одна полезная характеристика кучи заключается в том, что ее можно создать на месте из массива!

Ответ 4

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

Ответ 5

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

Ответ 6

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