PHP는 힙 정렬 알고리즘을 구현합니다(코드 예)

컴퓨터 과학에서 힙 정렬(1964년 J. W. J. Williams가 발명)은 비교 기반 정렬 알고리즘입니다. 힙 정렬은 향상된 선택 정렬로 볼 수 있습니다. 이 알고리즘과 유사하게 입력을 정렬 영역과 비정렬 영역으로 나누고 가장 큰 요소를 추출하여 정렬 영역으로 이동하여 정렬되지 않은 영역을 대화식으로 축소합니다. 개선 사항에는 선형 시간 검색 대신 힙 데이터 구조를 사용하여 최대값을 찾는 것이 포함됩니다.

실제로는 대부분의 시스템에서 잘 구현된 퀵소트보다 약간 느리게 실행되지만 최악의 경우 O(n log n) 런타임이라는 이점이 있습니다. 힙 정렬은 내부 정렬 알고리즘이지만 안정적인 정렬은 아닙니다.

힙 정렬 알고리즘은 무작위로 배열된 값 집합을 정렬합니다. 알고리즘의 첫 번째 단계에서 배열 요소는 힙 속성을 충족하도록 재정렬됩니다. 실제 정렬을 진행하기 전에 설명을 위해 힙 트리 구조를 간략하게 보여줍니다.

PHP 힙 정렬 알고리즘 아이디어 다이어그램:

PHP 힙 정렬 구현 코드는 다음과 같습니다.

<?php
class Node
{
    private $_i;

    public function __construct($key)
    {
        $this->_i = $key;
    }

    public function getKey()
    {
        return $this->_i;
    }
}

class Heap
{
    private $heap_Array;
    private $_current_Size;

    public function __construct()
    {
        $heap_Array = array();
        $this->_current_Size = 0;
    }

 
    public function remove()
    {
        $root = $this->heap_Array[0];
        
        $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size];
        $this->bubbleDown(0);
        return $root;
    }

   
    public function bubbleDown($index)
    {
        $larger_Child = null;
        $top = $this->heap_Array[$index]; 
        while ($index < (int)($this->_current_Size/2)) { 
            $leftChild = 2 * $index + 1;
            $rightChild = $leftChild + 1;

          
            if ($rightChild < $this->_current_Size
                && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) 
            {
                $larger_Child = $rightChild;
            } else {
                $larger_Child = $leftChild;
            }

            if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) {
                break;
            }

            
            $this->heap_Array[$index] = $this->heap_Array[$larger_Child];
            $index = $larger_Child;
        }

        $this->heap_Array[$index] = $top;
    }

    public function insertAt($index, Node $newNode)
    {
        $this->heap_Array[$index] = $newNode;
    }

    public function incrementSize()
    {
        $this->_current_Size++;
    }

    public function getSize()
    {
        return $this->_current_Size;
    }

    public function asArray()
    {
        $arr = array();
        for ($j = 0; $j < sizeof($this->heap_Array); $j++) {
            $arr[] = $this->heap_Array[$j]->getKey();
        }

        return $arr;
    }
}

function heapsort(Heap $Heap)
{
    $size = $Heap->getSize();
    
    for ($j = (int)($size/2) - 1; $j >= 0; $j--)
    {
        $Heap->bubbleDown($j);
    }
   
    for ($j = $size-1; $j >= 0; $j--) {
        $BiggestNode = $Heap->remove();
    
        $Heap->insertAt($j, $BiggestNode);
    }

    return $Heap->asArray();
}

$arr = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 : ";
echo implode(&#39;, &#39;,$arr );
$Heap = new Heap();
foreach ($arr as $key => $val) {
    $Node = new Node($val);
    $Heap->insertAt($key, $Node);
    $Heap->incrementSize();
}
$result = heapsort($Heap);
echo "\n排序后数组 : ";
echo implode(&#39;, &#39;,$result)."\n";

출력:

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 : -1, 0, 1, 2, 3, 4, 5

이 문서는 PHP 힙 정렬에 대한 소개입니다. 그렇게 되기를 바랍니다. 도움이 필요한 친구에게 도움이 되십시오.

위 내용은 PHP는 힙 정렬 알고리즘을 구현합니다(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!