> Sorting the entire array when I ask you for the top N elements! Getting the top handful of elements is a linear-time operation, people!

Unlike your other points, this one seems unlikely to cause any trouble in practice. From a polynomial-order perspective, a factor of log N is literally infinitesimal, essentially free.