Priority Queue

A very elegant solution to the problem of needing comparisons might be to implement comparisons on your nodes.  There are a set of Python special methods for rich comparisons - __lt__, __gt__, __eq__, __ne__, etc.  With these methods implemented on your Node class, you'll be able to compare nodes with the <, >, ==, and != operators.