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

Question

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Пример реального мира (хотя и не очень честный):

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

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

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

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

* 1 028 * Пример:

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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