堆排序-java

这次主要讲了堆排序和堆的基本构造，下一期会详细讲述堆的各种基本操作。

文章目录

前言

一、堆排序

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个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，每一层最多有 $2^{n-1}$ 个结点，除了最后一层，其余层的结点数都是满的，且最后一层从左往右依次分布。

堆是一种基于完全二叉树的数据结构。可以分为大根堆，小根堆。

大根堆：每个结点的值都大于或者等于其左右孩子的值。

小根堆：每个结点的值都小于或者等于其左右孩子的值。

二、算法思路

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);}}
}