Neither of those example should work (and neither do on my 3.4.0 installation). Heaps must have sortable components; you could only include callables (which are not sortable) in the tuples being sorted if you guarantee that some element(s) before the callable will ensure the elements are ordered without falling back on comparing the callable members. This isn't a bug; heapq.heapify() *should* fail in this case, and in any case where sorted() would fail due to uncomparable objects.