PHP의 힙 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아보세요.

PHP에서 힙 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아보세요

힙 정렬은 힙 데이터 구조를 기반으로 하는 정렬 알고리즘으로 시간 복잡도는 O(nlogn)입니다. 이 기사에서는 PHP 언어의 힙 정렬 알고리즘 원리를 소개하고 코드 예제를 제공합니다.

1. 힙의 정의와 속성

힙 정렬을 배우기 전에 먼저 힙의 정의와 속성을 이해해야 합니다. 힙은 각 노드의 값이 해당 하위 노드의 값보다 크거나 같은 완전한 이진 트리입니다. 이러한 힙을 빅맥스 힙이라고 합니다. 반대로 각 노드의 값이 자식 노드의 값보다 작거나 같으면 이를 작은 상단 힙이라고 부릅니다.

힙의 특성상 힙의 최상위 요소는 최대값 또는 최소값이므로 힙 정렬에서는 일반적으로 정렬할 배열을 완전 이진 트리로 간주하고 힙의 특성을 사용합니다. 정렬.

2. 힙 정렬 알고리즘의 원리

힙 정렬 알고리즘은 크게 힙 생성과 힙 조정의 두 단계로 나뉩니다.

1. Build Heap: 큰 상단 힙으로 정렬되도록 배열을 조정합니다.

단계는 다음과 같습니다.

• 마지막 리프가 아닌 노드(예: n/2-1)부터 하나씩 앞으로 이동하고 힙 조정 함수(adjustHeap)를 호출합니다.
• 힙 조정 기능은 하향식 접근 방식을 채택하여 현재 노드와 해당 하위 트리를 조정하여 현재 노드가 하위 노드보다 크도록 합니다.
• 전체 배열이 큰 상단 힙으로 조정될 때까지 위의 두 단계를 반복합니다.

2. AdjustHeap: 현재 노드와 해당 하위 트리를 큰 최상위 힙으로 조정합니다.

단계는 다음과 같습니다.

• 현재 노드의 위치를 ​​기준으로 왼쪽 및 오른쪽 하위 노드의 위치를 ​​계산합니다.
• 현재 노드와 왼쪽 및 오른쪽 자식 노드의 값을 비교하여 가장 큰 노드의 위치를 ​​찾습니다.
• 최대 노드의 위치가 현재 노드의 위치가 아닌 경우 최대 노드와 현재 노드의 값을 교환하고 자신을 재귀적으로 호출하여 교환된 하위 트리를 조정합니다.

3. Sort(sortHeap): 힙의 최상위 요소(즉, 배열의 첫 번째 요소)를 마지막 리프 노드와 교체한 다음 나머지 n-1 요소에 대해 힙 조정을 수행합니다.

단계는 다음과 같습니다.

• 힙의 최상위 요소를 마지막 리프 노드로 교환합니다.
• 힙의 범위를 줄입니다. 즉, 정렬된 마지막 리프 노드를 무시합니다.
• 큰 상단 힙의 특성을 유지하기 위해 감소된 범위 힙을 조정했습니다.
• 힙 범위가 1로 줄어들 때까지 위의 세 단계를 반복합니다.

3. PHP 코드 예제

다음은 PHP 언어로 힙 정렬 알고리즘을 구현하는 예제 코드입니다.

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

    // 构建大顶堆
    for ($i = floor($length/2 - 1); $i >= 0; $i--) {
        adjustHeap($arr, $i, $length);
    }

    // 调整堆并排序
    for ($i = $length - 1; $i >= 0; $i--) {
        // 交换堆顶元素和最后一个叶子节点
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整堆使其保持大顶堆性质
        adjustHeap($arr, 0, $i);
    }
}

function adjustHeap(&$arr, $i, $length) {
    $largest = $i; // 最大值的位置
    $left = $i * 2 + 1; // 左子节点的位置
    $right = $i * 2 + 2; // 右子节点的位置

    // 比较当前节点与左右子节点的值，找到最大值的位置
    if ($left < $length && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $length && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值的位置不是当前节点的位置，则交换两个位置的值，并递归调整堆
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        adjustHeap($arr, $largest, $length);
    }
}

// 测试
$arr = [8, 3, 6, 2, 9, 1];
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 6, 8, 9]

4. 시간 복잡도 분석

힙 정렬의 시간 복잡도는 O(nlogn)입니다. 그 중 힙을 만드는 시간복잡도는 O(n)이고, 힙을 조정하는 시간복잡도는 O(logn)이다. n개의 요소를 정렬해야 하므로 전체 시간 복잡도는 O(nlogn)입니다.

요약

이 글에서는 PHP 언어의 힙 정렬 알고리즘의 원리를 자세히 소개하고 해당 코드 예제를 제공합니다. 힙 정렬은 대규모 배열을 정렬하는 데 적합한 효율적인 정렬 알고리즘입니다. 힙 정렬 알고리즘을 학습하면 데이터 구조 및 알고리즘에 대한 이해와 응용 능력을 더욱 향상시킬 수 있습니다.

위 내용은 PHP의 힙 정렬 알고리즘의 원리와 시간 복잡도 분석을 알아보세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!