#pragma
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define HpDataType int
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int cap;
}Heap;
void HeapInit(Heap* php);//堆的初始化
void HeapDestory(Heap* hp);//堆的銷毀
void HeapPush(Heap* hp, HPDataType x);//堆的插入
void HeapPop(Heap* hp);//堆的刪除
HPDataType HeapTop(Heap* hp);//取堆頂?shù)臄?shù)據(jù)
int HeapSize(Heap* hp);//堆的數(shù)據(jù)個(gè)數(shù)
int HeapEmpty(Heap* hp);//堆的判空

void AdjustUP(HpDataType* arr, int child);//向上調(diào)整
void AdjustDOWN(HpDataType* arr, int size, int parent);//向下調(diào)整
void Swap(HpDataType* a, HpDataType* b);//元素的交換

void AdjustUP(HpDataType* arr,int child)
{
	int parent = (child - 1) / 2;//計(jì)算父節(jié)點(diǎn)下標(biāo)
	while (child>0)//注意這里不能是parent>0
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);//封裝一個(gè)函數(shù)進(jìn)行交換
			child = parent;//更新子節(jié)點(diǎn)
			parent = (child - 1) / 2;//更新父節(jié)點(diǎn)
		}
		else
			break;
	}
}

void AdjustDOWN(HpDataType* arr, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if ((child+1)<size&&arr[child] < arr[child + 1])
			child++;
		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void HeapInit(Heap* ps)//初始化
{
	assert(ps);
	ps->arr = NULL;
	ps->cap = ps->size = 0;
}
void HeapDestory(Heap* hp)//銷毀堆
{
	assert(hp);
	free(hp->arr);
	hp->cap = hp->size = 0;
}
void Swap(HpDataType* a, HpDataType* b)//交換元素
{
	HpDataType c = *a;
	*a = *b;
	*b = c;
}
void AdjustUP(HpDataType* arr,int child)//向下調(diào)整
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
void AdjustDOWN(HpDataType* arr, int size, int parent)//向上調(diào)整
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (arr[child] > arr[child + 1])
			child++;
		if ((child+1)<size&&arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
void HeapPush(Heap* ps, HPDataType x)//插入元素
{
	assert(ps);
	if (ps->size == ps->cap)
	{
		int pnc = ps->cap == 0 ? 4 : 2 * ps->cap;
		HpDataType* pnew = realloc(ps->arr, sizeof(HPDataType)*pnc);
		assert(pnew);
		ps->arr = pnew;
		ps->cap = pnc;
	}
	ps->arr[ps->size] = x;
	ps->size++;
	AdjustUP(ps->arr, ps->size - 1);
}
void HeapPop(Heap* hp)//刪除元素
{
	assert(hp);
	assert(hp->size);
	if (hp->size == 1)
	{
		hp->size--;
		return;
	}
	Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
	hp->size--;
	AdjustDOWN(hp->arr, hp->size, 0);
}
HPDataType HeapTop(Heap* hp)//取堆頂元素
{
	assert(hp);
	assert(hp->size);
	return hp->arr[0];
}
int HeapSize(Heap* hp)//計(jì)算堆元素個(gè)數(shù)
{
	assert(hp);
	return hp->size;
}
int HeapEmpty(Heap* hp)//判斷堆是否為空
{
	assert(hp);
	return hp->size == 0;
}

#include<stdio.h>
#include"Heap.h"
int main()
{
	int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
	int size = sizeof(arr) / sizeof(int);
	for (int i = 0; i < size; i++)
		AdjustUP(arr, i);//該函數(shù)在上文已給出，這里不再展示
	printf("建大堆后：\n");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	return 0;
}

#include<stdio.h>
#include"Heap.h"
int main()
{
	int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
	int size = sizeof(arr) / sizeof(int);
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
		AdjustDOWN(arr, size,i);//該函數(shù)在上文已給出，這里不再展示
	printf("建大堆后：\n");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	return 0;
}

#include<stdio.h>
#include"Heap.h"
int main()
{
	int arr[] = { 1,9,3,7,6,4,2,10,8,5 };
	int size = sizeof(arr) / sizeof(int);
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
		AdjustDOWN(arr, size,i);
	printf("建大堆后：\n");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);
	while (size)
	{
		Swap(&arr[0], &arr[size - 1]);//交換元素
		size--;
		AdjustDOWN(arr, size, 0);
	}
	printf("\n排序后；\n");
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
		printf("%d ", arr[i]);
	return 0;
}

#include<stdio.h>
#include"Heap.h"
void CreateNDate()
{
	//造數(shù)據(jù)，寫入文件中
	int n = 10000;
	srand((unsigned int)time(NULL));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = rand() % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
void PrintTopK(int k)
{
	int* arr = (int*)malloc(sizeof(int) * k);
	assert(arr);
	FILE* fop = fopen("data.txt", "r");
	if (!fop)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < k; i++)//先取出k個(gè)建大堆
		fscanf(fop, "%d", &arr[i]);
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
		AdjustDOWN(arr, k, i);
	int x = 0;
	while (fscanf(fop, "%d", &x) != EOF)
	{
		if (arr[0] > x)
		{
			arr[0] = x;
			AdjustDOWN(arr, k, 0);
		}
	}
	for (int i = 0; i < k; i++)//輸出堆中元素
		printf("%d ", arr[i]);
}
int main()
{
	CreateNDate();
	int k = 0;
	scanf("%d", &k);
	PrintTopK(k);
	return 0;
}