Сортировка по кучам и сортировка через минимальные кучи

#java #algorithm #heapsort

#java #алгоритм #сортировка по кучам

Вопрос:

Я знаю, как сортировать массив на месте, используя свойство heapsort и max-heap.
Но я не могу придумать, как я мог бы отсортировать его на месте, используя свойство min-heap.

Я могу отсортировать его с помощью минимальной кучи, используя временный промежуточный массив, например

 public static int[] heapSort2(int[] array){
     buildMinHeap(array);
     int [] temp = new int[array.length];
     for(int i = 0; i < array.length; i   ){
      temp[i] = extractMin(array);
      } 
   return temp;//returns array input sorted
}

Но я не могу придумать способ сделать это без использования temp. Возможно ли это, или минимальная куча предназначена только для очередей с приоритетом?

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

2. @bestsss: это сортировка по вставке

3. @user384706 Когда сортировка по кучам реализована на месте, она также выглядит так же на этапе вставки.

Ответ №1:

Сортировка на месте с использованием минимальной кучи симметрична сортировке с максимальной кучей.

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

Затем вы сортируете в порядке возрастания, используя массив min-heap, имея корень всегда в последнем элементе (индекс N), и вы выполняете один шаг сортировки, перемещая корень на место последнего листа (который является крайним левым элементом, который еще не отсортирован), создавая этот листновый корень и погружение его в кучу.

Уравнения для получения индексов родительского, левого и правого дочерних элементов в такой куче разные. В первом случае, предполагая индексы 1-> N, уравнения:

 parent(i) = floor(i / 2)
leftchild(i) = 2 * i
rightchild(i) = 2 * i   1

В последнем, обратном случае минимальной кучи, уравнения получаются путем изменения индексов на входе и выходе вышеуказанного:

 parent(i) = N   1 - floor((N   1 - i) / 2)
leftchild(i) = N   1 - (2 * (N   1 - i))
rightchild(i) = N   1 - (2 * (N   1 - i)   1)

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