堆（以大根堆为例）

⬅ 返回

1、定义

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为 O(nlogn)， 它也是不稳定排序。

2、堆排序步骤

一：构造大根堆

二：排序

总结：

3、题型

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数，表示整数数列。

输出格式

共一行，包含 m 个整数，表示整数数列中前 m 小的数。

4、代码

#include<iostream>
using namespace std;
const int N = 1e6+10;
int heap[N];//堆用一维数组存储 下标从1开始
int length;//记录堆的有效长度
----------------------------------------------------------
void down(int u)//下坠
{
	int t = u;//用t记录最小点的编号
	
	//有左儿子，并且左儿子比t节点的值小，更新t
	if(2*u<=length && heap[2*u]<heap[u])
			t=2*u;
			
	 //有右儿子，并且右儿子比t节点的值小，更新t
	if(2*u+1<=length &&  heap[2*u+1]<heap[t])
			t=2*u+1;
	
	if(t!=u) //如果待调整点不是最小的
	{
		swap(heap[t],heap[u]);//和最小的交换
		down(t);//递归处理
	}
}
-------------------------------------------······················
int main(){
	
	int n,m;
	cin>>n>>m;
	length=n;//开始时，右边界是数组边界
	
	
	for(int i=1;i<=n;i++)
	{
		cin>>heap[i];
	}
	
	//从第一个非叶节点开始，从右到左，从下到上处理每个节点
	for(int i=n/2;i>=1;i--)
			down(i);
			
	//输出m个最小值
	while(m--)
	{
		cout<<heap[1]<<" ";//堆顶保存的最小值，输出堆顶
		swap(heap[1],heap[legth]);//将堆顶和右边界交换
		length--;//右边界左移
		down(1);//从新处理堆顶
	}
} 
-----------------------------------------------------------------
void up(int u)//小元素上升 如果父节点比当前结点大 swap 
{
	int t=u; 
	if(u/2!=0 && heap[u/2]>heap[u])
	{
		swap(heap[u/2],heap[u]);
		t=u/2;
	}
	up(t);
}