[알고리즘]힙 정렬(Heap Sort)

<?php

class Heap {

    var $numOfData;

    var $heapArr = array();

    var $comp;

    function __construct($pc) { // 힙의 초기화

        $this->numOfData = 0;

        $this->comp = $pc;

    }

    function HIsEmpty() { // 힙이 비었는지 확인

        if ($this->numOfData == 0)

            return TRUE;

        else

            return FALSE;

    }

    function GetParentIDX($idx) { // 부모 노드의 인덱스 값 반환

        return floor($idx/2);

    }

    function GetLChildIDX($idx) { // 왼쪽 자식 노드의 인덱스 값 반환

        return $idx*2;

    }

    function GetRChildIDX($idx) { // 오른쪽 자식 노드의 인덱스 값 반환

        return $this->GetLChildIDX($idx)+1;

    }

// 두 개의 자식 노드중 높은 우선 순위의 자식 노드 인덱스 값 반환

    function GetHiPriChildIDX($idx) {

        if ($this->GetLChildIDX($idx) > $this->numOfData)

            return 0;

        else if ($this->GetLChildIDX($idx) == $this->numOfData)

            return $this->GetLChildIDX($idx);

        else

        {

            $comp = $this->comp;

            if ($comp($this->heapArr[$this->GetLChildIDX($idx)],

                $this->heapArr[$this->GetRChildIDX($idx)]) < 0)

                return $this->GetRChildIDX($idx);

            else

                return $this->GetLChildIDX($idx);

        }

    }

// 힙에 데이터 저장

    function HInsert($data) {

        $idx = $this->numOfData+1;

        $comp = $this->comp;

        while ($idx != 1) {

            if($comp($data, $this->heapArr[$this->GetParentIDX($idx)]) > 0) {

                $this->heapArr[$idx] = $this->heapArr[$this->GetParentIDX($idx)];

                $idx = $this->GetParentIDX($idx);

            }

            else

                break;

        }

        $this->heapArr[$idx] = $data;

        $this->numOfData += 1;

    }

// 힙에서 데이터 삭제

    function HDelete() {

        $retData = $this->heapArr[1];

        $lastElem = $this->heapArr[$this->numOfData];

        $parentIdx = 1;

        $childIdx;

        $comp = $this->comp;

        while ($childIdx = $this->GetHiPriChildIDX($parentIdx)) {

            if ($comp($lastElem, $this->heapArr[$childIdx]) >= 0)

                break;

            $this->heapArr[$parentIdx] = $this->heapArr[$childIdx];

            $parentIdx = $childIdx;

        }

        $this->heapArr[$parentIdx] = $lastElem;

        $this->numOfData -= 1;

        return $retData;

    }

}

$arr = array(3, 4, 2, 1);

// 오름차순

function PriorityComp($d1, $d2) {

    return $d2 - $d1;

}

$heap = new Heap(PriorityComp);

foreach ($arr as $val)

$heap->HInsert($val);

foreach ($arr as $k => $v) 

$arr[$k] = $heap->Hdelete();

print_r($arr);

?>