堆排序-java

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

---

前言

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

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、堆排序

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 2

3.代码运行结果

1 2 3 

---

总结

上述通过一些堆的基本操作来完成堆排序，后续会专门再写一次博客来详细介绍模拟堆的各种操作。