Order of comparison for heap elements in python
<p>I'm using a heap to make a priority queue using heapq.</p>

<p>I insert an item into the queue using</p>

<p><code>heapq.heappush(h, (cost, node))</code></p>

<p>where <code>h</code> is the heap object, <code>cost</code> is the item by which I order my heap and <code>node</code> is an object of a custom defined class. </p>

<p>When I run the code, I get the following error when I insert two different items in <code>h</code> with the same <code>cost</code></p>

<blockquote>
  <p>TypeError: unorderable types: SearchNode() &lt; SearchNode()</p>
</blockquote>

<p>where <code>SearchNode()</code> is the class of <code>node</code></p>

<p>The error makes it clear that Python is comparing the second item.</p>

<p><strong>Is there an order of comparison for the heap elements?</strong> If yes, how can I resolve ties in the algorithm such that it does not start comparing the second item. One possible solution that comes to my mind is to overload the comparison operators for the <code>SearchNode()</code> class. </p>

<p>I'm very new to python so feel free to point out if I am missing something very obvious. </p>

<p>If you can sensibly decide on a way to compare nodes, you could use this to break ties. For example, each node may be assigned a "label", which you can guarantee to be unique. You could break ties by comparing labels lexicographically.#</p>

<pre><code>class SearchNode:
    def __init__(self, label):
        self.label = label
        #etc

    def __lt__(self, other):
        return self.label &lt; other.label
</code></pre>

<p>This would ensure that comparisons of <code>(cost, node)</code> is deterministic.</p>

python algorithm python-3.x sorting heap