PHP 优先队列的实现

优先队列其实就是一个最大堆，主要是对最大堆的操作上的一些调整
 1 <?php
 2      #最大优先队列的实现
 3  
 4      #交换函数
 5      function swap(&$arr, $inx1, $inx2) {
 6          $temp = $arr[$inx1];
 7          $arr[$inx1] = $arr[$inx2];
 8          $arr[$inx2] = $temp;
 9      }
10      
11      #最大堆节点下沉调整
12      #@param $arr 待调整数组
13      #@param $start 待调整数组的开始坐标
14      #@param $end 待调整数组的结束坐标
15      function max_heapify(&$arr, $start, $end) {
16          $max_inx = $start;
17  
18          $left_inx = ($start + 1) * 2 - 1; #左孩子坐标
19          $rig_inx = $left_inx + 1; #右孩子坐标
20  
21          if ($left_inx <= $end) { #如果存在左孩子，开始调整
22              if ($arr[$left_inx] > $arr[$max_inx]) {
23                  $max_inx = $left_inx;
24              }
25  
26              if($rig_inx <= $end && $arr[$rig_inx] > $arr[$max_inx]) { #只有拥有左孩子才调整右孩子
27                  $max_inx = $rig_inx;
28              }
29          }
30  
31          if ($max_inx != $start) {
32              swap($arr, $max_inx, $start);
33              max_heapify($arr, $max_inx, $end);
34          }
35      }
36  
37      #建立最大堆
38      function build_max_heap(&$arr) {
39          for ($i = floor(count($arr) / 2) - 1; $i >= 0; $i--) { #从最后一个非叶子节点开始调整数组，构建最大堆
40              max_heapify($arr, $i, count($arr) - 1);
41          }
42      }
43  
44      #取出最大元素并删除
45      function heap_extract_max(&$arr) {
46          $len = count($arr);
47          swap($arr, 0, $len - 1); #首尾交换
48  
49          #保持最大堆性质
50          $max = array_pop($arr);
51          max_heapify($arr, 0, $len - 2);
52          return $max;
53      }      
54  
55      #插入一个比原值大的元素或插入一个新元素到队列
56      #@param $heap 待插入堆
57      #@param $inx 待插入坐标
58      #@param $key 待插入值
59      function heap_increase_key(&$heap, $inx, $key) {
60          if ($inx >= count($heap)) {
61              $heap[] = $key;
62              $inx = count($heap) - 1;
63          } else if ($heap[$inx] >= $key) {
64              die("必须插入比原值大的Key");
65          } else {
66              $heap[$inx] = $key;
67          }
68  
69          #开始调整节点,从插入值与其父母比较,如果比父母大，则上浮插入元素，直到比较到堆顶,否则退出比较
70          while (($p = floor($inx / 2)) >= 0) {
71              if ($heap[$p] < $heap[$inx]) {
72                  swap($heap, $p, $inx);
73                  $inx = $p;
74              } else {
75                  break;
76              }
77          }
78      }
79  
80  
81      $arr = array(1, 5, 7, 4, 2);
82      build_max_heap($arr);
83      print_r($arr);
84      echo "<br>";
85      heap_extract_max($arr);
86      print_r($arr);
87      echo "<br>";
88      heap_increase_key($arr, 3, 10);
89      print_r($arr);
90      echo "<br>";
91      heap_increase_key($arr, 10, 9);
92      print_r($arr);
93  ?>
Array ( [0] => 7 [1] => 5 [2] => 1 [3] => 4 [4] => 2 )
Array ( [0] => 5 [1] => 4 [2] => 1 [3] => 2 )
Array ( [0] => 10 [1] => 5 [2] => 1 [3] => 4 )
Array ( [0] => 10 [1] => 9 [2] => 5 [3] => 4 [4] => 1 )