PHP 데이터 구조: 효율적인 정렬과 우선순위 큐를 구현하는 힙 데이터 구조의 비밀

PHP의 힙 데이터 구조는 완전한 바이너리 트리와 힙 속성(상위 노드 값이 하위 노드 값보다 크거나 작음)을 만족하는 트리 구조이며 배열을 사용하여 구현됩니다. 힙은 정렬(작은 요소에서 큰 요소로 가장 큰 요소 추출)과 우선순위 큐(우선순위에 따라 가장 큰 요소 추출)라는 두 가지 작업을 지원합니다. 힙의 속성은 각각 heapifyUp 및 heapifyDown 메서드를 통해 유지됩니다.

PHP의 힙 데이터 구조: 정렬 및 우선순위 큐의 비밀 공개

힙은 다음 두 가지 속성을 만족하는 트리와 유사한 데이터 구조입니다.

• 완전한 이진 트리 속성: tree 의 각 노드에는 두 개의 하위 노드가 있거나 하위 노드가 없어 완전한 이진 트리를 형성합니다.
• 힙 속성: 각 상위 노드의 값은 두 하위 노드의 값(최대 힙)보다 크거나 같거나 두 하위 노드의 값(최소 힙)보다 작거나 같습니다. ) .

PHP 구현

PHP에서는 배열을 사용하여 힙을 구현합니다. 다음은 최대 힙의 PHP 구현입니다.

class MaxHeap {
    private $heap = array();
    private $size = 0;

    public function insert($value) {
        $this->heap[$this->size++] = $value;
        $this->heapifyUp($this->size - 1);
    }

    private function heapifyUp($index) {
        if ($index === 0) {
            return;
        }
        $parentIndex = intval(($index - 1) / 2);
        if ($this->heap[$index] > $this->heap[$parentIndex]) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$parentIndex];
            $this->heap[$parentIndex] = $temp;
            $this->heapifyUp($parentIndex);
        }
    }

    public function extractMax() {
        if ($this->size === 0) {
            return null;
        }
        $max = $this->heap[0];
        $this->heap[0] = $this->heap[$this->size - 1];
        $this->size--;
        $this->heapifyDown(0);
        return $max;
    }

    private function heapifyDown($index) {
        $largestIndex = $index;
        $leftIndex = 2 * $index + 1;
        $rightIndex = 2 * $index + 2;
        if ($leftIndex < $this->size && $this->heap[$leftIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $leftIndex;
        }
        if ($rightIndex < $this->size && $this->heap[$rightIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $rightIndex;
        }
        if ($largestIndex !== $index) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$largestIndex];
            $this->heap[$largestIndex] = $temp;
            $this->heapifyDown($largestIndex);
        }
    }
}

실제 사례

정렬:

$heap = new MaxHeap();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);
$heap->insert(8);
$heap->insert(12);

while ($heap->size > 0) {
    echo $heap->extractMax() . " ";
}

출력: 15 12 10 8 5

우선순위 큐:

$heap = new MaxHeap();
$heap->insert(5);
$heap->insert(2);
$heap->insert(3);
$heap->insert(1);

while ($heap->size > 0) {
    $element = $heap->extractMax();
    echo "服务于元素 " . $element . "\n";
}

출력:
서빙 요소 5
요소 3 제공
요소 2 제공
요소 1 제공

위 내용은 PHP 데이터 구조: 효율적인 정렬과 우선순위 큐를 구현하는 힙 데이터 구조의 비밀의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!