title: Java implement PriorityQueue - when no Comparator provided
body: <p>I am trying to implement my own version of a generic PriorityQueue in Java (using binary heaps). I have chosen to use an Object array for my heap.</p>
  
  <pre><code>Object[] qArray = new Object[initial_Size];
  </code></pre>
  
  <p>If a user provides a comparator - the implementation is pretty straightforward as I can use the comparator's compare method when I am doing my element comparisons.</p>
  
  <pre><code>Comparator&lt;T&gt; comparator; //Set to a user-provided comparator in my constructor.
  
  if(comparator.compare((T)qArray[i], (T)qArray[j])
      //do something
  </code></pre>
  
  <p>However, the problem comes when user does not provide a default comparator. One way I could potentially handle this is to make my PriorityQueue class implement Comparator and have the comparator do the following compare -</p>
  
  <pre><code>@Override
  public int compare(T o1, T o2)
  {
      if(this.comparator == null) //no comparator provided by user
      {
          return o1.toString().compareTo(o2.toString());
      }
      else
      {
          return this.comparator.compare(o1, o2);
      }
  }
  </code></pre>
  
  <p>However, this comparator is a little lame. It obviously works brilliantly for PriorityQueues of type String, but in case of (say) Integers, not quite (It would think 5 is greater than 49). Another approach would be to force the user to provide a comparator - but I know that Java Util's implementation of PriorityQueue is much kinder.  </p>
  
  <p>So, I tried to reverse-engineer Java's PriorityQueue a little bit and initialized a Priority Queue of a custom class type without passing in a comparator. </p>
  
  <pre><code>public class TestClass {
  
      public class SomeClass
      {
          int value;
          SomeClass(int value)
          {
              this.value = value;
          }
      }
  
      public static void main(String[] args)
      {
          TestClass tClass = new TestClass();
          TestClass.SomeClass sClass1 = tClass.new SomeClass(10);
          TestClass.SomeClass sClass2 = tClass.new SomeClass(20);
  
          PriorityQueue&lt;TestClass.SomeClass&gt; pQueue = new PriorityQueue&lt;TestClass.SomeClass&gt;();
          pQueue.add(sClass1);
      }
  }
  </code></pre>
  
  <p><img src="https://i.stack.imgur.com/ZbyDn.png" alt="StackTrace"></p>
  
  <p>So this siftUpComparable method potentially holds some important clues about how the util package does its comparing, but when I tried to read the source code I was lost. </p>
  
  <p>So any ideas for implementation here - wherein if a natural ordering comparator is defined on the provided object type (like Integer or String) it should be used by default. </p>