public
Last active

A min-max heap and a limited-size min heap (in PHP)

  • Download Gist
limitedminheap.php
PHP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
<?php
 
include 'minmaxheap.php';
 
/* A min-heap that will restrict itself to a maximum of some number of values.
* Implemented internally as a min-max heap.
*
* Public API:
* - Contructor takes a number, used as the maximum number of values allowed on the heap
* - count() - returns the number of elements on the heap
* - peek_min() - returns the minimum value
* - get_min() - removes the minimum value and returns it
* - insert($val) - adds $val to the heap
*/
class LimitedMinHeap extends MinMaxHeap {
private $max_values;
 
function __construct($max = 100) {
parent::__construct();
$this->max_values = $max;
}
 
public function insert($val) {
# If there are at least max_values values
if ($this->count() >= $this->max_values) {
# Do nothing if this value is larger than the current max
if ($val >= $this->peek_max()) return;
 
# Throw out the max value
$this->get_max();
}
 
# Add the new value
parent::insert($val);
}
}
 
?>
minmaxheap.php
PHP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
<?php
 
/* A min-max heap as described in
* <http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf>
*
* Public API:
* - count() - returns the number of elements on the heap
* - peek_min() - returns the minimum value
* - peek_max() - returns the maximum value
* - get_min() - removes the minimum value and returns it
* - get_max() - removes the maximum value and returns it
* - insert($val) - adds $val to the heap
*
* - compare($a, $b) - takes two list indexes, returns 0 if the values are
* equal, returns 1 if $a > $b, returns -1 if $a < $b. You may override
* this method in order to handle more complex objects.
*/
class MinMaxHeap {
protected $list;
 
function __construct() {
$this->list = array();
}
 
public function count() {
return count($this->list);
}
 
public function peek_min() {
if ($this->count() == 0) return null;
$rv = $this->list[0];
return $rv;
}
public function get_min() {
if ($this->count() == 0) return null;
$rv = $this->list[0];
 
# Remove the last element
$last = array_pop($this->list);
 
if ($this->count() > 0) {
# Place it in the root
$this->list[0] = $last;
 
# Trickle down
$this->trickle_down(0);
}
 
# Return the old root
return $rv;
}
 
public function peek_max() {
if ($this->count() == 0) return null;
$max = $this->get_max_id();
return $this->list[$max];
}
public function get_max() {
if ($this->count() == 0) return null;
$max = $this->get_max_id();
$rv = $this->list[$max];
 
# Remove the last element
$last = array_pop($this->list);
 
if ($this->count() > $max) {
# Place it in the max
$this->list[$max] = $last;
 
# Trickle down
$this->trickle_down($max);
}
 
# Return the old root
return $rv;
}
private function get_max_id() {
if ($this->count() == 0) return null;
$max = 0;
if ($this->count() >= 2)
$max = 1; # left root child is definitely bigger
if ($this->count() >= 3 and $this->compare(2, 1) == 1)
$max = 2; # maybe right root child is bigger still
return $max;
}
 
public function insert($val) {
# Place this value at the end
$i = array_push($this->list, $val) - 1;
 
# Bubble up
$this->bubble_up($i);
}
 
private function trickle_down($i) {
$dir = $this->get_level_direction($i);
$this->trickle_down_r($i, $dir);
}
private function trickle_down_r($i, $dir) {
# If list[i] has children then
if ($this->count() > $i * 2 + 1) {
# Find the index of the smallest of children and grandchildren
$m = $i*2 + 1;
foreach( array($i*2+2, $i*4+3, $i*4+4, $i*4+5, $i*4+6) as $j ) {
if (isset($this->list[$j]) and
$this->compare($j, $m) == $dir)
$m = $j;
}
 
# If m < i
if ($this->compare($m, $i) == $dir) {
# If m is a granchild then
if ($m >= $i*4 + 3) {
# Swap list[m] and list[i]
$tmp = $this->list[$m];
$this->list[$m] = $this->list[$i];
$this->list[$i] = $tmp;
 
# If list[m] is now > list[its parent]
$mparent = floor(($m-1) / 2);
if ($this->compare($m, $mparent) == -$dir) {
# Swap list[m] and list[its parent]
$tmp = $this->list[$m];
$this->list[$m] = $this->list[$mparent];
$this->list[$mparent] = $tmp;
}
 
# trickle_down_r(m)
$this->trickle_down_r($m, $dir);
# else, m is a child
} else {
# Swap list[m] and list[i]
$tmp = $this->list[$m];
$this->list[$m] = $this->list[$i];
$this->list[$i] = $tmp;
}
}
}
}
 
private function bubble_up($i) {
$dir = $this->get_level_direction($i);
 
# If list[i] has a parent and list[i] > list[parent]
$iparent = floor(($i-1) / 2);
if ($i > 0 and $this->compare($i, $iparent) == -$dir) {
# swap list[i] and list[parent]
$tmp = $this->list[$i];
$this->list[$i] = $this->list[$iparent];
$this->list[$iparent] = $tmp;
 
# bubble_up_r(parent)
$this->bubble_up_r($iparent, -$dir);
# else
} else {
# bubble_up_r(i)
$this->bubble_up_r($i, $dir);
}
}
private function bubble_up_r($i, $dir) {
# If list[i] has grandparent
if ($i > 2) {
# If list[i] < list[grandparent]
$igp = floor((floor(($i-1) / 2)-1) / 2);
if ($this->compare($i, $igp) == $dir) {
# swap list[i] and list[grandparent]
$tmp = $this->list[$i];
$this->list[$i] = $this->list[$igp];
$this->list[$igp] = $tmp;
 
# bubble_up_r(grandparent)
$this->bubble_up_r($igp, $dir);
}
}
}
 
private function get_level_direction($i) {
return (floor(log($i+1, 2)) % 2 == 1) ? 1 : -1;
}
 
protected function compare($i, $j) {
if ($i == $j or $this->list[$i] == $this->list[$j]) return 0;
return ($this->list[$i] < $this->list[$j]) ? -1 : 1;
}
}
 
?>

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.