Qth Largest element in an array

gistfile1.php

<?php
/*
INPUT:
- an unsorted array of integers, A
- an integer q, where 0 < q <= A.size

OUTPUT:
- find the q_th smallest element in A


solutions
1. n * log n
2. n * log q


priority queues
- max-heap: int peek, int pop, push(int a), size

A = 1, 2, 3, 0, 4, -1
q = 3

 3
2  1

heap size is 3, q is 3
pop 3, compare it to 0
it's greater so throw it away
push 0

 2
1 0

4, -1

pop 2
compare 2 to 4, 2 is smaller
throw away 4

peek at 2
compare to -1, -1 is smaller
throw away 2
push -1

   1
 0  -1
        
        1
      0   -1

*/

    class qthElement 
    {
        private $maxHeap; // (I think there is actually a SPL_MaxHeap)
        private $q;
        private $array;
        public qthElement($q, $array) {
           $this->q = $q;
           $this->array = $array; 
        }
        
        public solve()
        {
             // verify number
            foreach($array as $val) { // O(n)
            
                if ($maxHeap->size() >= $q) {
                    if($maxHeap->peek() > $val) {
                        $maxHeap->pop(); // trickle down O(log(q))
                        $maxHeap->push($val); // trickle up O(Log(q))
                    }
                }
                else
                {           
                    $maxHeap->push($val); // trickle up O(Log(q))
                }
            }
            
            return $maxHeap->peek();
        }
    }
?>

// http://php.net/manual/en/class.splmaxheap.php