Алгоритм HeapSort Индексируется от 1 до n, а фактический код должен быть от 0 до n-1.

Я новичок в алгоритмах и хотел реализовать алгоритм сортировки кучи. Алгоритм дается следующим образом:

Родитель(i) возвращает Math.floor(i/2)

Влево (i) вернуть 2i

Правильно (i) вернуть 2i+1

Затем есть метод HEAPIFY, который восстанавливает свойство heep. Алгоритм следующий:

HEAPIFY(A, i)
 l = Left(i)
 r = Right(i)
 if (l <= heap-size[A] and A[l] > A[i]
  then largest = l
 else largest = i
 if r <= heap-size[A] and A[r] > A[largest]
  then largest = r
 if largest != i
  then exchange A[i] <-> A[largest]
       HEAPIFY(A, largest)

Мой код, который реализует этот метод:

public static void HEAPIFY(int[] A, int i) {
    int l = LEFT(i);
    int r = RIGHT(i);
    int largest = 0;
    if (l < A.length && A[l] > A[i]) {
        largest = l;
    } else {
        largest = i;
    }

    if (r < A.length && A[r] > A[largest]) {
        largest = r;
    }

    if (largest != i) {
        int temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        HEAPIFY(A, largest);
    }
}

Теперь мой вопрос в алгоритме книги показан путем рисования дерева кучи и массива, например, массив: [16,14,10,8,7,9,3,2,4,1] и для дерева и также для массива он индексируется, начиная с 1 до n, поэтому Array[1] = 16, а в кодировании Array[0] = 16. Теперь я не могу настроить метод heapify, чтобы он начинался либо с индекса 1, либо до 1 или как-то заставьте его начинать с 0 и пусть куча будет проиндексирована от 0 до n-1.

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

Спасибо вам, ребята

Теперь HEAPIFY работает, и следующий код представляет собой код для создания кучи:

public static void BUILD_HEAP(int[] A) {
    heapSize = A.length;
    for (int i = (int) Math.floor(A.length / 2.0); i >= 0; i--) {
        HEAPIFY(A, i);
    }
}

build heap также работает, и единственный метод, который не работает, — это heapsort.

 public static void HEAPSORT(int[] A) {
    BUILD_HEAP(A);
    for (int i = A.length-1; i >= 1; i--) {
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        heapSize = heapSize-1;
        HEAPIFY(A,0);
    }
}

это должно сортироваться, но когда я пытаюсь просмотреть массив после вызова heapsort, он не дает отсортированный массив. есть идеи, как исправить пирамидальную сортировку?


java algorithm heap heapsort
person GGio    schedule 21.06.2012    source источник

Ответы (2)


arrow_upward
0
arrow_downward

если вы хотите начать с индекса 1, вы можете инициализировать массив следующим образом: [-x,16,14,10,8,7,9,3,2,4,1] -x — это массив [0] , другими словами, вы можете игнорировать элемент, который находится в массиве [0].

если вы хотите начать с индекса формы 0, вам нужно изменить функцию ВЛЕВО (i) и ВПРАВО (i).

ВЛЕВО(i) вернуть 2*i+1;

ВПРАВО(i) вернуть 2*i+2;

person liuzixing    schedule 21.06.2012

arrow_upward
1
arrow_downward

Родитель(i) возвращает Math.floor(i/2)

=> Parent(i) return Math.floor((i - 1)/2)

Влево (i) вернуть 2i

=> Влево (i) вернуть 2i + 1

Правильно (i) вернуть 2i+1

=> Верно (i) вернуть 2i + 2

Вы можете решить это, либо повозившись (что я на самом деле и сделал), либо приняв во внимание j = i - 1.

Если i' = 2 i и j = i - 1, значит, i = j + 1

j' = i' - 1 = (2i) - 1 = (2(j + 1)) - 1 = 2j + 1

person mcdowella    schedule 21.06.2012
comment
Большое спасибо, я исправил это, и теперь это работает. Если бы я хотел пройти по нему и распечатать все элементы, я бы просто прошел по массиву? - person GGio; 21.06.2012
comment
Я не проверял весь ваш код, но общая идея heapsort заключается в том, что после того, как вы вызвали HEAPSORT(A), массив A был отсортирован на месте, так что да, я ожидаю, что вы просто прочитаете массив, чтобы получить элементы в отсортированном порядке. - person mcdowella; 21.06.2012
comment
да, после вызова heapsort (A) я перебираю массив, но я получаю только некоторые из них, отсортированные не все - person GGio; 23.06.2012
comment
Насколько я вижу, опубликованный код пишет heapsize, но никогда его не читает. Идея цикла for в HEAPSORT заключается в том, что после того, как i проходит, i записей в конце массива являются i самыми большими значениями в массиве, а длина - i записей в начале массива представляет собой кучу размера length - i, из которого будет выбрано следующее наибольшее значение i. Итак, HEAPIFY хочет использовать heapSize, а не A.length. - person mcdowella; 24.06.2012