大顶堆升序、小顶堆降序的堆排序(以Java描述为例版本)

简介: 大顶堆升序、小顶堆降序的堆排序(以Java描述为例版本)

一、定义

  1. 堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
  2. 二叉树的相关性质当用数组来模拟二叉树的性质的时候,索引为i的结点的左孩子和右孩子对应的数组索引下标依次为:
  • 根节点:i ii
  • 左孩子:2 ∗ i + 1 2 * i + 12i+1
  • 右孩子: 2 ∗ i + 2 2 * i + 22i+2
  1. 数组长度l e n g t h lengthlength,那么最后一个非叶子节点为l e n g t h / 2 − 1 length/2-1length/21

可以分两种情形考虑:

①堆的最后一个非叶子节点若只有左孩子

②堆的最后一个非叶子节点有左右两个孩子

完全二叉树的性质之一是:如果节点序号为i ii,在它的左孩子序号为2 i + 1 2i+12i+1,右孩子序号为2 i + 2 2i+22i+2

对于①左孩子的序号为n-1,则n − 1 = 2 ∗ i − 1 n-1=2*i-1n1=2i1,推出i = n / 2 − 1 i=n/2-1i=n/21

对于②左孩子的序号为n-2,在n − 2 = 2 ∗ i − 1 n-2=2*i-1n2=2i1,推出i = ( n − 1 ) / 2 − 1 i=(n-1)/2-1i=(n1)/21;右孩子的序号为n-1,则

n − 1 = 2 ∗ i + 2 n-1=2*i+2n1=2i+2,推出i = ( n − 1 ) / 2 − 1 i=(n-1)/2-1i=(n1)/21

很显然,当完全二叉树最后一个节点是其父节点的左孩子时,树的节点数为偶数;当完全二叉树最后一个节点是其父节点的右孩子时,树的节点数为奇数。

根据java语法的特征,整数除不尽时向下取整,则若n为奇数时(n-1)/2-1=n/2-1。

因此对于②最后一个非叶子节点的序号也是n/2-1。

得证。

  1. 同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

    该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:
    大顶堆:a r r [ i ] > = a r r [ 2 i + 1 ] arr[i]>=arr[2i+1]arr[i]>=arr[2i+1] && a r r [ i ] > = a r r [ 2 i + 2 ] arr[i] >= arr[2i+2]arr[i]>=arr[2i+2]
    小顶堆:a r r [ i ] < = a r r [ 2 i + 1 ] arr[i]<=arr[2i+1]arr[i]<=arr[2i+1] && a r r [ i ] < = a r r [ 2 i + 2 ] arr[i] <= arr[2i+2]arr[i]<=arr[2i+2]

二、第一阶段:建大顶堆

第一步给定无序数组初始化:

第二步开始构建大顶堆:

2.1 此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的6结点),从左至右,从下至上进行调整。

2.2. 找到第二个非叶节点4,由于[4,9,8]中9元素最大,4和9交换。

2.3 这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6。

2.4 此时,初始化大顶堆以构建完成,但此时整体还是无序的,因为左右孩子的值没有比较过只是根节点和孩子节点之间的比较,不是左孩子和右孩子之间的比较。

这个时候的大根堆是这样子的

三、第二阶段:大顶堆排序

将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

重新调整结构,使其继续满足堆定义,此时堆为[8,6,4,5]

再将堆顶元素8与末尾元素5进行交换,得到第二大元素8。

后续再构建堆[6,5,4]

再将堆顶元素6与末尾元素4进行交换,得到第三大元素6。

然后4和5再交换,继续构建大顶堆 这个时候会是[5,4]

然后继续交换,5下沉到此时的最后面,变成了[4],得到第四大元素5

此时已经全部筛选完,是有序的了。

再简单总结下堆排序的基本思路:

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

附上代码,这个是可以自由输入的。

package heapsort;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/30-10:50
 */
public class BigHeapSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入要排序的数组的长度:");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入要排序的数组:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        scanner.close();
        buildHeap(arr);
    }
    public static void buildHeap(int[] arr) {
        int length = arr.length;
        // 先构建一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maximumHeap(arr,i, arr.length);
        }
        // 排序
        for (int i = arr.length - 1; i >= 0; i--) {
            // 过程中的每一步数组元素的变化过程
             System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(arr,0, length);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void maximumHeap(int[] arr,int i ,int length) {
        int tmp = arr[i];
        for (int j = 2 * i + 1;j < length; j = j * 2 + 1) {
            // 右孩子比左孩子要大,那么指向右孩子
            if (j+1 < length && arr[j] < arr[j+1]) {
                j++;
            }
            // 右孩子比根节点要大,一直往下探寻
            if (arr[j] > tmp) {
                arr[i] = arr[j];
                i = j;
            }
            //将temp放到最终位置
            arr[i] = tmp;
        }
    }
    public static void swap(int[] arr,int a,int b) {
       int tmp = arr[a];
       arr[a] = arr[b];
       arr[b] = tmp;
    }
}

测试用例

这个是定义好自行修改数组的。

package heapsort;
import java.util.Arrays;
/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/30-10:50
 */
public class BigHeapSort {
    public static void main(String[] args) {
        int[] arr = {5,4,8,9,6};
        buildHeap(arr);
    }
    public static void buildHeap(int[] arr) {
        int length = arr.length;
        // 先构建一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maximumHeap(arr,i, arr.length);
        }
        // 排序
        for (int i = arr.length - 1; i >= 0; i--) {
            // 过程中的每一步数组元素的变化过程
             System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(arr,0, length);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void maximumHeap(int[] arr,int i ,int length) {
        int tmp = arr[i];
        for (int j = 2 * i + 1;j < length; j = j * 2 + 1) {
            // 右孩子比左孩子要大,那么指向右孩子
            if (j+1 < length && arr[j] < arr[j+1]) {
                j++;
            }
            // 右孩子比根节点要大,一直往下探寻
            if (arr[j] > tmp) {
                arr[i] = arr[j];
                i = j;
            }
            //将temp放到最终位置
            arr[i] = tmp;
        }
    }
    public static void swap(int[] arr,int a,int b) {
       int tmp = arr[a];
       arr[a] = arr[b];
       arr[b] = tmp;
    }
}

如果只想看最后结果,可以在buildHeap()函数里把详细过程的输出打印代码注释掉就可以只看最后排序结果了。

package heapsort;
import java.util.Arrays;
import java.util.Scanner;
/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/30-10:50
 */
public class BigHeapSort {
    public static void main(String[] args) {
        int[] arr = {5,4,8,9,6};
        buildHeap(arr);
    }
    public static void buildHeap(int[] arr) {
        int length = arr.length;
        // 先构建一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maximumHeap(arr,i, arr.length);
        }
        // 排序
        for (int i = arr.length - 1; i >= 0; i--) {
            // 过程中的每一步数组元素的变化过程
            // System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(arr,0, length);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void maximumHeap(int[] arr,int i ,int length) {
        int tmp = arr[i];
        for (int j = 2 * i + 1;j < length; j = j * 2 + 1) {
            // 右孩子比左孩子要大,那么指向右孩子
            if (j+1 < length && arr[j] < arr[j+1]) {
                j++;
            }
            // 右孩子比根节点要大,一直往下探寻
            if (arr[j] > tmp) {
                arr[i] = arr[j];
                i = j;
            }
            //将temp放到最终位置
            arr[i] = tmp;
        }
    }
    public static void swap(int[] arr,int a,int b) {
       int tmp = arr[a];
       arr[a] = arr[b];
       arr[b] = tmp;
    }
}

小顶堆的只需要修改那个maximumHeap()函数里面的arr[j]和tmp的比较语句,还有左孩子和右孩子的比较语句,把比较的大于小于号分别改为相反的就行。

package heapsort;
import java.util.Arrays;
/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/30-10:50
 */
public class BigHeapSort {
    public static void main(String[] args) {
        int[] arr = {5,4,8,9,6};
        buildHeap(arr);
    }
    public static void buildHeap(int[] arr) {
        int length = arr.length;
        // 先构建一个大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            maximumHeap(arr,i, arr.length);
        }
        // 排序
        for (int i = arr.length - 1; i >= 0; i--) {
            // 过程中的每一步数组元素的变化过程
             System.out.println(Arrays.toString(arr));
            swap(arr,0,i);
            length--;
            maximumHeap(arr,0, length);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void maximumHeap(int[] arr,int i ,int length) {
        int tmp = arr[i];
        for (int j = 2 * i + 1;j < length; j = j * 2 + 1) {
            // 右孩子比左孩子要大,那么指向右孩子
            if (j+1 < length && arr[j] > arr[j+1]) {
                j++;
            }
            // 右孩子比根节点要大,一直往下探寻
            if (arr[j] < tmp) {
                arr[i] = arr[j];
                i = j;
            }
            //将temp放到最终位置
            arr[i] = tmp;
        }
    }
    public static void swap(int[] arr,int a,int b) {
       int tmp = arr[a];
       arr[a] = arr[b];
       arr[b] = tmp;
    }
}


相关文章
|
20天前
|
JavaScript NoSQL Java
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
168 96
接替此文【下篇-服务端+后台管理】优雅草蜻蜓z系统JAVA版暗影版为例-【蜻蜓z系列通用】-2025年全新项目整合搭建方式-这是独立吃透代码以后首次改变-独立PC版本vue版搭建教程-优雅草卓伊凡
|
5月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
132 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
监控 Java 中间件
8G的容器Java堆才4G怎么就OOM了?
本文记录最近一例Java应用OOM问题的排查过程,希望可以给遇到类似问题的同学提供参考。
|
3月前
|
算法 Java API
如何使用Java开发获得淘宝商品描述API接口?
本文详细介绍如何使用Java开发调用淘宝商品描述API接口,涵盖从注册淘宝开放平台账号、阅读平台规则、创建应用并申请接口权限,到安装开发工具、配置开发环境、获取访问令牌,以及具体的Java代码实现和注意事项。通过遵循这些步骤,开发者可以高效地获取商品详情、描述及图片等信息,为项目和业务增添价值。
127 10
|
3月前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
104 5
|
4月前
|
安全 Java 编译器
Java对象一定分配在堆上吗?
本文探讨了Java对象的内存分配问题,重点介绍了JVM的逃逸分析技术及其优化策略。逃逸分析能判断对象是否会在作用域外被访问,从而决定对象是否需要分配到堆上。文章详细讲解了栈上分配、标量替换和同步消除三种优化策略,并通过示例代码说明了这些技术的应用场景。
Java对象一定分配在堆上吗?
|
4月前
|
Java Linux Windows
如何查看已安装的 Java 版本
要查看已安装的 Java 版本,打开命令提示符或终端,输入 `java -version`,回车后即可显示当前系统中 Java 的版本信息。
1488 1
|
4月前
|
Ubuntu Java Linux
如何检查 Java 版本是否兼容
要检查Java版本是否兼容,可在命令行输入“java -version”查看当前安装的Java版本,然后对比目标应用所需的Java版本,确保其满足要求。
167 1
|
5月前
|
缓存 Java Maven
java: 警告: 源发行版 11 需要目标发行版 11 无效的目标发行版: 11 jdk版本不符,项目jdk版本为其他版本
如何解决Java项目中因JDK版本不匹配导致的编译错误,包括修改`pom.xml`文件、调整项目结构、设置Maven和JDK版本,以及清理缓存和重启IDEA。
120 1
java: 警告: 源发行版 11 需要目标发行版 11 无效的目标发行版: 11 jdk版本不符,项目jdk版本为其他版本
|
5月前
|
存储 算法 Java
🏗️Java零基础:深入了解Java 堆
【10月更文挑战第2天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
55 3

热门文章

最新文章