void AdjustUp(int* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			swap(a[parent], a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int* a,int size, int parent) // size 是總大小，parent是從哪里開始向下調整 
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
			child++;
		if (a[child] > a[parent])
		{
			swap(a[child], a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void Print_Heap_Topk(int* a, int n, int k)
{
	int* KMaxHeap = new int[k];   // 最大堆存最小的K個數(shù)
	for (int i = 0; i < k; ++i)
	{
		KMaxHeap[i] = a[i];
	}
	for (int i = (k - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(KMaxHeap, k, i);
	}
	for (int i = k; i < n; ++i)
	{
		if (a[i] < KMaxHeap[0])
			KMaxHeap[0] = a[i];
		AdjustDown(KMaxHeap, k, 0);
	}
	for (int i = 0; i < k; ++i)
	{
		cout << KMaxHeap[i] << " ";
	}
	cout << endl;
}
void test_topk()
{
	int n = 10000;
	int* a = new int[n];
	srand(time(0));
	for (int i = 0; i < n; ++i)
		a[i] = rand() % 1000000;
	a[5] = 1000000 + 1;
	a[1231] = 1000000 + 2;
	a[531] = 1000000 + 3;
	a[5121] = 1000000 + 4;
	a[120] = 1000000 + 5;
	a[99] = 1000000 + 6;
	a[0] = 1000000 + 7;
	a[76] = 1000000 + 8;
	a[423] = 1000000 + 9;
	a[3144] = 1000000 + 10;
	a[333] = -100;
	a[999] = -200;
	a[777] = -500;
	a[888] = -800;
	a[111] = -1000;
	a[798] = -1;
	a[1111] = -250;
	a[2222] = -350;
	a[3333] = -450;
	a[4444] = -550;
	Print_Heap_Topk(a, n, 10);
}
int main()
{
	test_topk();
	return 0;
}