Минимальная куча отсортирована по умолчанию

Я только что выбрал "Введение в алгоритмы", и я начал реализовывать алгоритмы куч и сортировки в C#.

Реализуя функцию, которая создает мин / макс кучу из массива значений типа double, я заметил, что у построенной кучи есть некоторые интересные свойства.

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

Является ли это свойством minheap, или я просто не могу получить дело, к которому это свойство не относится. Макс Хип не работает таким образом, по крайней мере, что я получаю здесь.

Выход:

2345 7 34 6 3 5 4 5 1 2 3 2 1 3 1 3 2 1 (maxheap)

1 1 1 1 2 2 2 3 3 3 3 4 5 5 6 7 34 2345 (minheap)

Спасибо за любые ответы заранее!

Источник

2 ответа

Решение

Кучи имеют отношение только между родительским узлом и их соответствующими дочерними узлами. Нет связи между узлами на одном уровне. 

For Min Heaps: Value of Parent node <= Value of its child nodes
For Max Heaps: Value of Parent node >= Value of its child nodes

Поэтому нет необходимости сортировать Min Heap при перемещении сверху вниз, слева направо. Это просто совпадение в вашем случае.
Например: рассмотрим эту последовательность: 1, 3, 2, 5, 4, 10, 9 Куча для вышеуказанной последовательности
Они в порядке MinHeapify, но явно не в отсортированном порядке.
Посетите эту интерактивную ссылку кучи или эту ссылку для правильной визуализации построения кучи.

Источник

Чтобы сделать реализацию кучи более надежной, люди обычно вызывают две операции, которые вы можете выполнить для узла: sift а также percolate

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

возможна реализация sift процедура

 public void sift (int i)
    {
        while (i != 0)
        {
            if (compare(heapData[i], parentValue(i)))
            {
                switchValuesAtIndexes(parentIndex(i), i);
                i = parentIndex(i);
            }
            else
                break;
        }
    }

percolate приносит узел как можно выше на дереве, переключая узел с родителем.

public void percolate (int i)
    {
        while (true)
        {
            if (indexExists(leftIndex(i)) && (!indexExists(rightIndex(i)) && compare(leftValue(i), heapData[i]) || indexExists(rightIndex(i)) && compare(leftValue(i), rightValue(i)) && compare (leftValue (i), heapData[i])))
            {
                switchValuesAtIndexes(leftIndex(i), i);
                i = leftIndex(i);
            }
            else
                if (indexExists(rightIndex(i)) && (compare (rightValue(i), leftValue(i)) && compare (rightValue(i), heapData[i])))
                {
                    switchValuesAtIndexes(rightIndex(i), i);
                    i = rightIndex(i);
                }
            else
                break;
        }
    }

Чтобы построить кучу, вам нужно будет применить sift или же percolate (или оба) для каждого элемента массива

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

Источник
Другие вопросы по тегам