Сортировка — фундаментальная операция в информатике, и существуют различные алгоритмы для эффективного выполнения этой задачи. В этой статье мы сосредоточимся на алгоритме сортировки кучи, реализованном в PHP. Мы рассмотрим концепцию пирамидальной сортировки, обсудим ее преимущества и недостатки и предоставим примеры кода для ее реализации. Итак, давайте окунемся в мир алгоритмов сортировки и узнаем, как пирамидальная сортировка может стать мощным инструментом в вашем арсенале программирования PHP.

Что такое пирамидальная сортировка.
Кучная сортировка — это алгоритм сортировки на основе сравнения, известный своей эффективностью и стабильностью. Он работает путем преобразования входного массива в структуру данных двоичной кучи, что позволяет эффективно извлекать максимальный (или минимальный) элемент. Алгоритм делит массив на отсортированную и несортированную область, многократно извлекая максимальный элемент из кучи и заменяя его последним элементом неотсортированной области. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован.

Метод 1: реализация пирамидальной сортировки с нуля
Вот пример того, как можно реализовать пирамидальную сортировку в PHP с нуля:

function heapSort(array &$arr) {
    $length = count($arr);
    // Build a max heap
    for ($i = (int)($length / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $length, $i);
    }
// Extract elements from the heap one by one
    for ($i = $length - 1; $i > 0; $i--) {
        // Swap the root (maximum element) with the last element
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        // Heapify the reduced heap
        heapify($arr, $i, 0);
    }
}
function heapify(array &$arr, int $length, int $root) {
    $largest = $root;
    $left = 2 * $root + 1;
    $right = 2 * $root + 2;
    // Check if the left child is larger than the root
    if ($left < $length && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
// Check if the right child is larger than the largest so far
    if ($right < $length && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }
// If the largest is not the root, swap them and heapify the affected subtree
    if ($largest !== $root) {
        $temp = $arr[$root];
        $arr[$root] = $arr[$largest];
        $arr[$largest] = $temp;
        heapify($arr, $length, $largest);
    }
}
// Usage example
$numbers = [9, 2, 7, 1, 5, 10];
heapSort($numbers);
print_r($numbers); // Output: [1, 2, 5, 7, 9, 10]

Метод 2: использование встроенных функций
PHP предоставляет встроенные функции для сортировки массивов, включая сортировку кучи. Вот пример использования расширения heapqв PHP:

// Usage example
$numbers = [9, 2, 7, 1, 5, 10];
heapq::heapSort($numbers);
print_r($numbers); // Output: [1, 2, 5, 7, 9, 10]

Сортировка пирамидой – это эффективный и стабильный алгоритм сортировки, который можно реализовать на PHP. В этой статье мы рассмотрели концепцию пирамидальной сортировки, предоставили примеры кода для ее реализации и обсудили ее преимущества. Независимо от того, решите ли вы реализовать сортировку кучей с нуля или использовать встроенные функции PHP, понимание алгоритмов сортировки, таких как сортировка кучей, может значительно улучшить ваши способности в программировании. Итак, продолжайте экспериментировать с сортировкой кучи в PHP, чтобы оптимизировать задачи сортировки.