Maximum Priority Queue using Heap I have written this program for Maximim Priority Queue after studying from Introduction to Algorithm . I want to improve my code. Is there any other method to implement Priority Queue instead of Heap?

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

template&lt;typename T&gt;
void max_heapify(std::vector&lt;T&gt;&amp; array, size_t index)
{
  size_t largest;
  size_t left  = (2*index) + 1;
  size_t right = left + 1;

  if(left &lt; array.size() &amp;&amp; array[left] &gt; array[index])
    largest = left;
  else
    largest = index;

  if(right &lt; array.size() &amp;&amp; array[right] &gt; array[largest])
    largest = right;

  if(largest != index)
  {
    int tmp = array[index];
    array[index] = array[largest];
    array[largest] = tmp;
    max_heapify(array, largest);
  }
}

template&lt;typename T&gt;
void build_max_heap(std::vector&lt;T&gt;&amp; array)
{
  for(int64_t i = (int64_t(array.size())/2) - 1; i &gt;= 0; i--)
  max_heapify(array, i);
}

template&lt;typename T&gt;
T heap_maximum(std::vector&lt;T&gt;&amp; array)
{
  return array[0];
}

template&lt;typename T&gt;
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;
  }
  else
  {
    T max = array[0];
    array[0] = array[array.size() - 1];
    array.erase(std::remove(array.begin(), array.end(), array[0]),
                  array.end());
    array.shrink_to_fit();
    max_heapify(array, 0);
    return max;
  }
}

template&lt;typename T&gt;
void heap_increase_key(std::vector&lt;T&gt;&amp; array, size_t index, T value)
{
  if(value &lt; array[index])
  {
    std::cerr &lt;&lt;"New value is smaller than the current value\n";
    return;
  }
  else
  {
    array[index] = value;
    while(index &gt; 0 &amp;&amp; array[(index/2) - 1] &lt; array[index])
    {
      std::swap(array[index], array[(index/2) - 1]);
      index = (index/2) - 1;
    }
  }
}

template&lt;typename T&gt;
void max_heap_insert(std::vector&lt;T&gt;&amp; array, T value)
{
  array.resize(array.size() + 1);
  array[array.size() - 1] = -1;
  heap_increase_key(array, array.size() - 1, value);
  build_max_heap(array);
}

int main()
{
std::vector&lt;int&gt; v({1, 2, 6, 3, 7});
build_max_heap(v);
std::cout &lt;&lt; "Max-Heap: ";
for(size_t i = 0; i &lt; v.size(); i++)
{
  std::cout &lt;&lt; v[i] &lt;&lt; " ";
}
std::cout &lt;&lt; "\n";
std::cout &lt;&lt; "Extract-Maximum: " &lt;&lt; heap_extract_max(v) &lt;&lt; "\n";
std::cout &lt;&lt; "New Heap: ";
for(size_t i = 0; i &lt; v.size(); i++)
{
  std::cout &lt;&lt; v[i] &lt;&lt; " ";
}
max_heap_insert(v, 10);
std::cout &lt;&lt; "\nNew Heap after inserting 10: ";
for(size_t i = 0; i &lt; v.size(); i++)
{
  std::cout &lt;&lt; v[i] &lt;&lt; " ";
}
std::cout &lt;&lt; '\n';
}
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.