Макс Heapify Алгоритм

Question

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

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

Одним из моих упражнений является Иллюстрируйте шаги Heapsort, заполнив массивы и представления дерева

Answer 1

Существует много реализаций структуры данных кучи, но речь идет об определенной c неявной двоичной куче . Сортировка кучи выполняется на месте, поэтому она использует этот дизайн. Для двоичных кучи требуется двоичное дерево , поэтому оно может быть представлено в виде неявной структуры, построенной из массива: для каждого 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], неявно представлен гомоморфизмом, используя приведенные выше правила, как,

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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