Return to Answer

• Adding correct calls to delete[] arr; in the right places (remember exceptions, assignments and so on!), which is rather bug-prone.

  Also, new T[size] default-constructs size objects of type T in the contiguous memory. This requires T to be default constructible and might be expensive, depending on T and size.

• Use a std::unique_ptr<T[]> arr instead. This will automatically clean up memory, but you still need to keep track of size, capacity etc.

  Still has the default-construction issue from above.

• Use a std::unique_ptr<std::aligned_storage<sizeof(T), alignof(T)>[]>. Similar to above, but without the default-construction issue. Requires placement new, though.

• Use a std::vector<T> (or similar container) and let it handle all that memory management stuff. Easiest solution, and hard to screw up. It also makes adding additional features easier, like growing capacity.

At the very lowest level, one could extract the comparison operation and the actual container and write the heap logic independently of those. This would allow to reuse the same implementation for many different orderings (min-heap, max-heap, ...) and different underlying storage.

1. There are many uses for heaps (or as the standard library calls them: Priority queues), and more often than not they don't operate on pure numbers. Most likely you'll have some objects ordered by a priority data member or by some timestamp. Relying on std::numeric_limits thus isn't a good idea.

   For deleting a random element, it would be better to swap it with the last element, and then bubble that one up or down as needed.

2. If I understand the question correctly, you seem to want to ask "How can I fail gracefully if I have to return a value?". The simple answer is: You can't. If you need to return a value, that value needs to come from somewhere, and special values like INT_MIN, INT_MAX, 0, -1 or T{} just aren't expressive enough since they introduce ambiguities and require special checks by the caller.

   In some cases, if "no result" is an actually expected return value, you can use std::optional<T> for that, which makes those checks more explicit.

   In other cases, there is no need for returning a value. For example, delete_min doesn't need to return a value (the same value could have been retrieved by calling get_min beforehand). If delete_mins return type got changed to void, it could fail gracefully (not throwing an exception) if the heap were empty.

   Generally, try to not return values from state modifiers (e.g. insertion or deletinon operations), unless those values are an indirect result of those state modifiers themselves (e.g. an iterator pointing to the newly inserted element/to the element after the removed element).

3. See above. -

• Adding correct calls to delete[] arr; in the right places (remember exceptions, assignments and so on!), which is rather bug-prone.

  Also, new T[size] default-constructs size objects of type T in the contiguous memory. This requires T to be default constructible and might be expensive, depending on T and size.

• Use a std::unique_ptr<T[]> arr instead. This will automatically clean up memory, but you still need to keep track of size, capacity etc.

  Still has the default-construction issue from above.

• Use a std::unique_ptr<std::aligned_storage<sizeof(T), alignof(T)>[]>. Similar to above, but without the default-construction issue. Requires placement new, though.

• Use a std::vector<T> (or similar container) and let it handle all that memory management stuff. The easiest solution, and hard to screw up. It also makes adding additional features easier, like growing capacity.

At the very lowest level, one could extract the comparison operation and the actual container and write the heap logic independently of those. This would allow to reuse the same implementation for many orderings (min-heap, max-heap, ...) and different underlying storage.

1. There are many uses for heaps (or as the standard library calls them: Priority queues), and more often than not they don't operate on pure numbers. Most likely you'll have some objects ordered by a priority data member or by some timestamp. Relying on std::numeric_limits thus isn't a good idea.

   For deleting a random element, it would be better to swap it with the last element, and then bubble that one up or down as needed.

2. If I understand the question correctly, you seem to want to ask "How can I fail gracefully if I have to return a value?". The simple answer is: You can't. If you need to return a value, that value needs to come from somewhere, and special values like INT_MIN, INT_MAX, 0, -1 or T{} just aren't expressive enough since they introduce ambiguities and require special checks by the caller.

   In some cases, if "no result" is an actually expected return value, you can use std::optional<T> for that, which makes those checks more explicit.

   In other cases, there is no need for returning a value. For example, delete_min doesn't need to return a value (the same value could have been retrieved by calling get_min beforehand). If delete_mins return type got changed to void, it could fail gracefully (not throwing an exception) if the heap were empty.

   Generally, try to not return values from state modifiers (e.g. insertion or deletion operations), unless those values are an indirect result of those state modifiers themselves (e.g. an iterator pointing to the newly inserted element/to the element after the removed element).

3. See above. -

1. There are many uses for heaps (or as the standard library calls them: Priority queues), and more often than not they don't operate on pure numbers. Most likely you'll have some objects ordered by a priority data member or by some timestamp. Relying on std::numeric_limits thus isn't a good idea.

   For deleting a random element, it would be better to swap it with the last element, and then bubble that one up or down as needed.

2. If I understand the question correctly, you seem to want to ask "How can I fail gracefully if I have to return a value?". The simply answer is: You can't. If you need to return a value, that value needs to come from somewhere, and special values like INT_MIN, INT_MAX, 0, -1 or T{} just aren't expressive enough since they introduce ambiguities and require special checks by the caller.

   In some cases, if "no result" is an actually expected return value, you can use std::optional<T> for that, which makes those checks more explicit.

   In other cases, there is no need for returning a value. For example, delete_min doesn't need to return a value (the same value could have been retrieved by calling get_min beforehand). If delete_mins return type got changed to void, it could fail gracefully (not throwing an exception) if the heap were empty.

   Generally, try to not return values from state modifiers (e.g. insertion or deletinon operations), unless those values are an indirect result of those state modifiers themselves (e.g. an iterator pointing to the newly inserted element/to the element after the removed element).

3. See above. -

1. There are many uses for heaps (or as the standard library calls them: Priority queues), and more often than not they don't operate on pure numbers. Most likely you'll have some objects ordered by a priority data member or by some timestamp. Relying on std::numeric_limits thus isn't a good idea.

   For deleting a random element, it would be better to swap it with the last element, and then bubble that one up or down as needed.

2. If I understand the question correctly, you seem to want to ask "How can I fail gracefully if I have to return a value?". The simple answer is: You can't. If you need to return a value, that value needs to come from somewhere, and special values like INT_MIN, INT_MAX, 0, -1 or T{} just aren't expressive enough since they introduce ambiguities and require special checks by the caller.

   In some cases, if "no result" is an actually expected return value, you can use std::optional<T> for that, which makes those checks more explicit.

   In other cases, there is no need for returning a value. For example, delete_min doesn't need to return a value (the same value could have been retrieved by calling get_min beforehand). If delete_mins return type got changed to void, it could fail gracefully (not throwing an exception) if the heap were empty.

   Generally, try to not return values from state modifiers (e.g. insertion or deletinon operations), unless those values are an indirect result of those state modifiers themselves (e.g. an iterator pointing to the newly inserted element/to the element after the removed element).

3. See above. -

template<typename T, typename Container = std::vector<T>, typename Comparer = std::less<typename Container::value_type>>
class heap {
    Container storage{};
    Comparer compare{};

public:
    heap() = default;

    void push(const T& value);
    void push(T&& value);

    template<typename... Args>
    void emplace(Args&&... args);

    void pop();

    const T& top() const; // could return T, but would be expensive for large T

private:
    void heapify();
    void bubble_down(typename Container::iterator pos); // could be std::size_t or std::ptrdiff_t instead
};

template<typename T, typename Container = std::vector<T>, typename Comparer = std::less<typename Container::value_type>>
class heap {
    Container storage{};
    Comparer compare{};

public:
    heap() = default;

    void push(const T& value);
    void push(T&& value);

    template<typename... Args>
    void emplace(Args&&... args);

    void pop();

    const T& top() const; // could return T, but would be expensive for large T

    typename Container::size_type size() const;
    bool empty() const;

private:
    void heapify();
    void bubble_down(typename Container::iterator pos); // could be std::size_t or std::ptrdiff_t instead
};