Heap implementation to keep track of the largest N values in a stream.

n-largest-heap.cpp

template<typename T, std::size_t N>
class NLargestHeap
{
public:
	
	using size_t = std::size_t;
	
	static const size_t minimum_capacity = 10;
	
	NLargestHeap(std::initializer_list<T> list,
			size_t capacity = minimum_capacity)
	: _size(0)
	{
		_capacity = std::max(list.size(), capacity);
		
		_data = new T[_capacity];
		
		for (const auto& i : list) insert(i);
	}
	
	NLargestHeap(size_t capacity = minimum_capacity)
	: _data(new T[capacity])
	, _size(0)
	, _capacity(capacity)
	{ }
	
	NLargestHeap(const NLargestHeap& other)
	: _data(new T[other._capacity])
	, _size(other._size)
	, _capacity(other._capacity)
	{
		std::copy(other._data,
				  other._data + other._capacity,
				  _data);
	}
	
	NLargestHeap(NLargestHeap&& other) noexcept
	: NLargestHeap()
	{
		swap(other);
	}
	
	NLargestHeap& operator=(NLargestHeap other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(NLargestHeap& other) noexcept
	{
		// Enable ADL
		using std::swap;
		
		swap(_data, other._data);
		
		swap(_size, other._size);
		
		swap(_capacity, other._capacity);
	}
	
	friend void swap(NLargestHeap& first, NLargestHeap& second) noexcept
	{
		first.swap(second);
	}
	
	~NLargestHeap()
	{
		delete [] _data;
	}
	
	
	void insert(const T& item)
	{
		if (_size < N)
		{
			if (++_size == _capacity) _resize();
			
			_data[_size] = item;
			
			_swim(_size);
		}
		
		else if (item > _data[1])
		{
			_data[1] = item;
			
			_sink(1);
		}
	}
	
	
	const T& top() const
	{
		if (_size < 1) throw std::invalid_argument("No such element!");
		
		return _data[1];
	}

	T pop()
	{
		if (_size < 1) throw std::invalid_argument("No such element!");
		
		auto value = _data[1];
		
		_swap(1, _size);
		
		if (--_size == _capacity/4) _resize();
		
		_sink(1);
		
		return value;
	}
	
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	void _resize()
	{
		size_t new_capacity = _size * 2;
		
		if (new_capacity < minimum_capacity) return;
		
		_capacity = new_capacity;
		
		auto old = _data;
		
		_data = new T[new_capacity];
		
		std::copy(old, old + _size + 1, _data);
		
		delete [] old;
	}
	
	constexpr inline size_t _parent(size_t index) const
	{
		return index == 1 ? 1 : index/2;
	}
	
	constexpr inline size_t _left(size_t index) const
	{
		return index * 2;
	}
	
	constexpr inline size_t _right(size_t index) const
	{
		return index * 2 + 1;
	}
	
	void _swim(size_t index)
	{
		if (index == 1) return;
		
		size_t parent = _parent(index);
		
		while (_data[index] < _data[parent])
		{
			_swap(index, parent);
			
			index = parent;
			
			parent = _parent(index);
		}
	}
	
	void _sink(size_t index)
	{
		if (index == _size) return;
		
		while (true)
		{
			auto left = _left(index);
			
			if (left > _size) return;
			
			auto right = _right(index);
			
			size_t child;
			
			if (right > _size || _data[left] < _data[right]) child = left;
			
			else child = right;
			
			if (_data[child] < _data[index]) _swap(child, index);
			
			else return;
			
			index = child;
		}
	}
	
	void _swap(size_t first, size_t second)
	{
		auto temp = _data[first];
		
		_data[first] = _data[second];
		_data[second] = temp;
	}
	
	
	T* _data;
	
	size_t _size;
	
	size_t _capacity;
};