Some heap practice.

heap.cpp

template<typename T>
class MaxHeap
{
public:
	
	using size_t = std::size_t;
	
	static const std::size_t minimum_capacity;
	
	MaxHeap(std::size_t capacity = minimum_capacity)
	: _data(new T[capacity])
	, _size(0)
	, _capacity(capacity)
	{ }
	
	MaxHeap(const std::initializer_list<T>& list,
			std::size_t capacity = minimum_capacity)
	: _size(0)
	{
		_capacity = std::max(capacity, list.size());
		
		_data = new T[_capacity];
		
		for (const auto& item : list) insert(item);
	}
	
	MaxHeap(const MaxHeap& other)
	: _data(new T[other._size])
	, _size(other._size)
	, _capacity(other._capacity)
	{
		std::copy(other._data, other._data + _size, _data);
	}
	
	MaxHeap(MaxHeap&& other) noexcept
	: MaxHeap()
	{
		swap(other);
	}
	
	MaxHeap& operator=(MaxHeap other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(MaxHeap& other) noexcept
	{
		// Enable ADL
		using std::swap;
		
		swap(_data, other._data);
		
		swap(_size, other._size);
		
		swap(_capacity, other._capacity);
	}
	
	friend void swap(MaxHeap& first, MaxHeap& second) noexcept
	{
		first.swap(second);
	}
	
	~MaxHeap()
	{
		delete [] _data;
	}
	
	
	void insert(const T& item)
	{
		if (++_size == _capacity) _resize();
		
		_data[_size] = item;
		
		_swim(_size);
	}
	
	const T& top()
	{
		if (is_empty())
		{
			throw std::out_of_range("No item to pop!");
		}
		
		return _data[1];
	}
	
	T pop()
	{
		if (is_empty())
		{
			throw std::out_of_range("No item to pop!");
		}
		
		auto item = _data[1];
		
		_swap(1, _size);
		
		if (--_size == _capacity/4) _resize();
		
		_sink(1);
		
		return item;
	}
	
	void clear()
	{
		delete [] _data;
		
		_size = 0;
		
		_capacity = minimum_capacity;
		
		_data = new T[_capacity];
	}
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	constexpr inline size_t _left(size_t index) const
	{
		return 2 * index;
	}
	
	constexpr inline size_t _right(size_t index) const
	{
		return 2 * index + 1;
	}
	
	constexpr inline size_t _parent(size_t index) const
	{
		return (index == 1) ? 1 : index/2;
	}
	
	void _swim(size_t index)
	{
		auto parent = _parent(index);
		
		while (_data[parent] < _data[index])
		{
			_swap(parent, index);
			
			index = parent;
			
			parent = _parent(parent);
		}
	}
	
	void _sink(size_t index)
	{
		while (index < _size)
		{
			auto left = _left(index);
			
			if (left > _size) break;
			
			auto child = _right(index);
			
			if (child > _size || _data[left] > _data[child]) child = left;
			
			if (_data[child] > _data[index]) _swap(child, index);
			
			else break;
			
			index = child;
		}
	}
	
	inline void _swap(size_t first, size_t second)
	{
		std::swap(_data[first], _data[second]);
	}
	
	void _resize()
	{
		size_t new_capacity = std::max(minimum_capacity, _size * 2);
		
		auto old = _data;
		
		_data = new T[new_capacity];
		
		std::copy(old, old + _size, _data);
		
		_capacity = new_capacity;
		
		delete [] old;
	}
	
	T* _data;
	
	size_t _size;
	
	size_t _capacity;
	
};

template<typename T>
const std::size_t MaxHeap<T>::minimum_capacity = 10;

template<typename Iterator>
class HeapSort
{
public:
	
	void operator()(Iterator begin, Iterator end)
	{
		auto i = begin;
		
		std::advance(i, std::distance(begin, end)/2);
		
		for (auto stop = std::prev(begin); i != stop; --i)
		{
			_sink(begin, end, i);
		}
		
		for (--end; end != begin; --end)
		{
			std::swap(*begin, *end);
			
			_sink(begin, end, begin);
		}
	}
	
private:
	
	constexpr inline Iterator _left(Iterator begin, Iterator iterator) const
	{
		std::advance(iterator, std::distance(begin, iterator));
		
		return iterator;
	}
	
	constexpr inline Iterator _right(Iterator begin, Iterator iterator) const
	{
		iterator = _left(begin, iterator);
		
		return ++iterator;
	}
	
	void _sink(Iterator begin, Iterator end, Iterator iterator)
	{
		while (iterator < end)
		{
			auto left = _left(begin, iterator);
			
			if (left >= end) break;
			
			auto child = _right(begin, iterator);
			
			if (child >= end || *left > *child) child = left;
			
			if (*child > *iterator)
			{
				std::swap(*child, *iterator);
			}
			
			else break;
			
			iterator = child;
		}
	}
	
	
};

template<typename Iterator>
void heap_sort(Iterator begin, Iterator end)
{
	HeapSort<Iterator> sort;
	
	sort(begin, end);
}