# Trying for an efficient and readable heap-sort implementation

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));
}
}


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.

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).

• 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. May 21 at 15:51