Максимальный алгоритм Heapify

Я немного смущен. Если у меня есть массив, я должен построить дерево. Чтобы сравнить дочерние элементы, мне нужно знать, насколько велик мой массив, в данном случае его N = 6, поэтому я должен разделить его на 2, чтобы получить 3. Это означает, что я должен начать с индекса 3, чтобы сравнить с родительским узлом. Если дочерний узел больше, чем родительский узел, я должен поменять его местами, иначе мне не нужно. Затем я перехожу к индексу 2 и сравниваю с родительским, если дочерний узел больше, чем родительский узел, тогда я должен поменять его местами. Затем индекс 1 я должен сравнить с дочерними элементами и при необходимости поменять местами. Поэтому я создал кучу Max. Но знайте, я не понимаю, почему я должен обменивать A1 с A[6], затем A1 с A[5]. Наконец, я не получаю максимальную кучу, я получаю минимальную кучу? Что означает Heapify?

Большое спасибо, я ценю каждый ответ!

Одно из моих упражнений — Проиллюстрировать этапы Heapsort, заполнив массивы и представления дерева.

введите здесь описание изображения


algorithm heap heapsort
person Sayuri    schedule 08.01.2020    source источник
comment
Итак, когда я делаю Max или Min Heapify, мне нужно поменять местами первый и последний узел, а затем на каждой итерации я должен сравнивать A[i] с другими узлами, пока не достигну A[i-1]?   -  person Sayuri    schedule 08.01.2020
comment
После замены A[1] и A[6] -> почему я могу просто сравнить левую часть 1 и 4 и поменять местами ее, но не 3 и 7? Также случай, а также после обмена A[1] на A[5], почему я могу поменять местами только 4 и 2, но не 3 и 7?   -  person Sayuri    schedule 08.01.2020

Ответы (2)


arrow_upward
2
arrow_downward

Существует много реализаций структуры данных кучи, но одна из них говорит о конкретной неявной двоичной куче. сортировка кучей выполняется на месте, поэтому используется такой дизайн. Двоичные кучи требуют конкурирующего двоичного дерева, поэтому его можно представить в виде построенной неявной структуры. из массива: для каждого A[n] в массиве с отсчетом от нуля

  • A[0] — корень; если n != 0, A[floor((n-1)/2)] является родителем;
  • если 2n+1 находится в диапазоне массива, то A[2n+1] является левым дочерним элементом, иначе это конечный узел;
  • если 2n+2 находится в диапазоне массива, то A[2n+2] является правильным дочерним элементом.

Скажем, массив [10,14,19,21,23,31] неявно представлен гомоморфизмом с использованием приведенных выше правил, например,

Правила применяются к [10,14,19,21,23,31].

Это не соответствует инвариантам максимальной кучи, поэтому нужно heapify, вероятно, используя конструкцию кучи Флойда., который использует sift down и работает в O(n). Теперь у вас есть куча и отсортированный массив без длины, ([31,23,19,21,14,10],[]) (все это неявно, поскольку куча не занимает дополнительной памяти, это просто массив в памяти). Визуализация кучи на этом этапе,

Куча [31,23,19,21,14,10].

Мы удаляем максимальный элемент кучи и используем sift up для восстановления формы кучи. Теперь куча стала на единицу меньше, и мы взяли максимальный элемент и сохранили его без смещения в наш массив ([23,21,19,10,14],[31]),

Куча [23,21,19,10,14].

повтор, ([21,14,19,10],[23,31]),

Куча [21,14,19,10].

([19,14,10],[21,23,31]),

Куча [19,14,10].

([14,10],[19,21,23,31]),

Куча [14,10]

([10],[14,19,21,23,31]),

Куча [10].

Размер кучи равен единице, поэтому окончательный отсортированный массив равен [10,14,19,21,23,31]. Если использовать мини-кучу и тот же алгоритм, то массив будет отсортирован по-другому.

person Neil    schedule 08.01.2020
comment
Спасибо Нил за объяснение! - person Sayuri; 09.01.2020

arrow_upward
2
arrow_downward

Кучевая сортировка — это двухэтапный процесс. На первом этапе вы превращаете массив в кучу с максимальным значением наверху A[1]. Это первый переход, обведенный красным. После этой фазы куча находится в массиве с индексами от 1 до 6, а самое большое значение находится в индексе 1 в A[1].

На втором этапе мы сортируем значения. Это многоэтапный процесс, в котором мы извлекаем наибольшее значение из кучи и помещаем его на место в отсортированном массиве.

Куча находится на левой стороне массива и будет сжиматься влево. Отсортированный массив находится справа от массива и растет слева.

На каждом шаге мы меняем верхнюю часть кучи A[1], содержащую наибольшее значение кучи, на последнее значение кучи. Затем отсортированный массив увеличился на одну позицию влево. Поскольку значение, которое было помещено в A[1], не самое большое, мы должны восстановить кучу. Эта операция называется max-heapify. После этого процесса A[1] содержит самое большое значение в куче, размер которой был уменьшен на один элемент.

Повторно извлекая самое большое значение, оставшееся в куче, мы можем отсортировать значения в массиве.

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

person chmike    schedule 08.01.2020
comment
Спасибо chmike за объяснение. Я понимаю это лучше. - person Sayuri; 09.01.2020