2022-01-02每日刷题打卡

堆是实现优先队列的一种数据结构，是一种特殊的完全二叉树。

堆排序的模板应当背下来。

#include 
using namespace std;

const int N = 1e5 + 10;
int q[N];

void heap_adjust(int q[], int i, int n)
{
	for(int j = i*2+1; j < n; j = j*2+1)
	{
		if(j < n-1 && q[j] < q[j+1]) j++;
		if(q[i] >= q[j]) break;
		swap(q[i], q[j]);
		i = j;	
	}	
}

void heap_sort(int q[], int n)
{
	//建立初始堆 
	for(int i = n/2 - 1; i >= 0; i--) heap_adjust(q, i, n);
	//排序
	for(int i = n-1; i > 0; i--)
	{
		swap(q[0], q[i]);
		heap_adjust(q, 0, i);	
	} 
}

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	
	for(int i = 0; i < n; i++) scanf("%d", &q[i]);
	
	heap_sort(q, n);

	for(int i = 0; i < m; i++) printf("%d ", q[i]);	
	
	return 0;
}