Реализация пирамидальной сортировки с использованием минимальной кучи (тройной кучи) — отзывы о корректности и оптимизац ⇐ JAVA

[Anonymous]

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

В нашем курсе мы обсуждали двоичную кучу. Аналогично можно реализовать троичную кучу
, где каждый узел имеет до трех потомков. Дочерние
узла в позиции i расположены в позициях 3i +
1, 3i + 2 и 3*i + 3 в массиве. Задача состоит в том, чтобы реализовать
куричную сортировку с использованием такой троичной кучи, гарантируя, что алгоритм работает
на месте.
Реализовать пирамидальную сортировку с использованием троичной кучи. Ваш алгоритм должен работать
на месте. Вам следует расширить класс HeapTernary из Moodle.
Основной метод изменять не следует, но можно добавить вспомогательные методы.
Каково наихудшее время выполнения вашего алгоритма в O-нотации?
Обоснование ваш ответ.

Мое решение:
Вот моя реализация кода:
< pre class="lang-java Prettyprint-override">

Код: Выделить всё

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

class HeapTernary {

public static void main(String[] args) {
Random random = new Random(42);
int[] a = new int[17];
for (int i = 0; i < a.length; ++i) {
a[i] = random.nextInt(100);
}
System.out.println(Arrays.toString(a));

heapsort(a);

System.out.println(Arrays.toString(a));
}

public static void heapsort(int[] a) {

for (int i = 0; i < a.length; i++) {
for (int j = i * 3 + 1; j < i * 3 + 4; j++) {
if (j < a.length) {
if (a[j] < a[i]) {
switchPos(a, i, j);
heapsort(a);
}
}
}
}
}

private static void switchPos(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

Я перебрал весь массив, сравнивая каждый узел с его дочерними элементами. Если дочерний узел был меньше родительского, я выполнял замену, чтобы поменять их местами. После замены я использовал рекурсию, чтобы проверить, был ли новый родительский узел меньше, чем его обновленный родительский узел. Эта рекурсивная проверка гарантирует, что свойство min-heap сохраняется во всей структуре кучи.

Подробнее здесь: https://stackoverflow.com/questions/790 ... correctnes