#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
#include <vector>

using namespace std;

class HeapSort
{
public:
	vector<int> sort_data;             //原数组
	vector<int> sorted_data;		   //排序后的数组	
	int num_unzero;					   //非0元素的个数
	HeapSort()
	{
		sort_data = generate_rand_queue(100);
		int idx = 0;
		sorted_data = heapSort(sort_data);
		for (; idx < 100; ++idx)
		{
			if (sorted_data[idx] > 0)
				break;
		}
		num_unzero = 100 - idx;
	}

	HeapSort(vector<int> rand_date) :sort_data(rand_date)
	{
		int idx = 0;
		sorted_data = heapSort(sort_data);
		int data_num = sorted_data.size();
		for (; idx < data_num; ++idx)
		{
			if (sorted_data[idx] > 0)
				break;
		}
		num_unzero = data_num - idx;
	}

private:
	vector<int> generate_rand_queue(const int& num)
	{
		vector<int> res;
		srand((int)time(NULL));
		for (int i = 0; i < num; ++i)
			res.push_back(rand() % 30);
		return res;
	}

	void moveDown(vector<int>& arr, int first, int last)
	{
		int curIndex = first * 2 + 1;
		while (curIndex <= last)
		{
			if (curIndex < last && arr[curIndex] < arr[curIndex + 1])
				curIndex++;

			if (arr[first] < arr[curIndex])
			{
				swap(arr[first], arr[curIndex]);
				first = curIndex;
				curIndex = 2 * first + 1;
			}
			else
				break;
		}
	}
	void buildHeap(vector<int>& arr)
	{
		int i = arr.size() / 2 - 1;
		while (i >= 0)
		{
			moveDown(arr, i, arr.size() - 1);
			i--;
		}
	}
	vector<int>& heapSort(vector<int>& arr)
	{
		buildHeap(arr);
		int first = 0, last = arr.size() - 1;
		while (first <= last)
		{
			swap(arr[first], arr[last]);
			last--;
			moveDown(arr, first, last);
		}
		return arr;
	}
};


int main()
{
	HeapSort hp;
    return 0;
}