порядок кучи в питоне

Question

Новая структура данных кучи.

Попытка создать кучу из списка.

li = [5, 7, 9, 1, 3]

heapq.heapify(li)

После кучи вывод будет

[1, 3, 9, 7, 5]

Почему этот порядок?
Я думал, что для кучи с минимальным приоритетом элементы должны быть упорядочены от минимальной до максимальнойто есть
heapq.heapify(li) должно совпадать с li.sort()

Может ли кто-нибудь помочь мне понять?

Answer 1

Кучи

на самом деле сортируются не так, как списки.Python не имеет уникальной структуры данных кучи и использует списки с операциями кучи, что, вероятно, является источником некоторых из вас путаницы.Отсортированная куча (с минимальным приоритетом) - это та, которая удовлетворяет «условию кучи», так что любой дочерний узел больше, чем его родительский узел.Это не означает, что сглаженное представление будет в следующем порядке.

Ваш пример будет выглядеть до сглаживания следующим образом:

    1
   / \
  3   9
 / \
7   5

Каждый узел получает до 2 дочерних элементов, и дочерние элементы всегда добавляютсяслева направо, пока строка не заполнится.Плоское представление затем создается путем объединения строк: [1] + [3, 9] + [7, 5]

Answer 2

на самом деле сортировка кучи - это полуорганизованный алгоритм.Основная идея заключается в том, что каждый родитель должен быть меньше или равен своим потомкам (в сортировке min heap).поэтому мы знаем, что первый элемент самый маленький.когда мы выталкиваем первый элемент кучи, следующий наименьший элемент займет его место.Для получения дополнительной информации смотрите эти ссылки:

сортировка кучи википедии

Answer 3

Проще взглянуть на кучу как на дерево:

         1
     3      9
  7     5

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

Полное дерево допускает простое встраивание в массив путем нумерации узлов в порядке ширины, начиная с корня как узла 1.

         1(1)
     3(2)      9(3)
  7(4)     5(5)

При такомвстраивание, имеют место следующие соотношения:

1. li[i] <= li[2*i]
2. li[i] <= li[2*i + 1]

2*i и 2*i + 1 - формулы для вычислениялевый и правый дочерний, соответственно, узла в позиции i:

 +--+--+
 |  v  v
[1, 3, 9, 7, 5]
    |     ^  ^
    +-----+--+

(Вы можете указать эти свойства для массива на основе 0, но проще думать с массивами на основе 1.)

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