当前位置:   article > 正文

堆排序算法实现

堆排序算法实现

堆排序:结构逻辑上是完全二叉树,但是可以使用顺序存储来实现

一些二叉树的区别:

二叉树:度数最大为2并且每个子树也是二叉树

二叉树:每层节点都是满的,没有空缺,也就是,叶子节点只能出现在最后一层
在这里插入图片描述

完全二叉树:限制条件比满二叉树弱化,只需要前k-1层是满二叉树结构,最后一层的叶子节点都靠左排列,右侧可以出出现连续缺失(一个学序列可以按照编号一一对应上满二叉树的节点编号)

在这里插入图片描述

以下不是满二叉树结构:

在这里插入图片描述在这里插入图片描述
排序二叉树: 二叉树的基础上,加上 中序遍历是有序输出这一要求
平衡二叉树:排序二叉树的基础上,加上要求左右子树的深度差的绝对值只能是0或者1

现在回到堆排序:
具体满足什么条件的才是堆呢?
以大根堆为例: 对于每棵子树,都满足 根与左右孩子节点相比中最大的元素

堆排序的算法流程:

  1. 堆的初始化(将输入序列调整为符合堆的性质)
  2. 输出堆顶元素(将堆顶元素与堆尾元素交换,堆的大小-1)
  3. 调整堆结构
  4. 重复2 3 ,直到全部输出(堆大小变为0)

假设堆的编号是从0 开始
那么编号i的节点 (这规律没啥记忆的,画几个圈看下规律即可)
父节点:(i-1)/2
左孩子: 2*i+1
右孩子:2*i+2
最后一个非叶子节点编号: 假设堆共有n个节点,那么最后一个非叶子节点编号为 n/2-1

java代码实现:


/**
 * @author  wangwei
 * @date     2019/3/9 8:52
 * @classDescription   完全二叉树:比满二叉树条件稍弱
 *                      一共k层的完全二叉树,只要求第k-1层是满的
 *                      并且第k层的节点集中在左侧,也就是右侧可能出现连续缺失情况
 *
 *                      大顶堆:根最大,每课子树只保证根大于左孩子,大于右孩子,但是不保证左右孩子之间的大小关系
 *
 *          给定序列,如何判断是否为堆呢?
 *          将序列按照层次遍历的形式,构建完全二叉树,观察即可
 *          比如:1  4 3  7 8 5
 *              1
 *             / \
 *            4   3
 *          /  \  / \
 *          7   8 5
 *    显然是小根堆
 *
 *    堆排序思想:
 *    1.以初始关键字序列,构建堆
 *    2.输出堆顶最小元素
 *    3,调整剩余元素,使其成为新堆
 *    4,重复2,3 直到n个元素全部输出,得到一个有序序列
 *
 *    如果输入为数组:
 *    当前为i  (i从1开始)
 *    则左孩子为 2*i
 *     右孩子:   2*i+1
 *
 *
 *     堆调整:将堆顶输出,最后孩子放置在堆顶,对剩余元素进行调整
 *            新堆顶与左右孩子比较,
 *           与较小孩子交换
 *           直到调整到叶子节点或者是 比左右孩子都小时,停止调整
 *      如何初始化序列建堆:从最后一个非叶子节点开始,向上调整,直到根节点
 *      //      最后一个非叶子节点是  n/2  向下取整
 *
 *
 *
 *      问题:为什么堆适合线性存储
 *      答:因为堆是完全二叉树结构,堆中元素的位置能根据父节点索引计算得到,
 *      所以不需要左右指针也可以找到子节点的位置
 *
 */
public class HeapSort {
   

    public  void init(int []array){
   
        if(null==array||0==array.length){
   
            return;
        }
        // 注意:计算  左孩子 2*i  ,这里表示编号是从1 开始
        //               数组从0开始,则需要是 2*i+1
        //               右孩子:2*i+2
        //  最后一个非叶子节点 索引:  n/2-1
        // 最后一个非叶子节点,可能只有左孩子
        for(int index=array.length/2-1<
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/615298
推荐阅读
相关标签
  

闽ICP备14008679号