Maximum Priority Queue using Heap
Advice 1

array.shrink_to_fit();: don't do it. If the implementation obeys strictly that request, you will waste a lot CPU cycles. 

Advice 2 

Whenever you publish your results, make sure that your algorithms/data structures do not write to standard output.

Advice 3

You can micro-optimize your max_heapify. Instead of swapping \$n\$ times, do a shift (see image below). When you have to swap, you sacrifice 3 assignments, so the total work is \$3n\$. If you do a shift instead, you make \$n + 1\$ assignments.



Advice 4

T heap_extract_max(std::vector&lt;T&gt;&amp; array)
{
  if(array.size() &lt; 0)
  {
    std::cerr &lt;&lt; "Heap Underflow \n";
    return -1;
  }


I believe bad things will happen when T is not an integer.