//author:Mitchell_Donovan
//date:5.25
#include<iostream>
using namespace std;

template<class T>
class MinHeap {
private:
	T* heapArray;//存放堆数据的数组
	int currentSize;//当前堆中的元素个数
	int maxSize;//堆的大小
	//交换位置x和位置y的元素
	void swap(int x, int y) {
		T pass = heapArray[x];
		heapArray[x] = heapArray[y];
		heapArray[y] = pass;
	}
public:
	//构造函数，参数n为堆的大小
	MinHeap(T Array[],int m,int n) {
		if (n <= 0) {
			currentSize = 0;
			maxSize = 0;
			heapArray = new T;
			return;
		}
		currentSize = m;
		maxSize = n;
		heapArray = new T[maxSize];
		for (int i = 0; i < size; i++) {
			heapArray[i] = Array[i];
		}
		for (int i = currentSize / 2 - 1; i >= 0; i--) {
			SiftDown(i);
		}
	}
	//虚析构函数
	virtual ~MinHeap() {
		delete[]heapArray;
	}
	//层序遍历打印堆中元素
	void print() {
		for (int i = 0; i < currentSize; i++) {
			cout << heapArray[i] << " ";
		}
	}
	//判断是否为叶结点
	bool isLeaf(int pos)const {
		return (pos >= currentSize / 2) && (pos < currentSize);
	}
	//返回左孩子的位置
	int LeftChild(int pos)const {
		return 2 * pos + 1;
	}
	//返回右孩子的位置
	int RightChild(int pos)const {
		return 2 * pos + 2;
	}
	//返回父结点的位置
	int Parent(int pos)const {
		return (pos - 1) / 2;
	}
	//向堆中插入新元素
	bool Insert(const T& newNode) {
		if (currentSize == maxSize) {
			return false;
		}
		heapArray[currentSize] = newNode;
		SiftUp(currentSize);
		currentSize++;
		return true;
	}
	//从堆顶删除最小值
	bool RemoveMin() {
		if (currentSize == 0) {
			cout << "Can't Delete!";
			return false;
		}
		else {
			swap(0, --currentSize);
			if (currentSize > 1) {
				SiftDown(0);
			}
			return true;
		}
	}
	//删除给定下标元素,并记录删除的元素
	bool Remove(int pos, T& node) {
		if ((pos < 0) || (pos >= currentSize)) {
			return false;
		}
		node = heapArray[pos];//记录删除的元素
		swap(pos, --currentSize);//用最后的元素替代被删除元素
		if (heapArray[Parent(pos)] > heapArray[pos]) {
			SiftUp(pos);
		}
		else {
			SiftDown(pos);
		}
		return true;
	}
	//从pos开始向上调整
	void SiftUp(int pos) {
		int temppos = pos;
		T temp = heapArray[temppos];
		while ((temppos > 0) && (heapArray[Parent(temppos)] > temp)) {
			heapArray[temppos] = heapArray[Parent(temppos)];
			temppos = Parent(temppos);
		}
		heapArray[temppos] = temp;
	}
	//从pos开始向下筛选
	void SiftDown(int pos) {
		int i = pos;
		int j = LeftChild(i);
		T temp = heapArray[i];
		while (j < currentSize) {
			if ((j < currentSize - 1) && (heapArray[j] > heapArray[j + 1])) {
				j++;
			}
			if (temp > heapArray[j]) {
				heapArray[i] = heapArray[j];
				i = j;
				j = LeftChild(j);
			}
			else {
				break;
			}
		}
		heapArray[i] = temp;
	}
};

template<class T>
void HeapSort(T Array[], int size) {
	MinHeap<T> minHeap(Array, size, size);
	for (int i = 0; i < size; i++) {
		minHeap.Remove(0,Array[i]);
	}
}

int main() {
	int size;
	cout << "数组大小：";
	cin >> size;
	int* test = new int[size];
	memset(test, 0, size * sizeof(int));
	for (int i = 0; i < size; i++) {
		//初始化正序数组
		//test[i] = i;
		//初始化逆序数组
		//test[i] = size - 1 - i;
		//初始化随机数组
		test[i] = rand() % size;
	}
	cout << "排序前：";
	for (int i = 0; i < size; i++) {
		cout << test[i] << " ";
	}
	HeapSort(test, size);
	cout << "排序后：";
	for (int i = 0; i < size; i++) {
		cout << test[i] << " ";
	}
}