PHP를 사용하여 힙 정렬 알고리즘을 작성하는 방법

PHP를 사용하여 힙 정렬 알고리즘을 작성하는 방법

힙 정렬은 효율적인 정렬 알고리즘입니다. 핵심 아이디어는 정렬할 시퀀스를 바이너리 힙으로 구성한 다음 힙의 구조를 지속적으로 조정하여 정렬을 수행하는 것입니다. 이 기사에서는 PHP를 사용하여 힙 정렬 알고리즘을 작성하는 방법을 소개하고 참조용 코드 예제를 제공합니다.

1. 힙 정의
   힙 정렬 알고리즘 작성을 시작하기 전에 먼저 힙의 정의와 속성을 명확히 해야 합니다. 힙은 다음 속성을 가진 완전한 이진 트리입니다. 모든 노드 i에 대해 다음 두 가지 조건이 충족됩니다.
2. 상위 노드의 값은 항상 하위 노드의 값(최대 힙)보다 크거나 같습니다.
3. 상위 노드의 값은 항상 하위 노드(최소 힙)의 값보다 작거나 같습니다.
4. 힙 작업 조정
   힙을 구축하려면 힙 조정 작업을 수행하는 방법을 이해해야 합니다. 힙 조정은 두 단계로 나뉩니다.
5. 리프가 아닌 마지막 노드에서 시작하여 해당 노드를 하위 노드와 차례로 비교하고 더 큰(또는 더 작은) 값을 상위 노드의 위치로 교환합니다.
전체 힙의 구조가 힙의 속성을 만족할 때까지 위 단계를 반복합니다.

다음은 PHP에서 구현된 힙 조정 함수의 예입니다.

function heapify(&$arr, $n, $i) {
    $largest = $i; // 将当前节点标记为最大值节点
    $l = 2 * $i + 1; // 左子节点
    $r = 2 * $i + 2; // 右子节点

    // 如果左子节点大于根节点
    if ($l < $n && $arr[$l] > $arr[$largest]) {
        $largest = $l;
    }

    // 如果右子节点大于根节点
    if ($r < $n && $arr[$r] > $arr[$largest]) {
        $largest = $r;
    }

    // 如果最大值不等于当前节点，则交换它们的位置
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        // 递归调整交换之后的子树
        heapify($arr, $n, $largest);
    }
}

힙 정렬 알고리즘
3. 힙 정의 및 힙 조정 작업이 끝나면 힙 정렬 알고리즘을 작성할 수 있습니다. 힙 정렬의 주요 단계는 다음과 같습니다.
   
최대 힙 구축: 리프가 아닌 마지막 노드부터 시작하여 순서대로 힙 조정 함수를 호출하여 최대 힙을 구축합니다.
4. 정렬: 최상위 요소(최대값)를 교환합니다. ) 힙의 마지막 요소 위치를 삭제하고 힙 크기를 1만큼 줄인 다음 힙 조정 함수를 호출하여 나머지 요소의 순서를 조정합니다.
5. 힙 크기가 1이 될 때까지 위 단계를 반복합니다. , 이때 모든 요소는 오름차순으로 정렬됩니다.

다음은 PHP에서 구현된 힙 정렬 함수의 예입니다.

function heapSort(&$arr) {
    $n = count($arr);

    // 构建最大堆
    for ($i = ($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 排序
    for ($i = $n - 1; $i > 0; $i--) {
        // 交换堆顶和最后一个元素
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整剩余元素的顺序
        heapify($arr, $i, 0);
    }
}

힙 정렬 알고리즘 사용
4. 힙 정렬 알고리즘을 사용하는 방법은 매우 간단합니다. 위의 힙 정렬 기능. 다음은 힙 정렬 알고리즘을 사용하여 배열을 정렬하는 예입니다.
   

$arr = [3, 7, 2, 11, 1, 9, 6, 4, 8];

echo "排序前：" . implode(", ", $arr) . "
";

heapSort($arr);

echo "排序后：" . implode(", ", $arr) . "
";

위 코드를 실행하면 다음과 같은 결과가 나타납니다.

排序前：3, 7, 2, 11, 1, 9, 6, 4, 8
排序后：1, 2, 3, 4, 6, 7, 8, 9, 11

이렇게 하면 PHP를 사용하여 힙 정렬 알고리즘을 성공적으로 작성하고 적용했습니다. .

요약:

힙 정렬은 최대(또는 최소) 힙을 구축하여 정렬을 구현하는 효율적인 정렬 알고리즘입니다. 힙의 구조를 조정함으로써 힙 정렬을 쉽게 구현할 수 있습니다. PHP를 사용하여 힙 정렬 알고리즘을 작성하는 것은 비교적 간단합니다. 힙 조정 함수와 힙 정렬 함수를 작성하고 정렬할 배열을 매개변수로 전달하면 됩니다. 이 글의 내용이 힙 정렬 알고리즘을 이해하고 사용하는 데 도움이 되기를 바랍니다.

위 내용은 PHP를 사용하여 힙 정렬 알고리즘을 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!