这次主要讲了堆排序和堆的基本构造，下一期会详细讲述堆的各种基本操作。
文章目录
前言
一、堆排序
1.题目描述
2.堆
二、算法思路
1.堆的存储
2. 结点下移down
3.结点上移up
4.堆的基本操作
5.堆的初始化
三、代码如下
1.代码如下：
2.读入数据：
3.代码运行结果
总结
前言
这次主要讲了堆排序和堆的基本构造，下一期会详细讲述堆的各种基本操作。
提示：以下是本篇文章正文内容，下面案例可供参考
一、堆排序
1.题目描述
输入一个长度为 n 的整数数列，从小到大输出前 m小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤100000，
1≤数列中元素≤1000000000
2.堆
图2.1完全二叉树示意图
完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，每一层最多有个结点，除了最后一层，其余层的结点数都是满的，且最后一层从左往右依次分布。
堆是一种基于完全二叉树的数据结构。可以分为大根堆，小根堆。
大根堆：每个结点的值都大于或者等于其左右孩子的值。
小根堆：每个结点的值都小于或者等于其左右孩子的值。
二、算法思路
1.堆的存储
图1.1堆的存储示例图
我们用一个一维数组来存储堆的值，下标来表示是哪个结点，下标为1就存储根节点的值，下标为2存储它的左孩子的值，下标为3存储它的右孩子的值，我们就可以类比推理出任一结点的左孩子和右孩子的下标。例如下标为x的结点，它的左孩子在数组中存储的下标就是2x，它的右孩子在数组中存储的下标是2x+1。（注：下标从1开始）
2. 结点下移down
图2.1示例一
我们以一个小根堆为例，父结点的值要小于它的左右孩子结点。当我们将根节点修改为6后，此时小根堆的性质就被破坏了，那么我们就要对这个小根堆进行调整。
图2.2示例二
此时，我们需要与根节点的左右孩子进行比较，得出6的左孩子3是3个点中最小的，进行交换。此时小根堆的性质还没维护好，此时我们还需要将6跟它的左右孩子进行比较，得出它的左孩子3是最小的，再将6和它的左孩子进行交换，此时检查后发现，符合小根堆的性质。即我们将某一个值变大，那么在小根堆中它就要下移。
//传入结点下标
public static void down(int x){
int temp = x;
//两个if语句来找出3个结点中最小的结点的下标
if(2 * x <= size && heap[2* x] < heap[temp]){
temp = 2 * x;
}
if (2 * x + 1 <= size && heap[2*x + 1] < heap[temp]){
temp = 2 * x + 1;
}
//说明此时结点不是最小值，进行交换，再递归处理看是否还需要交换
if(temp != x){
int t = heap[temp];
heap[temp] = heap[x];
heap[x] = t;
down(temp);
}
}
3.结点上移up
图3.1结点上移示例
当我们把最右下角的结点值修改为2，此时小根堆的性质被破坏。我们把2和它的父结点进行比较得出2就是3个结点的最小值，2跟它的父结点进行交换；然后。此时的2再跟它的父结点进行比较得出2是3个结点中的最小值，将2跟它的父结点进行交换。此时检查后，发现符合小根堆的性质。可以看出如果值变大的话，我们需要进行结点上移操作，即结点上移来维护小根堆的性质。
up操作我们只需要跟父亲结点比就可以了。
//传入结点下标
public static void up(int x){
int t = x;
int temp = x / 2;
if(temp >= 1 && heap[temp] > heap[t]){
t = temp;
}
if(t != x){
int arr = heap[t];
heap[t] = heap[x];
heap[x] = arr;
up(t);
}
}
4.堆的基本操作
我们引入一个一维整型数组heap来存储堆，一个整型变量size来表示堆中最后一个元素的下标或者堆中的元素个数。（数组下标0不用，我们从下标为1开始存储）
向堆中插入一个数：我们则直接在数组最后一个元素后面加入一个值，最后一个元素的下标为size即head[++size] = x;此时我们要预防堆的性质是否被破坏，那么我们直接执行结点上移操作即可。up(size)；
求堆中的最小值：小根堆中的根节点就是堆中的最小值即head[1]。
删除最小值：即我们将根节点删除了，在一维数组中第一个元素我们很难删除，但是最后一个元素很容易删除，我们只需要用最后一个元素将根节点覆盖，然后将堆的大小减1即head[1] = head[size]；dowx(1)来让结点下移来维护堆的性质。
删除任意一个元素：删除下标为k的结点值，我们还是用堆中的最后一个元素将这个元素值进行覆盖，然后将堆的大小减1即head[k] = head[size]；size--；如果结点值变大的进行结点下移，结点值变小进行结点下移，那么我们直接down(k)；up(k)；因为它最后只会执行这两个操作中的一个，这样小根堆的性质也会被维护。
修改任意一个元素：修改下标为k的元素为x，那么我们需要head[k] = x；如果结点值变大的进行结点下移，结点值变小进行结点下移，那么我们直接down(k)；up(k)；因为它最后只会执行这两个操作中的一个，这样小根堆的性质也会被维护。
5.堆的初始化
图5.1示例图
因为我们需要初始化建造一个小根堆，那么我们只需要从倒数第2层开始每一个结点进行结点下移操作就可以了。最后一层是叶子节点不需要进行结点下移操作。
for(int i = 1; i <= n; i++){
heap[i] = sc.nextInt();
}
size = n;
//初始化建堆
for(int i = n / 2;i > 0;i--){
down(i);
}三、代码如下
1.代码如下：
import java.io.*;
import java.util.*;
public class 堆排序 {
static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N = 100010;
//存储堆
static int[] heap = new int[N];
//堆中最后一个结点的下标，也是堆中元素的个数
static int size = 0;
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(br);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 1; i <= n; i++){
heap[i] = sc.nextInt();
}
size = n;
//初始化建堆
for(int i = n / 2;i > 0;i--){
down(i);
}
while (m-- > 0){
//打印最小值
pw.print(heap[1] +" ");
//删除堆中的根节点，然后维护小根堆性质
heap[1] = heap[size];
size--;
down(1);
}
pw.flush();
}
//传入结点下标
public static void down(int x){
int temp = x;
//两个if语句来找出3个结点中最小的结点的下标
if(2 * x <= size && heap[2* x] < heap[temp]){
temp = 2 * x;
}
if (2 * x + 1 <= size && heap[2*x + 1] < heap[temp]){
temp = 2 * x + 1;
}
//说明此时结点不是最小值，进行交换，再递归处理看是否还需要交换
if(temp != x){
int t = heap[temp];
heap[temp] = heap[x];
heap[x] = t;
down(temp);
}
}
//传入结点下标
public static void up(int x){
int t = x;
int temp = x / 2;
if(temp >= 1 && heap[temp] > heap[t]){
t = temp;
}
if(t != x){
int arr = heap[t];
heap[t] = heap[x];
heap[x] = arr;
up(t);
}
}
}
2.读入数据：
5 3
4 5 1 3 23.代码运行结果
1 2 3 总结
上述通过一些堆的基本操作来完成堆排序，后续会专门再写一次博客来详细介绍模拟堆的各种操作。
![[SQL-SERVER：数据库安全及维护]：MSSM工具进行附加还原备份等操作](https://img-blog.csdnimg.cn/direct/124c12fe328c4bc198e57189dacb8d76.png)
