Сортировка кучи на месте состоит из двух этапов:
- Создание кучи из произвольного массива.
- Изменение порядка результирующего массива так, чтобы он сортировался.
Вы можете сделать первый шаг за время O (n), используя алгоритм makeHeap.Я показываю основную идею ниже.Предположим, что массив a имеет длину n.
for i = (n-1)/2 downto 0
bubbleDown(i);
Обратите внимание, что вы начинаете с середины и возвращаетесь к началу массива.Позвольте мне привести пример того, как это работает.Скажем, вам дан массив [1,5,3,4,6,7,2].Представленный в виде двоичной кучи, он становится:
1
5 3
4 6 7 2
(n-1)/2 равен 3, поэтому мы начнем со значения 4 в куче.Это не может двигаться, поэтому мы переходим к значению 3.Мы строим максимальную кучу, поэтому мы проверяем двух дочерних элементов, чтобы узнать, больше ли один из них. Если это так, мы поменяемся местами с самым большим из двух дочерних элементов.Это дает:
1
5 7
4 6 3 2
Переходя назад к значению 5, мы видим, что 6 больше, и поэтому мы меняем эти два элемента:
1
6 7
4 5 3 2
И, наконец,корневой элемент.7 больше, чем дети, поэтому мы поменяемся местами:
7
6 1
4 5 3 2
И, поскольку мы еще не достигли уровня листьев, мы снова проверяем и меняем местами 1 с 3:
7
6 3
4 5 1 2
И там у вас есть допустимая максимальная куча.Этот алгоритм всегда работает.
Обратите внимание, что ваша идея начать с корня и работать вниз не всегда приведет к правильной куче.Возьмите начальную позицию, которую я дал ранее:
1
5 3
4 6 7 2
Если я начну с вершины и поднимусь вниз, то мы поменяемся местами 1 и 5, а затем поменяем 5 и 6,давая:
6
5 3
4 1 7 2
Мы смотрим на 5, и это не должно быть пузырьком вниз.Затем мы смотрим на 3 и меняем местами 7, в результате чего:
6
5 7
4 1 3 2
И все готово, потому что уровень листьев не может быть увеличен.И в итоге получается дерево, которое не является допустимой кучей.
Итак, makeHeap для построения кучи.
Шаг 2: сортировка.
Сортировка массивакак только вы создали кучу, это довольно легко.Базовый алгоритм:
while n > 0
swap(a[0], a[n-1]) // puts the largest item at the end of the heap
n = n - 1 // decrease remaining count
bubbleDown(0) // adjust the heap
Это всего лишь небольшое изменение стандартной функции removeLargest из любой реализации max heap.Вместо того, чтобы удалять и возвращать корневой элемент, вы заменяете его последним элементом в куче.
Давайте посмотрим, как это работает.Учитывая начальную кучу:
7
6 3
4 5 1 2
Поменяйте местами 7 на 2, уменьшите счет и уменьшите число:
6
5 3
4 2 1 7
Поменяйте местами 6 на 1, уменьшите счет и уменьшите число:
5
4 3
1 2 6 7
Поменяйте местами 5 с 2, уменьшите счет и уменьшите число:
4
2 3
1 5 6 7
Поменяйте местами 4 с 1, уменьшите счет и уменьшите число:
3
2 1
4 5 6 7
... И я на этом остановлюсь, потому что я думаю, что вы поняли идею.
Это действительно так просто.Если у вас есть реализация max heap с методами insert и removeLargest и стандартными вспомогательными методами siftUp и bubbleDown (или как вы их называете), то добавление метода сортировки - это вопрос создания этих двух маленькихфункции, которые вызывают вспомогательные методы.
Рекомендуется heapSort метод:
public static void heapSort(Comparable[] a, int size)
{
MaxHeapPriorityQueue elementData = new MaxHeapPriorityQueue();
// PriorityQueue<Comparable> pq = new PriorityQueue();
for (int i = (size-1)/2; i >= 0; i--) //down to 0
{
bubbleDown(i);
}
while(size > 0)
{
swap(elementData, size, 0); // puts the largest item at the end of the heap
size = size - 1; // decrease remaining count
bubbleDown(0); // adjust the heap
}
// The array is sorted.
}