[알고리즘]힙 정렬(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);
?>