服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - 堆排序原理及算法代码详解

堆排序原理及算法代码详解

2021-11-15 10:53抽离的心 Java教程

这篇文章主要介绍了堆排序算法的讲解及Java版实现,堆排序基于堆这种数据结构,在本文中对堆的概念也有补充介绍,需要的朋友可以参考下

一、堆排序算法原理和动态图解

将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次最大值。如此反复执行,就能得到一个有序序列了。这个过程其实就是先构建一个最大/最小二叉堆,然后不停的取出最大/最小元素(头结点),插入到新的队列中,以此达到排序的目的。如下图所示:

二、二叉树定义

要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点;深度为 k 的二叉树至多有 2k - 1 个结点;对任何一棵二叉树 t,如果其终端结点数为 n0,度为 2 的结点数为 n2,则n0 = n2 + 1。二叉树又分为完全二叉树(complete binary tree)和满二叉树(full binary tree)。树和二叉树的三个主要差别:

  • 树的结点个数至少为 1,而二叉树的结点个数可以为 0
  • 树中结点的最大度数没有限制,而二叉树结点的最大度数为 2
  • 树的结点无左、右之分,而二叉树的结点有左、右之分

1.满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树,即每一层上的节点数都是最大节点数。如下图b所示:深度为3的满二叉树。

2.完全二叉树:而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树(complete binary tree)。如下图a所示:是一个深度为4的完全二叉树。

三、堆的定义

堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。

堆排序原理及算法代码详解

对于7在数组存放的position=2,而它的子元素6的position=5=2*2[也就是父元素存放的位置]+1、子元素4的position=6=2*2[也就是父元素存放的位置]+2;同样对于11在在数组存放的position=0,而它的子元素10的position=1=2*0[也就是父元素存放的位置]+1、子元素7的position=2=2*0[也就是父元素存放的位置]+2;所以对于i个元素,它的左右子节点在下标以0开始的数组中的位置分别为:2*i+1、2*i+2。那脑补一下,对于不完全二叉树,如果用数组来存放会有什么问题呢?当然是中间有很多空的元素啦,所以说对于不完全二叉树最好是用链表来存储~。

堆的构建过程示例:建堆的核心内容是调整堆,使二叉树满足堆的定义(每个节点的值都不大于其父节点的值)。调堆的过程应该从最后一个非叶子节点开始,假设有数组a = {1, 3, 4, 5, 7, 2, 6, 8, 0}。那么调堆的过程如下图,数组下标从0开始,a[3] = 5开始。分别与左孩子和右孩子比较大小,如果a[3]最大,则不用调整,否则和孩子中的值最大的一个交换位置,在图1中是a[7] > a[3] > a[8],所以a[3]与a[7]对换,从图1.1转到图1.2。

堆排序原理及算法代码详解

二叉堆(英语:binary heap)是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉堆。当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。二叉堆一般用数组来表示。如果根节点在数组中的位置是1,第n个位置的子节点分别在2n和 2n+1。因此,第1个位置的子节点在2和3,第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。如果存储数组的下标基于0,那么下标为i的节点的子节点是2i + 1与2i + 2;其父节点的下标是⌊floor((i − 1) ∕ 2)⌋。函数floor(x)的功能是“向下取整”,或者说“向下舍入”,即取不大于x的最大整数(与“四舍五入”不同,向下取整是直接取按照数轴上最接近要求值的左边值,即不大于要求值的最大的那个值)。比如floor(1.1)、floor(1.9)都返回1。对于堆定义中的堆结构插入元素:对于二叉堆来说,要插入一个新元素其整个过程是怎么样的呢?这里还是以我们之前的那个二叉堆进行说明,以插入"9"为例:

堆排序原理及算法代码详解

目前肯定不满足二叉堆的要求,父接点6是小于新插入的节点9的,所以两者进行位置交换:

堆排序原理及算法代码详解

同样的思路,父节点7比子节点9要小,所以需要调换位置:

堆排序原理及算法代码详解

至此元素插入完成,也符合二叉堆父元素大于子元素的规则,从添加过程中可以发现:只需更改待比较的元素,其它的任何元素位置不需要动,所以效率还是很高的。对于堆定义中的堆结构删除元素:这里以删除根结点为例【因为删除根节点是最重要的,所以以它为例】,整个过程如下:

堆排序原理及算法代码详解

这时当然是不符合二叉堆的规则,接着这样来做:

堆排序原理及算法代码详解

堆排序原理及算法代码详解

同理继续进行处理:

堆排序原理及算法代码详解

堆排序原理及算法代码详解

继续:

堆排序原理及算法代码详解

堆排序原理及算法代码详解

经过这些动作之后就将一个根结点给删除掉了,可以发现其实跟插入一个元素一样,只需更改待比较的元素,其它的任何元素位置不需要动,那像这种每次移除掉最大的值有啥用呢?堆排序就产生了,因为每次从根节点拿肯定是最大的数【以最大堆来说】,这样拿出来的数就成了一个有序的数列了。注意:对于一个很大的堆,这种存储是低效的。因为节点的子节点很可能在另外一个内存页中。b-heap是一种效率更高的存储方式,把每个子树放到同一内存页。如果用指针链表存储堆,那么需要能访问叶节点的方法。可以对二叉树“穿线”(threading)方式,来依序遍历这些节点。

四、堆排序java代码实现

?
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package com.luna.sort;
public class heapsortmaxandmin{
    public static void main(string[] args) {
        int[] array = { 19, 38, 7, 36, 5, 5, 3, 2, 1, 0, 56 };
        system.out.println("排序前:");
        for (int i = 0; i < array.length; i++) {
            system.out.print(array[i] + ",");
        }
        system.out.println();
        system.out.println("分割线---------------");
        heapsort(array);
        system.out.println("排序后:");
        for (int i = 0; i < array.length; i++) {
            system.out.print(array[i] + ",");
        }
    }
    public static void heapsort(int[] array) {
        if (array == null || array.length == 1)
            return;
        buildarraytoheap(array); //将数组元素转化为大顶堆/小顶堆
        for (int i = array.length - 1; i >= 1; i--) {
            // 经过上面的一些列操作,目前array[0]是当前数组里最大的元素,需要和末尾的元素交换,然后拿出最大的元素
            swap(array, 0, i);
            /**
             * 交换完后,下次遍历的时候,就应该跳过最后一个元素,也就是最大的那个
             * 值,然后开始重新构建最大堆堆的大小就减去1,然后从0的位置开始最大堆
             */
//          buildmaxheap(array, i, 0);
            buildminheap(array, i, 0);
        }
    }
    // 构建堆
    public static void buildarraytoheap(int[] array) {
        if (array == null || array.length == 1)
            return;
        //递推公式就是 int root = 2*i, int left = 2*i+1, int right = 2*i+2;
        int cursor = array.length / 2;
        for (int i = cursor; i >= 0; i--) { // 这样for循环下,就可以第一次排序完成
//          buildmaxheap(array, array.length, i);
            buildminheap(array, array.length, i);
        }
    }
    //大顶堆
    public static void buildmaxheap(int[] array, int heapsieze, int index) {
        int left = index * 2 + 1; // 左子节点
        int right = index * 2 + 2; // 右子节点
        int maxvalue = index; // 暂时定在index的位置就是最大值
        // 如果左子节点的值,比当前最大的值大,就把最大值的位置换成左子节点的位置
        if (left < heapsieze && array[left] > array[maxvalue]) {
            maxvalue = left;
        }
        // 如果右子节点的值,比当前最大的值大,就把最大值的位置换成右子节点的位置
        if (right < heapsieze && array[right] > array[maxvalue]) {
            maxvalue = right;
        }
        // 如果不相等说明,这个子节点的值有比自己大的,位置发生了交换了位置
        if (maxvalue != index) {
            swap(array, index, maxvalue); // 就要交换位置元素
            // 交换完位置后还需要判断子节点是否打破了最大堆的性质。最大堆性质:两个子节点都比父节点小。
            buildmaxheap(array, heapsieze, maxvalue);
        }
    }
    //小顶堆
    public static void buildminheap(int[] array, int heapsieze, int index) {
        int left = index * 2 + 1; // 左子节点
        int right = index * 2 + 2; // 右子节点
        int maxvalue = index; // 暂时定在index的位置就是最小值
        // 如果左子节点的值,比当前最小的值小,就把最小值的位置换成左子节点的位置
        if (left < heapsieze && array[left] < array[maxvalue]) {
            maxvalue = left;
        }
        // 如果右子节点的值,比当前最小的值小,就把最小值的位置换成左子节点的位置
        if (right < heapsieze && array[right] < array[maxvalue]) {
            maxvalue = right;
        }
        // 如果不相等说明这个子节点的值有比自己小的,位置发生了交换了位置
        if (maxvalue != index) {
            swap(array, index, maxvalue); // 就要交换位置元素
            // 交换完位置后还需要判断子节点是否打破了最小堆的性质。最小性质:两个子节点都比父节点大。
            buildminheap(array, heapsieze, maxvalue);
        }
    }
    // 数组元素交换
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

大顶堆优化实现算法:

?
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
61
62
63
64
65
import java.util.arrays;
public class maxheapsort {
    private int[] arr;
    public maxheapsort(int[] arr){
        this.arr = arr;
    }
    /**
     * 堆排序的主要入口方法,共两步。
     */
    public void sort(){
        /*
         *  第一步:将数组堆化
         *  beginindex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginindex = (len - 1) >> 1;
        for(int i = beginindex; i >= 0; i--){
            maxheapify(i, len);
        }
        /*
         * 第二步:对堆化数据排序
         * 每次都是移出最顶层的根节点a[0],与最尾部节点位置调换,同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素,使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxheapify(0, i - 1);
        }
    }
    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /**
     * 调整索引为 index 处的数据,使其符合堆的特性。
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆(数组)的长度
     */
    private void maxheapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cmax = li;             // 子节点值最大索引,默认左子节点。
        if(li > len) return;       // 左子节点索引超出计算范围,直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点,哪个较大。
            cmax = ri;
        if(arr[cmax] > arr[index]){
            swap(cmax, index);      // 如果父节点被子节点调换,
            maxheapify(cmax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }
    /**
     * 测试用例
     * 输出:
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(string[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};       
        new maxheapsort(arr).sort();       
        system.out.println(arrays.tostring(arr));
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/u011635492/article/details/83046477

延伸 · 阅读

精彩推荐