<?php
//Kopiec
//Marek Rynarzewski
//www.algorytm.org

class Kopiec
{
	//tablica przechowywujaca wartosci kopca
	private $_aArray = array();
	//wielkosc kopca
	private $_iHeapSize;
	
	//tworzy kopiec na podstawie danych z tablicy $array
	public function __construct(array $array = null)
	{
		//wczytaj tablice jezeli jest podana i zawiera wylacznie wartosci liczbowe
		if ($array != null and is_numArr($array))
		{
			//zapewnij ze tablica jest numerowana od 1
			if ( getFirstKey($array) == 1)
			{
				$this->_aArray = $array;
			}
			else
			{
				$this->_aArray = setFirstKeyAs1($array);
			}
		}
		$this->_iHeapSize = count($this->_aArray);
		$this->buildheap();
	}
	
	//buduje kopiec - zapewnia ze podana tablica spelnia warunek kopca
	public function buildheap()
	{
		//poczawszy od ostatniego elementu, zapenij ze kazdy spelnia warunek kopca
		$this->_iHeapSize = count($this->_aArray);
		for ($i = floor(count($this->_aArray)/2); $i >= 1; $i --)
		{
			$this->heapify($i);
		}
	}
	
	//sortowanie stogowe
	public function heapsort()
	{
		//utworz kopiec 
		$this->buildheap();
		//dla kazdego elementu
		for ($i = count($this->_aArray); $i >= 2; $i --)
		{
			//usun z kopca element najwiekszy (korzen), czyli
			//przesun go na koniec kopca (zamien z ostatnim) i zmniejsz jego rozmiar o 1)
			$this->swapInArray(1, $i);
			$this->dec();
			//zapewnij ze nowy korzen spelnia warunek kopca
			$this->heapify(1);
		}
	}
	
	//zapewnia, ze element $i-ty jest na odpowiednim miejscu - spelnia warunek kopca
	public function heapify($i)
	{
		$l = Kopiec::left($i);
		$r = Kopiec::right($i);
		if ($l <= $this->heapSize() and $this->get($l) > $this->get($i))
		{
			$L = $l;
		}
		else
		{
			$L = $i;
		}
		if ($r <= $this->heapSize() and $this->get($r) > $this->get($L))
		{
			$L = $r;
		}
		//jezeli, element $i-ty jest mniejszy od ktoregos ze swoich dzieci, zamien go miejscami
		if ($L != $i)
		{
			$this->swapInArray($i, $L);
			$this->heapify($L);
		}
	}
	
	//zwraca wielkosc (liczbe elementow) kopca
	public function heapSize()
	{
		return $this->_iHeapSize;
	}
	
	//ustawia $i-ty element kopca na wartosc $v
	public function set($i, $v)
	{
		$this->_aArray[$i] = $v;
	}
	
	//zwraca wartosc $i-tego elementu
	public function get($i)
	{
		return $this->_aArray[$i];
	}
	
	//zamienia elementy $a-ty i $b-ty miejscami
	private function swapInArray($a, $b)
	{
		$c = $this->get($a);
		$this->set($a, $this->get($b));
		$this->set($b, $c);
	}
	
	//zwraca lewe dziecko wezla $i
	public static function left($i)
	{
		return 2*$i;
	}
	
	//zwraca prawe dziecko wezla $i
	public static function right($i)
	{
		return Kopiec::left($i)+1;
	}
	
	//zwraca rodzica wezla $i
	public static function _parent($i)
	{
		return floor($i/2);
	}
	
	//wypisuje zawartosc kopca
	public function __toString()
	{
		return wypiszKopiec($this);
	}
	
	//zwraca kopiec w postaci tablicy
	public function getArray()
	{
		return $this->_aArray;
	}
	
	//zwraca wartosc maksymalna w kopcu (korzen)
	public function max()
	{
		return $this->get(1);
	}
	
	//zamienia element maksymalny kopca z ostatnim i zmniejsza kopiec o jeden element
	//(operacja do sortowania stogowego)
	public function extract_max()
	{
		$max = $this->max();
		$this->set(1, $this->get($this->heapSize()));
		$this->dec();
		$this->heapify(1);
		return $max;
	}
	
	//zmienijsza wielkosc kopca
	public function dec()
	{
		$this->_iHeapSize--;
	}
	
	//zwieksza wielkosc kopca
	public function inc()
	{
		$this->_iHeapSize++;
	}
	
	//wstawia element do kopca
	public function insert($key)
	{
		//zwieksz wielkosc kopca
		$this->inc();
		//ustaw wartosc ostatniego elementu na zadana
		$i = $this->heapSize();
		$this->set($i, $key);
		//zapenij ze ostatni element spelnia warunek kopca
		//jezeli wstawiony element jest wiekszy od rodzica, zamieniamy go miejscami.
		//nastrpnie po zamianie zn�w sprawdzamy, czy element jest wirkszy od nowego rodzica, itd...
		while ($i > 1 and $this->get(Kopiec::_parent($i)) < $this->get($i))
		{
			$this->swapInArray($i, Kopiec::_parent($i));
			$i = Kopiec::_parent($i);
		}
	}
}

//wypisuje zawartosc kopca
function wypiszKopiec(Kopiec $k)
{
	$a = $k->getArray();
	$N = count($a);
	$x = pow(2, Floor(log($N)/log(2))) - 1; 
	$k = 2;
	for ($i = 1; $i <= $N; $i ++)
	{
		for ($j = 0; $j < $x; $j ++)
		{
			echo '  ';
		}
		printf("%2d", $a[$i]);
		for ($j = 0; $j <= $x; $j ++)
		{
			echo '  ';
		}
		if (($i + 1) == $k)
		{
			$k += $k;
			$x = floor($x/2);
			echo '<br/>';
		}
	}
}

//zwraca true, jezeli wszystkie wartosc w tablicy sa liczbami
function /*boolean*/ is_numArr(array $a)
{
	foreach ($a as $k => $i)
	{
		if (!is_numeric($k))
			return false;
	}
	return true;
}

//zwraca wartosc pierwszego klucza w tablicy (numer indeksu od ktorego zaczyna sie tablica)
function /*mixed*/ getFirstKey(array $a)
{
	foreach ($a as $k => $i)
	{
		return $k;
	}
}

//przerabia tablice tak, by pierwszy indeks by rowny 1
function /*array*/ setFirstKeyAs1(array $array)
{
	$r = array();
	foreach ($array as $k => $i)
	{
		if (getFirstKey($array) == $k)
		{
			$r[1] = $i;
		}
		else
		{
			$r[] = $i;
		}
	}
	return $r;
}

//przyklad:
$a = array(1=>4, 5, 3, 9, 10, 2, 6, 4, 3, 8, 7, 4, 0);
$k = new Kopiec($a);
echo 'Kopiec:<pre>';
echo wypiszKopiec($k);
echo '</pre>';

$k->insert(11);
echo 'Kopiec po wstawieniu elementu 11:<pre>';
echo wypiszKopiec($k);
echo '</pre>';

echo 'Sortowanie stogowe: ';
echo $k->heapsort();
$a = $k->getArray();
$N = count($a);
for ($i = 1; $i <= $N; $i ++) 
	echo $a[$i].', ';
?>