Odświeżanie algorytmu. Dlaczego heapsort jest algorytmem insortującym?

Nie rozumiem, dlaczego heapsort jest uważany za algorytm sortowania w miejscu .

Mam na myśli dodatkową strukturę danych zapełnioną elementami tablicy do sortowania, tj. Stertę, która jest używana do pomocy w wydobyciu wartości minimalnej i procesie sortowania.

Może więc nie rozumiem tutaj definicji miejsca na miejscu?

Ale na przykład rodzaj wstawiania jest oczywisty, że jest to algorytm zastępczy, tj. Nie jest wymagana dodatkowa pamięć dla elementów.

Więc dlaczego uważa się to za miejsce?

Mam na myśli dodatkową strukturę danych zapełnioną elementami tablicy do sortowania, tj. Stertę, która jest używana do pomocy w wydobyciu wartości minimalnej i procesie sortowania.

Nie. Tablica jest przekształcana, aby była zgodna z ograniczeniem sterty bez użycia dodatkowej pamięci większej niż O (1). (W rzeczywistości wszystko, czego potrzebujesz, to dodatkowa pamięć wystarczająca do przechowywania jednego elementu tablicy do celów wymiany, a także wartość logiczna lub dwa oraz zmienna pętli lub dwa).

Ok, technicznie rzecz biorąc może się zdarzyć, że heapsort jest zwykle wyjaśniany jako użycie osobnej hałdy, ale można go zaimplementować na miejscu.

Być może brakuje ci podstawowego zrozumienia, że ​​do określenia układu drzewa można użyć tablicy.

Załóżmy, że masz drzewo binarne, a węzeł wewnętrzny znajduje się w indeksie i tablicy. Następnie indeks tablicy rodzica i potomków tego węzła można znaleźć:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Widzieć:

http://www.personal.kent.edu/~rmuhamma/Alameterms/MyAlgorithms/Sorting/heapSort.htm

Ponieważ stertę można przechowywać i organizować w całości w tablicy, heapsort może działać w miejscu, przesuwając elementy wewnątrz tablicy wejściowej. Rzeczywiście, sterta jest budowana i przetwarzana przy użyciu oryginalnej tablicy wejściowej.

Jeśli, jak mówisz, naprawdę potrzebna jest dodatkowa struktura do zbudowania sterty, wówczas heapsort rzeczywiście NIE byłby algorytmem sortowania w miejscu.

Tak jednak nie jest. Możesz zbudować stertę na tej samej tablicy, którą chcesz posortować, a następnie zastosować algorytm heapsort, aby sortować na miejscu.

W informatyce algorytm lokalny (lub łaciński in situ) to algorytm, który przekształca dane wejściowe przy użyciu struktury danych z małą, stałą ilością dodatkowej przestrzeni dyskowej. Dane wejściowe są zwykle nadpisywane przez dane wyjściowe podczas wykonywania algorytmu. Algorytm, który nie jest na miejscu, jest czasem nazywany „nie na miejscu” lub „na miejscu”.

Wikipedia - algorytm lokalny

Uważa się, że jest na miejscu, ponieważ jego wymagania dotyczące miejsca są znikome (stałe lub wcale, jeśli używasz operacji bitowych do zamiany przedmiotów). Na przykład MergeSort nie istnieje, ponieważ zestaw danych wejściowych nie jest modyfikowany w każdej iteracji przykładu wyszukiwania.

Najlepszym sposobem zilustrowania różnic między algorytmami lokalnymi i algorytmami zewnętrznymi jest prawdopodobnie sprawdzenie następującego kodu odwracającego łańcuch C / C ++, który to robi (z K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Jeśli na przykład odczytujesz łańcuch wejściowy od końca i umieszczasz znaki w innym buforze, byłby to algorytm odwracania łańcucha na nie na miejscu.