How can std::make_heap be implemented while making at most 3N comparisons?
A binary heap over n elements can be created in O(n) time using a clever algorithm and a clever analysis. In what follows I’m just going to talk about how this works assuming that you have explicit nodes and explicit left and right child pointers, but this analysis is still perfectly valid once you compress … Read more