#pragma once

#include <iostream>
#include <cstdlib>

using namespace std;

extern const int DEFAULT_CAPACITY;

// 堆是一棵完全二叉树，其存储结构是用一维数组存储的
template <class TData>
class MaxHeap
{
private:
	TData* elements_;	// 堆元素数组
	int size_;			// 当前堆的size
	int capacity_;		// 容量

	// 下筛
	void siftDown_(int index);

	//  上筛
	void siftUp_(int index);

	// 交换
	void swap_(TData& element1, TData& element2);
public:
	// 初始化空堆
	explicit MaxHeap(int capacity = DEFAULT_CAPACITY);

	// 根据已有的数组初始化有数据的堆，自底向上建堆法
	MaxHeap(TData* elements, int length, int capacity = DEFAULT_CAPACITY);

	~MaxHeap()
	{
		delete[] this->elements_;
		this->elements_ = NULL;
	}

	// 插入堆，自顶向下建堆法，插入新元素到一维数组尾部
	bool insert(const TData& element);

	// 堆顶出堆
	bool pop(TData& element);

	// 获取堆顶
	bool top(TData& element);

	// 是否是空堆
	bool isEmpty() const { return this->size_ == 0; }

	// 是否满堆
	bool isFull() const { return this->size_ == this->capacity_; }

	// 获取堆大小
	int size() const { return this->size_; }

	// 清空堆
	void clear() { this->size_ = 0; }
};

template<class TData>
inline void MaxHeap<TData>::siftDown_(int index)
{
	for (int child_index = 2 * index + 1; child_index < this->size_; index = child_index, child_index = index * 2 + 1)
	{
		// child_index是index结点的左孩子

		// 有右孩子且右孩子大于左孩子
		if (child_index + 1 < this->size_ && this->elements_[child_index] < this->elements_[child_index + 1])
			child_index++; // 移动到右孩子

		// 过了上面这个if之后child_index就是index结点两个孩子结点（如果有）中较大的那一个

		if (this->elements_[index] >= this->elements_[child_index])
			break;

		// 如果父节点小于其孩子结点,靠近树根的节点（父节点）与其子节点交换，“下滤”
		this->swap_(this->elements_[index], this->elements_[child_index]);
	}
}

template<class TData>
inline void MaxHeap<TData>::siftUp_(int index)
{
	for (int parent_index = (index - 1) / 2; parent_index >= 0; index = parent_index, parent_index = (index - 1) / 2)
	{
		if (this->elements_[parent_index] >= this->elements_[index])
			break;

		// 子节点与其父节点交换，“上滤”
		this->swap_(this->elements_[parent_index], this->elements_[index]);
	}
}

template<class TData>
inline void MaxHeap<TData>::swap_(TData& element1, TData& element2)
{
	TData tmp = element1;
	element1 = element2;
	element2 = tmp;
}

template<class TData>
inline MaxHeap<TData>::MaxHeap(int capacity)
{
	this->capacity_ = (capacity > DEFAULT_CAPACITY ? capacity : DEFAULT_CAPACITY);
	this->size_ = 0;
	this->elements_ = new TData[this->capacity_];
	if (!this->elements_)
		throw bad_alloc();
}

template<class TData>
inline MaxHeap<TData>::MaxHeap(TData* elements, int length, int capacity)
{
	// 初始化
	this->capacity_ = (capacity > DEFAULT_CAPACITY ? capacity : DEFAULT_CAPACITY);
	this->size_ = length;

	this->elements_ = new TData[this->capacity_];
	if (!this->elements_)
		throw bad_alloc();

	for (int i = 0; i < length; i++)
	{
		this->elements_[i] = elements[i];
	}

	// 建堆，叶子结点不需要调整，叶子结点会随其父节点的调整而被调整
	// （推荐）自底向上建堆法，时间复杂度T(n) = O(n)，直接对堆进行调整，自下而上执行"下滤"操作
	// （不推荐）自顶向下建堆法，时间复杂度T(n) = O(nlogn)，要先将元素插入堆，然后执行"上滤"操作，劣于上面的建堆法
	for (int i = (this->size_ - 2) / 2; i >= 0; i--)
	{
		// 下滤
		this->siftDown_(i);
	}
}

template<class TData>
inline bool MaxHeap<TData>::insert(const TData& element)
{
	// 合法性判断，堆是否已满
	if (this->size_ == this->capacity_)
		return false;

	// 数组末尾插入元素
	this->elements_[this->size_] = element;

	// 调整堆，“上滤”
	this->siftUp_(this->size_);
	this->size_++;

	// 退出函数
	return true;
}

template<class TData>
inline bool MaxHeap<TData>::pop(TData& element)
{
	// 堆为空则退出
	if (!this->size_)
		return false;

	// 保存堆顶
	element = this->elements_[0];

	// 一维数组尾部元素替换堆顶
	this->elements_[0] = this->elements_[this->size_ - 1];
	this->size_--;

	// 调整堆，“下滤”
	this->siftDown_(0);

	// 退出函数
	return true;
}

template<class TData>
inline bool MaxHeap<TData>::top(TData& element)
{
	// 空堆返回
	if (!this->size_)
		return false;

	// 返回堆顶元素
	element = this->elements_[0];

	// 退出函数
	return true;
}