Sortowanie tablic z użyciem struktur danych – implementacja kopca binarnego

Założenie: Zrozumieć i zaimplementować algorytm sortowania za pomocą kopca binarnego w PHP.

Krok po kroku:

1. Tworzenie klasy Kopiec: Zdefiniujmy klasę reprezentującą kopiec binarny. Klasa będzie zawierała tablicę przechowującą elementy kopca oraz metody do zarządzania kopcem.

kopiec[] = $element;
        $this->przesiejWGore(count($this->kopiec) - 1);
    }

    private function przesiejWGore($index) {
        // ... (implementacja przesiewania w górę) ...
    }

    // ... (inne metody: usun, przesiejWDol, sortuj) ...
}
?>
				

2. Implementacja metody `przesiejWGore`: Ta metoda zapewnia, że po dodaniu elementu kopiec zachowuje swoją strukturę.

    private function przesiejWGore($index) {
        $rodzic = floor(($index - 1) / 2);
        while ($index > 0 && $this->kopiec[$index] > $this->kopiec[$rodzic]) {
            [$this->kopiec[$index], $this->kopiec[$rodzic]] = [$this->kopiec[$rodzic], $this->kopiec[$index]];
            $index = $rodzic;
            $rodzic = floor(($index - 1) / 2);
        }
    }
				

3. Implementacja metody `sortuj`: Metoda ta wykorzystuje kopiec do posortowania tablicy.

    public function sortuj() {
        for ($i = count($this->kopiec) - 1; $i > 0; $i--) {
            [$this->kopiec[0], $this->kopiec[$i]] = [$this->kopiec[$i], $this->kopiec[0]];
            $this->przesiejWDol(0, $i);
        }
    }

    private function przesiejWDol($index, $max) {
        // ... (implementacja przesiewania w dół) ...
    }
}
?>
				

4. Użycie klasy Kopiec: Utwórzmy instancję klasy i przetestujmy sortowanie.

dodaj($element);
}
$kopiec->sortuj();
print_r($kopiec->getKopiec()); // Wyświetli posortowaną tablicę
?>
				

Pamiętaj, że powyższy kod to uproszczona wersja. Pełna implementacja wymaga dodania brakujących metod (np. `przesiejWDol`, `getKopiec`).

Ten przykład pokazuje podstawy implementacji kopca binarnego i jego zastosowania do sortowania. Zachęcamy do dalszego zgłębiania tematu i eksperymentowania z różnymi algorytmami sortowania!