欢迎访问欧博网址!

三公开船:高级数据结构---堆树和堆排序

admin1个月前3

堆树先容:

之前在二叉树的时刻说到过一种特殊的二叉树---完全二叉树(除了最后一层,其他层的每个结点都是满的,且最后一层结点所有靠左排列,这样就可以很利便的用数组来示意,下标从0最先若是父结点索引是i那么它两个子结点的索引就是2i+12i+2,详细的图解见二叉树)。而堆树又是一种特殊的完全二叉树。它的每一个结点值都大于即是或者小于即是其左右结点的值。这里和二叉搜索树不一样,搜索树是左节点小于根,右结点大于根。为什么是大于即是或者小于即是呢,若是大于即是,那么根就是最大的数,这样的就是大顶堆;若是是小于即是,那么根就是最小的数,这样就是小顶堆。

 

堆树的操作:

插入:

堆树插入之后要举行一个堆化的操作,也就是让这棵树知足堆树的性子。

一种是从下往上另一种是从上往下的堆化。

从下往上:

由于完全二叉树用数据组织之后,那么新插入的数据都在最后,然则插入之后,可能就不知足堆树的要求了,以是需要举行更改。以上图的大顶堆为例,我们在最后插入9之后是不知足堆树的性子的。以是我们需要与其父结点举行交流,直到不能再交流位置。不用忧郁数据量大了交流的次数问题,完全二叉树近似一个满二叉树,最多交流logn-1次,想想232的次方是多少,这么大的数据最多才31次。

 

删除:

假设我们要删除掉根结点10,而且删除之后,还要知足堆树的性子。

若何才气删除之后还能保证性子呢。实在就是将要删除的元素和最后一个元素交流之后,删除最后一个元素之后,再从上往下举行堆化的操作。

 

修改数据之后,同样要举行堆化操作,凭据修改之后的数据和他父结点和子结点对照来决定是向上照样向下举行堆化操作。

 

堆排序:

排序算法一种,就是先将数组组织成堆树,再举行排序。那么怎么将一个数组组织成堆树。实在一个数组我们都可以看成是一棵完全二叉树,然则需要将这棵树举行革新,才气获得堆树。若何革新?

好比这个数组:[8 4 20 7 3 1 25 14 17]

树结构:

三公开船:高级数据结构---堆树和堆排序 第1张

 

 我们从最后一个非叶子结点逆向依次举行向下堆化操作,如上图也就是先从7(最后一个非叶子结点)最先向下堆化,7会和17举行对换,然后逆向一次执行,接下来就是20向下执行堆化,会和25对换;然后是4,这个时刻会将适才换上来17换上去,然后4继续和下面对照,和14举行交流.......依次这样操作之后就可以获得一棵堆树了。图解如下:

 

三公开船:高级数据结构---堆树和堆排序 第2张

 

那么获得堆树之后,看起来也是无序的啊,怎么就能实现排序呢?

可以看到堆树的根要么是最大的数要么是最小的数,那我们依次将根取出来,之后再举行堆化操作,又会获得剩余数中最大或者最小的。以是,我们将根与最后一个数交流之后,再举行堆化操作(这里的堆化操作就要除开最后一个点了),然后再新的根和倒数第二个交流再堆化,依次这样操作,后面数逐步的都是有序的了。

图解如下:

三公开船:高级数据结构---堆树和堆排序 第3张

 

代码实现数组转堆树和堆排序(不稳定):

 

    /**
     * 堆排序
     * @param arr
     */
    private static void heapSort(int[] arr) {
        int len = arr.length;
        /**
         * 数组组织堆树,从倒数第一个非叶子结点最先逆向一次举行堆化操作。最后一个叶子结点的父结点就是最后一个非叶子结点。
         * 索引从0最先。两个子结点索引是2i+1和2i+2,以是最后一个非叶子结点的索引就是 len/2 - 1
         */
        for (int i = len / 2 - 1; i >=0 ; i--) { //时间复杂度nlogn
            createMaxHeap(arr, i, len);
        }
        for (int i = len - 1; i > 0 ; i--) { //时间复杂度nlogn
            int maxData = arr[0]; //第一个数最大
            arr[0] = arr[i];
            arr[i] = maxData;
            /**
             * 交流第一个最后一个位置,然后重新组织大顶堆。每循环一次就组织好了一个数的位置,
             * 最后到i为止都是排好序的,堆化的时刻不需要再操作了
             */
            createMaxHeap(arr, 0, i);
        }
    }
    /**
     * 大顶堆组织及堆化历程
     * @param arr
     * @param start  
     * @param end  end之后是已经排好序的,以是需要end下标来判断停止
     */
    private static void createMaxHeap(int[] arr, int start, int end) {
        int parentIndex = start;
        int leftChildIndex = 2 * parentIndex + 1;
        while (leftChildIndex < end) {
            int tempIndex = leftChildIndex;
            //对照左右结点谁大,纪录谁的下标
            if (leftChildIndex + 1 < end && arr[leftChildIndex] < arr[leftChildIndex + 1]) {
                tempIndex = leftChildIndex + 1;
            }
            //父结点比孩子大,不交流
            if (arr[parentIndex] > arr[tempIndex]) {
                return;
            }
            else {
                //交流数据,刷新父结点继续执行堆化操作
                int tempData = arr[parentIndex];
                arr[parentIndex] = arr[tempIndex];
                arr[tempIndex] = tempData;
                parentIndex = tempIndex;
                leftChildIndex = 2 * parentIndex + 1;
            }
        }
    }

 堆树和堆排序在JDK中的应用,可以参见优先行列:java.util.PriorityQueue

,

Sunbet

Sunbet www.6358917.com Sunbet(www.sunbet.in)是进入Sunbet的主力站点。Sunbet开放Sunbet会员开户网址、Sunbet代理开户、Sunbet手机版下载、Sunbet电脑客户端下载等业务。

上一篇 下一篇

猜你喜欢

最新文章
热门文章
热评文章
随机文章
热门标签