Operations on a heap

Question

Introduction

I started going through some basic algorithms as I'll have algorithms course next semester. The last time I've written any heap operations is around 5 years ago. This time around it took me an hour to debug the case where the right child wouldn't exist, but left child did. Otherwise it was straightforward.

The code below implements four basic operations on a heap:

• Push (sift down)

• Pop (swap with the last element and then perform push on truncated heap)

• Build heap (push one by one starting from the middle, achieving linear complexity)

• Sort heap (continuosly pop elements and truncate the heap, pushing greater elements to the end of the underlying container)

The code works on iterator ranges, requires RandomAccessIterator, Swappable value types of the iterator type.

Code

#include <vector>
#include <iostream>
#include <random>
#include <unordered_set>
#include <numeric>
#include <algorithm>

std::vector<int> generate_vector(std::size_t size)
{
    if (size == 0)
        return {};
    if (size == 1)
        return {0};

    static std::mt19937 twister{};
    std::vector<int> numbers(size);
    std::iota(numbers.begin(), numbers.end(), 0);
    std::shuffle(numbers.begin(), numbers.end(), twister);

    return numbers;
}

#include <iterator>

namespace shino
{
    template <typename RandomAccessIterator>
    void push_heap(RandomAccessIterator first,
                   RandomAccessIterator last,
                   RandomAccessIterator element)
    {
        auto dist = std::distance(first, element) + 1;
        auto left_child = first + dist * 2 - 1;
        if (left_child >= last)
            return;
        auto right_child = first + dist * 2;
        if (right_child >= last)
        {
            if (*element < *left_child)
            {
                std::iter_swap(element, left_child);
                push_heap(first, last, left_child);
            }
            return;
        }

        if (*element >= *left_child and *element >= *right_child)
            return;

        auto next_location =
                (*left_child >= *right_child) ? left_child : right_child;
        std::iter_swap(next_location, element);
        shino::push_heap(first, last, next_location);
    }

    template <typename RandomAccessIterator>
    void build_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        for (auto middle = first + std::distance(first, last) / 2;
             middle != first; --middle)
        {
            shino::push_heap(first, last, middle);
        }

        shino::push_heap(first, last, first);
    }

    template <typename RandomAccessIterator>
    void pop_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        if (std::distance(first, last) < 2)
            return;

        auto new_last = std::prev(last);
        std::iter_swap(first, new_last);
        shino::push_heap(first, new_last, first);
    }

    template <typename RandomAccessIterator>
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last)
    {
        auto current_last = last;
        while (first != current_last)
        {
            shino::pop_heap(first, current_last);
            --current_last;
        }
    }
}

#include <algorithm>

int main()
{
    for (std::size_t i = 0; i <= 10'000; ++i)
    {
        std::vector<int> v(generate_vector(i));

        std::cout << "heapifying vector of size " << i << '\n';
        shino::build_heap(v.begin(), v.end());
        if (not std::is_heap(v.begin(), v.end()))
            std::cerr << "incorrect heapifying on size " << i << '\n';

        shino::sort_heap(v.begin(), v.end());
        if (not std::is_sorted(v.begin(), v.end()))
            std::cerr << "incorrect heap sorting on size " << i << '\n';
    }
}

---

Concerns

• push_heap looks very ugly

  The control flow is so obfuscated and hard to follow. I couldn't make it better though.

• Indexing looks ugly too

  One of the weakest point of iterators: algorithms where indexing is important. Is there a way to make it better?

• Anything else

Answer 1

It looks like you know what you’re doing.

One thing I spotted: Don’t write std::iter_swap quallified like that. You have to use ADL to pick up the right version provided for the template arguments. You need the “two step”:

using std::iter_swap;
iter_swap (a,b);

just like with regular swap.

---

You don’t need to qualify your own names when you are in that namespace. Or is that intentional to guard against ADL? I never see that technique used.

---

Check out Catch2 for beefing up your main into a comprehensive unit test.

---

generate_vector is missing out on NVRO due to your precondition tests. Declare numbers at the top; always return that.

Answer 2

List all your #include directives at the top of the file. Then you'd see that you #include <algorithm> twice.