PHP 힙 정렬 구현 코드

小云云원래의: 2018-03-22 09:31:401379검색

힙은 완전한 이진 트리로 간주될 수 있습니다. 맨 아래 레이어를 제외하면 모든 레벨이 가득 차 있습니다. 이를 통해 힙을 배열로 표현할 수 있으며 각 노드는 배열의 요소에 해당합니다.
배열과 힙의 관계:
이진 힙은 일반적으로 최대 힙과 최소 힙의 두 가지 유형으로 나뉩니다.
최대 힙: 힙에 있는 각 상위 노드의 요소 값은 해당 하위 노드(존재하는 경우)보다 크거나 같습니다.

최소 힙: 힙에 있는 각 상위 노드의 요소 값은 다음보다 작거나 같습니다. 해당 하위 노드(존재하는 경우) ;

힙 정렬이란 무엇입니까

힙 정렬(최대 힙이 사용된다고 가정)은 힙 상단의 최대 수를 꺼내고 나머지 힙을 최대로 계속 조정하는 것입니다. heap

힙 정렬 알고리즘

힙 만들기: 힙 만들기는 지속적으로 조정됩니다. 힙 프로세스는 len/2에서 시작하여 첫 번째 노드까지 계속됩니다. 여기서 len은 힙의 요소 수입니다. 힙을 만드는 과정은 선형 과정입니다. 힙을 조정하는 과정은 항상 len/2에서 0으로 호출됩니다. 이는 o(h1) + o(h2) ...+ o(hlen/2)와 동일합니다. 여기서 h는 노드의 깊이를 나타내고, len/2는 노드 수를 나타내며, 이는 합산 과정이며 결과는 선형 O(n)입니다.

조정 힙: 조정 힙은 힙을 만드는 과정에서 사용되며, 힙 정렬 과정에서도 사용됩니다. 아이디어는 노드 i와 그 하위 노드 left(i) 및 right(i)를 비교하고 세 개 중 가장 큰(또는 가장 작은) 값을 선택하는 것입니다. 하위 노드는 노드 i 및 거기에 있는 노드와 상호 작용한 다음 힙 조정 프로세스를 호출합니다. 힙을 조정하는 프로세스의 시간 복잡도는 힙의 깊이와 관련이 있습니다. 깊이 방향을 따라 조정되기 때문입니다.

힙 정렬: 힙 정렬은 위의 두 가지 프로세스를 사용하여 수행됩니다. 첫 번째는 요소를 기반으로 힙을 구축하는 것입니다. 그런 다음 힙의 루트 노드를 꺼내고(일반적으로 마지막 노드와 교환) 첫 번째 len-1 노드에 대해 힙 조정 프로세스를 계속한 다음 모든 노드가 제거될 때까지 루트 노드를 제거합니다. 힙 정렬 프로세스의 시간 복잡도는 O(nlogn)입니다. 힙 작성의 시간 복잡도는 O(n)(1회 호출)이므로 힙 조정의 시간 복잡도는 logn이고

조정에는 n-1번이 걸리므로 힙 정렬의 시간 복잡도는 O(nlogn)입니다. .

예:

<?php
// PHP 堆排序算法实现、堆排序时间复杂度分析
/**
 * 堆排序
 * @param array $arr
 */
function heap_sort(array &$arr)
{
    $count = count($arr);
    // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点)
    for($i = floor($count / 2) - 1; $i >= 0; $i --)
    {
        heap_adjust($arr, $i, $count);
    }
    // 调整堆
    for($i = $count - 1; $i >= 0; $i--)
    {
        //将堆顶元素与最后一个元素交换
        swap($arr,0,$i);
        heap_adjust($arr,0,$i - 1);
    }
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $a 数组下标
 * @param int $b 数组下标
 */
function swap(array &$arr, $a, $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $start 数组下标
 * @param int $end 数组下标
 */
function heap_adjust(array &$arr, $start, $end)
{
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
    for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
    {
        if($j != $end && $arr[$j] < $arr[$j + 1])
        {
            $j ++;
        }
        if($temp < $arr[$j])
        {
	        //将根节点设置为子节点的较大值
	        $arr[$start] = $arr[$j];
	        $start = $j;
        }
    }
    $arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);

출력:

Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5 ] => 6 [6] => 7 [7] => 8 [8] => 9 )

시간 복잡도 분석

일반적으로 힙 정렬의 시간 복잡도는 O(nlogn)입니다. 힙 정렬은 원본 레코드의 정렬 상태에 민감하지 않으므로 최고, 최악, 평균 시간 복잡도는 O(nlogn)입니다. 이는 버블링, 단순 선택 및 직접 삽입의 O(n^2) 시간 복잡도보다 성능 면에서 훨씬 더 좋습니다.

힙 정렬은 불안정한 정렬 방법입니다(정렬 전과 후의 동일한 요소의 순서가 바뀔 수 있음).

PHP 힙 정렬 구현 코드

힙 정렬이란 무엇입니까

힙 정렬 알고리즘

관련 기사