No, that's the point; the previous algorithm was O(1) [a simple queue] but that led to doing a huge amount of extra work. By using a smarter queue that "cost" an extra O(log(n)), we could skip work that didn't need doing in the first place.