向东博客 专注WEB应用 构架之美 --- 构架之美，在于尽态极妍 | 应用之美，在于药到病除|赢在IT，Playin' with IT,Focus on Killer Application,Marketing Meets Technology.

class PriorityQueue
{
private $heap;
private $_size;
private $maxSize;

public function debug()
{
  print_r($this->heap);
}
private function upHeap()
{
  
  $i=$this->_size;
  $node=$this->heap[$i];
  $j=intval($i>>1);
  while($j>0&&$this->lessThan($node,$this->heap[$j]))
  {
   $this->heap[$i]=$this->heap[$j];
   $i=$j;
   $j=intval($j>>1);
  }
  $this->heap[$i]=$node;
  
}

private function downHeap()
{
  $i=1;
  $node=$this->heap[$i];
  $j=intval($i<<1);
  $k=$j+1;
  if($k<=$this->_size&&$this->lessThan($this->heap[$k],$this->heap[$j]))
  {
   $j=$k;
  }
  
  while($j<=$this->_size&&$this->lessThan($this->heap[$j],$node))
  {
   $this->heap[$i]=$this->heap[$j];
   $i=$j;
   $j=intval($i<<1);
   $k=$j+1;
   if($k<=$this->_size&&$this->lessThan($this->heap[$k],$this->heap[$j]))
   {
    $j=$k;
   }
  }
  $this->heap[$i]=$node;
}


function __construct()
    {
  $this->_size=0;
  $this->heap=null;
  $this->maxSize=0;
    }
    
    function __destruct()
{
  $this->clear();
  unset($this->heap);
}

function put($element)
{
  if($this->_size>=$this->maxSize)
  {
   return false;
  }
  ++$this->_size;
  $this->heap[$this->_size]=$element;
  $this->upHeap();
  return true;
}

function insert($element)
{
  if($this->_size<$this->maxSize)
  {
   return $this->put($element);
  }
  else if($this->_size>0)
  {
   $top=$this->top();
   if(!$this->lessThan($element,$top))
   {
    $this->heap[1]=$element;
    $this->adjustTop();
    return true;
   }
  
  }
  return false;
}


function top()
{
  if($this->_size>0)
  {
   return $this->heap[1];
  }
  
  return null;
}

function pop()
{
  if($this->_size>0)
  {
   $result=$this->heap[1];
   $this->heap[1]=$this->heap[$this->_size];
   $this->heap[$this->_size]=0;
   --$this->_size;
   $this->downHeap();
   return $result;
  }
  return null;
}


function adjustTop()
{
  $this->downHeap();
}


function size()
{
  return $this->_size;
}

function clear()
{
  $this->_size=0;
}
    
    public function initialize($maxSize)
    {
     $this->_size=0;
     $heapSize=$maxSize+1;
     $this->heap=array();
     for($i=0;$i<$heapSize;$i++)
     {
      $this->heap[]=0;
     }
     $this->maxSize=$maxSize;
    }



//根据需要在子类中重写
public function lessThan($cmp1,$cmp2)
{
  return $cmp1<$cmp2;
}
  
}

$arrayRand=array();
for($i=10;$i>=0;$i--)
{
$arrayRand[]=rand(0, 10);;
}

print_r($arrayRand);

$query=new PriorityQueue();
$query->initialize(5);
foreach($arrayRand as $eachValue)
{
$query->insert($eachValue);
}
while(true)
{
$element=$query->pop();
if($element===null)
{
  break;
}
echo "###{$element}\n";
}