PHP 힙정렬 구현

1 개요

PHP 힙정렬 구현

<?php
function heap_sort(&$a) {
    $heapify = function(&$a, $size, $i) use (&$heapify) {
        $largest = $i;
        $L = 2*$i + 1;
        $R = 2*$i + 2;
        if( $L<$size && $a[$i]<$a[$L] ) $largest=$L;
        if( $R<$size && $a[$largest]<$a[$R] ) $largest=$R;
        if( $largest != $i ) {
        	$temp=$a[$i]; $a[$i]=$a[$largest]; $a[$largest]=$temp;
        	$heapify($a, $size, $largest);
        }
    };
    $size = count($a);
    for($i=$size; $i>-1; $i--) $heapify($a, $size, $i);
    for($i=$size-1; $i>0; $i--) {
        $temp=$a[$i]; $a[$i]=$a[0]; $a[0]=$temp;
        $heapify($a, $i, 0);
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
heap_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

<?php
function heapify(&$a, $size, $i) {
    $largest = $i;
    $L = 2*$i + 1;
    $R = 2*$i + 2;
    if( $L<$size && $a[$i]<$a[$L] ) $largest=$L;
    if( $R<$size && $a[$largest]<$a[$R] ) $largest=$R;
    if( $largest != $i ) {
    	$temp=$a[$i]; $a[$i]=$a[$largest]; $a[$largest]=$temp;
    	heapify($a, $size, $largest);
    }
}
function heap_sort(&$a) {
    $size = count($a);
    for($i=$size; $i>-1; $i--) heapify($a, $size, $i);
    for($i=$size-1; $i>0; $i--) {
        $temp=$a[$i]; $a[$i]=$a[0]; $a[0]=$temp;
        heapify($a, $i, 0);
    }
}
$arr = [9,1,22,4,0,-1,1,22,100,10];
heap_sort( $arr );
echo implode(',',$arr);
# -1,0,1,1,4,9,10,22,22,100

2 같이 보기

• 힙정렬
• 힙정렬 구현