Please review the following implementation of heapsort and pay attention to the following:Have I correctly chosen the names InputIt and BidirIt for my iterators?Is there a way to make the initialise iterator and then advance it pattern occupy one line instead of two?Is the it != ix - 1 comparison of iterators ok?Here is the code:#include <iterator>#include <functional>template<    class InputIt,    class Key = std::less_equal<        std::iterator_traits<InputIt>::value_type    >>void plunge(    const InputIt ix, // first element of heap    const InputIt iy, // one-past last element of heap    const InputIt iz, // element to be plunged    Key key = Key()   // comparison key to use (up or down)) {    auto ii = iz;    auto il = ix;    std::advance(il, 2 * std::distance(ix, ii) + 1);    while (il < iy) {        auto ir = il + 1;        auto it = ir < iy && key(*ir, *il) ? ir : il;        if (key(*ii, *it)) {return;}        std::iter_swap(ii, it);        std::     swap(ii, it);        il = ix;        std::advance(il, 2 * std::distance(ix, ii) + 1);    }}template<    typename BidirIt,    typename Key = std::greater_equal<        std::iterator_traits<BidirIt>::value_type    >>void heapsort(const BidirIt ix, const BidirIt iy, Key key = Key()) {    auto it = ix;    std::advance(it, std::distance(ix, iy) / 2);    for (; it != ix - 1; --it) {        plunge(ix, iy, it, key);    }    for (it = iy - 1; it != ix - 1; --it) {        std::iter_swap(ix, it);        plunge(ix, it, ix, key);    }}
Heapsort implementation in C++14
c++;algorithm;c++14;heap sort
Answers:Input iterator is not suitable for your plunge function. The reasonis in std::advance(). It increments the iterators, whichinvalidates all previous ones. Bidirectional iterators are ok.Use std::next() as mentioned in the comment byuser2296177.No. Only random access iterators are mandated to support theoperation.Here is the piece of C++ 14 standard that proves answer #1.Paragraph 24.2.3 of N4296 (Input Iterators). Note from table 107 - Input Iterator requirements (in addition to Iterator). Expression:++r;pre: r is dereferenceable.  post: r is dereferenceable or  r is past-the-end.  post: any copies of the  previous value of r are no  longer required either to be  dereferenceable or to be in  the domain of ==.where r is Input Iterator. Additionally, it is stated that post increment has the same effect. Either pre or post increment should be used to implement std::distance(), so it invalidates all copies of Input Iterators according to the standard.Comments about the codetemplate<    class InputIt,    class Key = std::less_equal<        std::iterator_traits<InputIt>::value_type    >>Very arguable gain in readability.Combo of first and last if preferred when referring to range. value is used to refer to some instance of T. ii and il make things even worse. Don't be lazy to type!Bad idea to make iterators const. May be you wanted iterator pointing to const?Nice usage of standard library (though you will need to be sure what it does, which you're trying to do). The code is not working for input iterators, as mentioned in answers.Nice one for the first try overall.