есть ли проблемы с этим алгоритмом?

Question

У меня проблема с этим алгоритмом для сортировки кучи

Heap_Sort(A)
  Build_Heap(A)
  for i<--n down to 2
    swap (A[1],A[n])
    n<--n-1
    MaxHeapify(A,1)

Я думаю, что вместо этого алгоритма мы должны написать:

Heap_Sort(A)
  Build_Heap(A)
  for i<-- n down to 1
    Delete_Max(A)

Answer 1

Если вы делаете сортировку на месте ...

Heap_Sort(A)
    B = Build_Heap(A)    # Assuming maxheap

    for i -> A.length to 0:
        Remove top value from B (which is basically just A, but treated differently),
        assuming the heap is modified to maintain partial ordering during this part
        (as well as decreasing the noted size of the heap by 1) and add the removed
        value to position A[i].

В основном ваш алгоритм.Если вы не выполняете сортировку на месте, вы можете просто использовать minheap и вставить все значения в новый массив.

Answer 2

Если вы переместите элемент max в конец массива кучи, а затем удалите его, вы не останетесь ни с чем в вашем массиве после завершения.Таким образом, ваш алгоритм, который удаляет максимум, не приведет к сортировке массива ваших исходных элементов.

Обновление на основе редактирования OP:

Вы можетеделай такПервый способ, тем не менее, позволяет сортировать на месте.Ваш метод требует O (N) дополнительного хранилища.

Другое Правка:

Трудно точно понять, какие предположения вы делаете на первом алгоритме, но, как яПодумайте о комментарии, который я сделал ниже, похоже, что MaxHeapify(A,1) должно быть MaxHeapify(A, n).Обычно вы передаете массив и его размер, или, в этом случае, количество элементов, которые вы хотите упорядочить в виде кучи.Это может быть спорным, если вы предполагаете, что n является глобальной переменной.