Trying for an efficient and readable heap-sort implementation

Question

I'm looking for any sort of optimization and/or conventional practice tips, such as using the appropriate data types and naming my variables appropriately.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
constexpr short MIN_ELEMS = 3;
constexpr short MAX_ELEMS = 15;
constexpr short LARGEST_ELEM_INT = 99;
void fill_vector(std::vector<int> &v, short MAX_ELEMS, short LARGEST_ELEM_INT);
void print_vector(const std::vector<int>::iterator start, const std::vector<int>::iterator end);
void max_heap(const std::vector<int>::iterator elem, const std::vector<int>::iterator start, std::vector<int>::iterator end);
void heap_sort(const std::vector<int>::iterator start, const std::vector<int>::iterator end);
int main() {
 srand(time(NULL));
 short random_range = rand() % MAX_ELEMS + 1;
 short num_of_elems = random_range < MIN_ELEMS ? MIN_ELEMS : random_range; // prevents num_of_elems from being less than MIN_ELEMS
 std::vector<int> v;
 fill_vector(v, num_of_elems, LARGEST_ELEM_INT);
 print_vector(v.begin(), v.end());
 heap_sort(v.begin(), v.end());
 print_vector(v.begin(), v.end());
}
void fill_vector(std::vector<int> &v, short num_of_elems, short LARGEST_ELEM_INT) {
 short i = 0;
 while (++i, i <= num_of_elems) {
 v.push_back(rand() % LARGEST_ELEM_INT);
 }
}
void print_vector(const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
 for (auto elem = start; elem != end; ++elem) {
 std::cout << *elem << ' ';
 }
 std::cout << '\n';
}
void max_heap(const std::vector<int>::iterator elem, const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
 auto biggest = elem;
 auto left_child = start+((elem-start)*2+1);
 auto right_child = start+((elem-start)*2+2);
 if (left_child < end && *left_child > *biggest) {
 biggest = left_child;
 }
 if (right_child < end && *right_child > *biggest) {
 biggest = right_child;
 }
 if (elem != biggest) {
 auto val = *biggest;
 *biggest = *elem;
 *elem = val;
 max_heap(biggest, start, end);
 }
}
void heap_sort(const std::vector<int>::iterator start, const std::vector<int>::iterator end) {
 // sort vector to max heap
 for (auto i = start+((end-start)/2)-1; i >= start; --i) {
 max_heap(i, start, end);
 }
 // sort vector in ascending order
 for (auto i = start; i != end-1; ++i) {
 auto val = *start;
 *start = *(start+(end-i-1));
 *(start+(end-i-1)) = val;
 max_heap(start, start, start+(end-i-1));
 }
}

Answer 1

1. Sort your includes. That way, you can keep track even if there are more of them.

2. Writing a test-program is a good idea. Though print the seed-value, and allow overriding from the command-line for reproducibility.

   In line with that, add a method to test whether a range is ordered, print that result and use it for the exit-code too.

3. I would expect a function named print_vector() to, you know, print a vector. Not an iterator-range from a vector. Also, encoding the type of an argument in the function-name hurts usability, especially in generic code.

4. fill_vector() is a curious interface. I would expect get_random_data() which returns the vector.

5. Know your operators. ++i, i <= num_of_elems is equivalent to ++i <= num_elements.

   Anyway, that should be a for-loop, or you could omit i and just count the argument down to zero.

6. Kudos for using constexpr to avoid preprocessor-cnstants where not needed. Still, ALL_CAPS_AND_UNDERSCORES identifiers are generally reserved for preprocessor-macros. They warn/assure everyone that preprocessor-rules apply. Fix the naming too.

7. The C++ headers <cxxx> modelled on the C headers <xxx.h> only guarantee to put their symbols into ::std. Don't assume they are also in the global namespace.

8. max_heap() will often try to create pointers far beyond the passed range. Creating such a pointer invokes undefined behavior.
   For simple and correct code, better use indices.

Answer 2

Unless you really need to save memory, don't use short. Your number-of-elements should be size_t. I've benchmarked x86-64 systems that 16-bit values are much slower than 8, 32, or 64.

Don't use the C NULL macro. C++ has a keyword nullptr.

It would be more readable if you made an alias for std::vector<int>::iterator that you use many times. Really, this ought to be a template, but I understand that writing fixed code is the first step to getting it to work and then you transform it into a template. But you should think about that later step when writing the code.

It's good that you are using iterators. Most beginners seem to use arrays and index numbers instead.

I think your implementation follows the algorithm's textbook description well and is easy enough to follow, but would benefit from some comments. For example, explain that max_heap expects a certain range of elements to already be in a heap structure and draws in a new element (assuming I got that right; I'm not following that in the code but from my memory of the algorithm).

• Deduplicator: Most are good additional points, but at least inside max_heap(), indices have the advantage that even if they are grossly out-of-range, they don't cause UB.