精华内容
下载资源
问答
  • 图解大根堆的堆排序

    千次阅读 多人点赞 2020-03-30 22:09:55
    文章目录1 大根堆2 创建堆,heapInsert 1 大根堆 进行堆排序之前,需要先明确大根堆的概念,大根堆就是根节点是整棵树的最大值(根节点大于等于左右子树的最大值),对于他的任意子树,根节点也是最大值。大根堆有两个...

    1 大根堆

    进行堆排序之前,需要先明确大根堆的概念,大根堆就是根节点是整棵树的最大值(根节点大于等于左右子树的最大值),对于他的任意子树,根节点也是最大值。大根堆有两个操作,一个创建堆heapInsert时间复杂度是O(N),还有一个操作是当大根堆里的某个节点的值,发生变化的时候,需要对这个大根堆进行调整,每一次调整时间复杂度是O(lg(N)),调整的次数是跟这个堆的高度有关。这里总结了一下,使用了很多图,应该很简单就能立即

    2 创建堆,heapInsert

    这里堆放到数组里进行存储的,首先堆是一棵完全二叉树。比如一棵树有N个元素,存放在数组里分别对应0~N-1,假设数组中从0到i-1位置的元素是一个大根堆,然后把第i个位置的元素插入大根堆里,构造一个新的大根堆,就需要从第i个位置的元素开始,依次看它的父节点的值是否小于它,如果小于就进行交换,直到它的父节点不小于它,或者到了该大根堆的最顶端的根节点,这一次过程才算彻底结束。
    上面说的不太清楚,看下面具体的例子
    下面这个是一个随机生成的数组。
    在这里插入图片描述
    它对应的完全二叉树的结构:
    在这里插入图片描述
    index是数组的下标,从0开始,现在开始创建大根堆,index=0;

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=1
    把43插入到大根堆里,43的父节点为9,43大于9,所以9要和43交换位置,然后构成新的大根堆。

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=2
    把-54插入进来,由于-54小于它的父节点43,所以不进行交换

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=3
    插入4,由于4小于它的父节点,所以不进行交换。

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=4
    插入-13,由于-13小于它的父节点,所以不交换。

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=5
    插入10,由于10比它的父节点-54大,所以进行交换。

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    index=6
    插入36,36比它的父节点10大,进行交换

    大根堆结构数组
    在这里插入图片描述在这里插入图片描述

    以上就是建立整个大根堆的过程。

     public static void  heapInsert(int[] arr,int index){
            /*
            对第i个元素进行插入,前提是前i-1个元素已经变成了大根堆,
            然后把最后面的一个元素,插入进去,进行调整,把它变成大根堆,它调整的过程是看第i个元素的父节点,
            是否比它小,如果小的话,就进行交换,然后再网上看父节点,直到它的父节点比他大,或者到了整棵树的根节点。
            * */
            while(arr[index]>arr[(index-1)/2]){
                // while 循环的终止条件是当前节点比它的父节点小,当index为0的时候,(index-1)/2也为0,循环也会终止。
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
        // swap函数用于交换两个不同位置的元素
        public static void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    

    3 调整堆 heapify

    数组中对应的大根堆的长度为heapSize,则从0到heapSize-1,是大根堆里的元素,当数组中下标为index的元素的值发生了变化,就要对这个堆进行调整,保证它还是大根堆,具体过程是:将index对应的元素和它的左右子节点的值进行比较,如果比它小的话,就把index对应的元素和它的左右子节点中最大的值进行交换,交换后对他的子节点也执行这个过程。

    public static void heapify(int[] arr,int index,int heapSize){
            // 要调整的节点的左孩子节点
            int left=2*index+1;
            // 0到heapSize-1,是大根堆,所以当left等于或者大于heapSize的时候,说明index对应的节点就是叶子节点。
            while(left<heapSize){
                // 寻找左子节点和右子节点的最大值,left+1 为右子节点,当右子节点存在且右子节点的值大于左子节点的值的时候,largest才是右子节点。
                int largest=left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
                // 把左右子节点中的最大值和父节点进行比较,来判断是否进行交换
                largest = arr[largest] > arr[index] ? largest : index;
                // 如果当前节点比它的左右子节点都大的话,就没有必要再进行交换了。
                if (largest == index) {
                    break;
                }
                swap(arr, largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }
    

    以上面的大根堆为例,我们最上面的元素43和最后面的一个元素交换,同时把heapSize减1,这个时候数组就变成了这样:
    在这里插入图片描述
    这个数组对应的堆就变成了这样:43 不考虑。
    在这里插入图片描述
    接下来开始进行调整,首先是10和它的左右子元素进行比较,36比较大,交换。就变成了这样:
    在这里插入图片描述
    然后10比-54大,所以不用再进行交换了,这就是一次heapify.

    4 堆排序

    堆排序就是利用了heapinsert和heapify来进行排序,当创建完大根堆以后,每一次都把堆顶的元素和堆的最后一个元素进行交换,并且把堆的长度减小1,然后对新的堆进行调整,重新调整为大根堆,然后再取堆顶的元素和堆的最后一个节点进行交换,大根堆的长度减小1,然后再调整,重复这个过程,直到堆里面剩余的元素个数为1.这就是堆排序,具体代码如下:

    public static void heapSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                heapInsert(arr, i);
            }
            int size = arr.length;
            swap(arr, 0, --size);
            while (size > 0) {
                heapify(arr, 0, size);
                swap(arr, 0, --size);
            }
        }
    
        public static void heapInsert(int[] arr, int index) {
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }
    
        public static void heapify(int[] arr, int index, int size) {
            int left = index * 2 + 1;
            while (left < size) {
                int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
                largest = arr[largest] > arr[index] ? largest : index;
                if (largest == index) {
                    break;
                }
                swap(arr, largest, index);
                index = largest;
                left = index * 2 + 1;
            }
        }
    
        public static void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    

    还是以上面的数组对应的大根堆为例:
    最开始:
    在这里插入图片描述
    刚开始heapSize 为7,把43 和10 进行交换,heapSize变成6,此时堆对应的数组就变成了
    在这里插入图片描述
    然后开始调整:10 和36交换,堆对应的数组就变成了左边这个,由于10不小于-54,不再进行交换,这个时候43 不考虑。

    在这里插入图片描述在这里插入图片描述

    把36和-54 交换,heapSize变成5,最开始的时候是最左边,然后-54和10进行交换,因为heapSize为5,这一次就结束了。

    在这里插入图片描述在这里插入图片描述

    把10和-13交换,heapSize变成4,-13和9进行交换,此时还没有调整完成,因为-13小于它的左子节点,还要再调整一次,

    交换后最终
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    然后是-13和9交换,heapSize变成3,然后-13和4(4比-54大)进行交换,这次调整就结束了。

    在这里插入图片描述在这里插入图片描述

    把4和-54 交换,heapSize变成2,-54和-13进行交换。

    在这里插入图片描述在这里插入图片描述

    把-54和-13交换,heapSize变成1,结束
    在这里插入图片描述

    展开全文
  • 堆(大根堆、小根堆)

    千次阅读 2020-05-26 20:51:02
    本文介绍完全二叉堆,包括大根堆、小根堆。相关的算法堆(大根堆、小根堆)的插入、删除、批量建立。

    完全二叉堆

    堆又可称之为完全二叉堆。这是一个逻辑上基于完全二叉树、物理上一般基于线性数据结构(如数组、向量、链表等)的一种数据结构。

    完全二叉树的存储结构

    学习过完全二叉树的同学们都应该了解,完全二叉树在物理上可以用线性数据结构进行表示(或者存储),例如数组int a[5] = {1,2,3,4,5}就可以用来描述一个拥有5个结点的完全二叉树。那么基于完全二叉树的堆结构自然也可以使用线性结构进行描述。回顾一下这样表示时,元素的秩之间的关系。若有元素秩为k(k >= 0),则有Rank(LeftChild) = 2k+1,Rank(RightChild) = 2k+2(此处元素的秩从0开始,若从1开始则推导出的公式略有不同,注意这之间的区别)。

    堆的有序性

    堆可分为两种:大根堆(最大堆)、小根堆(最小堆)。

    大根堆

    何为大根堆?顾名思义,大根堆即指在逻辑上的二叉树结构中,根结点>子结点,总是最大的,并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆,而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素。

    小根堆

    小根堆的性质与大根堆类似,只不过在二叉树的结构中,根结点<子结点。例如{1,2,3}为小根堆,{1,3,2}同样也是小根堆。小根堆的根结点在整个堆中是最小的元素。

    小结

    1. 大/小根堆中根结点即是整个序列中最大 /小的元素,那么从堆中获取最大/小的元素则非常快速,只要返回序列中的首元素即可。
    2. 更一般的,堆处处局部的有序性,形成了堆整体的有序性。 只要有一处局部没有满足堆的有序性,则可以说堆失序,此时便需要进行相应的调整。

    堆的常用场景

    1、根据之前的总结,我们可以利用堆的性质来找出一个序列中最大/小的元素,这不失为一种方法,尽管通过遍历来解决这一问题可能更好。
    2、堆排序,相信学习过堆排序的同学对此都会认同。
    3、建立优先级队列,根据上述的小结可知,若利用堆来建立优先级队列,可以快速的获取到队列中优先级最高/低的任务。
    4、n个元素中排列出前k大的元素问题,对于此类问题,可以建立一个小根堆,依次读入n个元素并调整,并在堆的规模达到k+1时,剔除掉第1个元素,剩下k个较大元素,保持堆的规模不超过k,一直循环即可得到最终的结果。
    5、其他的应用还请各路大神留言指导,互相探讨,小弟感激不尽。

    堆的操作

    堆的操作呢,无非就是建立、插入、删除。建立一个空的堆是非常简单的操作,而利用一个已有的序列生成一个是一个值得思考的问题;插入和删除操作,比较简单;值得思考的是插入元素或者删除元素之后如何恢复堆的堆序性。

    堆的插入与上滤

    1. 往一个线性序列中插入一个元素是比较简单的,例如数组a[N],在秩为k(k<N)的位置上插入一个元素e,分为以下操作:a) 将秩大于等于k的元素一次后移一位;b)将a[k]赋值为e。
    2. 假设堆使用数组作为底层的实现,那么堆的插入又该如何实现呢?是插入到原堆的头部?还是尾部?亦或是中间? 鉴于原堆已经保持了堆序性,如果插入在头部,相当于所有元素对应的父结点和子结点都会发生变化,这样以来会导致整个堆失效;如果插入在中间的某一位置,则会导致插入位置之后的所有元素对应的父结点和子结点发生变化,这样一来会导致堆的部分失效;如果插入在堆底,则原堆的结构未遭破坏,此时唯一可能不符合堆性质的只是最后一个元素(刚刚插入的元素)的父结点是否比它大/小,即在这个局部是否还满足之前所说的堆序性。
    3. 好,现在,可以确定在堆底插入新元素的代价是最小的,那么接下来就是思考在这种情况下如何恢复堆序性。试想一个小根堆如下{2,3},在其尾部插入元素1,如何调整使其满足小根堆的性质呢?对,通过将元素2和元素1交换即可得到小根堆{1,3,2}。此时回顾以下小根堆的性质便不难看出,在此种情形下,对失序的堆执行以下操作即可恢复其堆序性:若新插入结点小于其父结点,则将两者交换。
    4. 在第三条所阐述的情况中,并没有对新插入结点的兄弟结点(如果有的话)做任何操作,甚至不需要考虑它,这是为何?假设新插入结点为N,其父结点为F(N),其兄弟结点为B(N),则在原堆(结点N插入之前)中有这样的关系:F(N) < B(N)。插入结点N后,若N < F(N),则有N < F(N) < B(N)。回顾堆序性的描述,不难知道只要将N与F(N)互换位置就可以使得堆恢复堆序性。
    5. 由点及面,假设上述的堆{2,3}只是另一个堆heap2中的局部(3为heap2中的堆底元素,2为3的父结点),通过上一条阐述的操作,我们可以恢复局部的堆序性,但别忘了,由于原来元素2变成了元素1,此时要继续检查元素1以及元素1的父结点、兄弟结点组成的局部堆是否满足堆序性,循环往复直到插入元素所处的局部满足了堆序性。这样的一个过程也称为堆的上滤(percolateUp)
      代码如下:
    template<typename T>
    void  percolateUp(T *s, size_t rank)
    {
    	while(rank)
    	{
    		size_t f = (rank-1)>>1;
    		if (s[f] > s[rank])
    		{
    			swap(s[f], s[rank]);
    			rank = f;
    		}
    		else
    			break;
    	}
    }
    
    1. 时间复杂度,O(logn)。不难看出插入的结点在一层一层地向上升(与父结点互换位置),而完全二叉树的高度为logn,故其时间复杂度为O(logn)。

    堆的删除与下滤

    1. 从一个线性序列中删除一个元素是简单的,但对于堆这样的结构而言,若以比较的方式来删除某一个元素并无意义,堆的有序性告诉我们,从堆中删除掉对顶元素是比较有价值的(时间复杂度O(1))。不妨将堆的删除操作视为取出堆顶元素。
    2. 对于一个堆heap而言,取出对顶元素只需要删除掉heap[0]即可,那么删除掉首元素之后,原来的堆失去了它的跟结点,整个堆面临着失效的尴尬境地。与插入操作类似,需要思考一个问题,如何调整可以使得原堆中其他部分可以依旧保持的原来的结构(各个元素之间的父子关系)?可以在被删除掉的首元素的位置再插入一个元素来保持原堆中其他结点的结构不变,可以将这样的过程视为一个新的结点替换掉了原来的根结点。
    3. 那么这个新的结点从何而来呢?若选取了中间的某一结点X来替换掉根结点,则会导致X之后的结点全部失效(原来的结构被破坏)。至此,相信大家不难看出,一如插入操作一般,选取堆底元素来替换根结点是最佳的选择,这使得整个堆依旧可以保持原来的结构。接下来要思考的就是替换之后整个堆是否依旧保持着堆序性。
    4. 前面说到堆处处局部的有序即是堆整体的有序,那么在替换之后,局部是否有序便成了判断堆整体是否有序的依据。分别用N、L(N)、R(N)表示替换之后的根结点、根结点的左孩子、根结点的右孩子。如果N < L(N)且N < R(N),那么堆序性依旧保持;否则堆序性被破坏。不如将上述的条件写成如下的形式:如果N < MIN(L(N), R(N)),那么堆序性依旧保持;否则堆序性被破坏。此种情形与在堆底插入一个元素所造成的堆序性破坏略有不同,那么接下来该思考的是如何调整使得堆的局部恢复有序性呢?是否可以通过类似于上滤的方案来解决此类失序的问题呢?
    5. 还是回到堆序性这个特性上,对于N、L(N)、R(N)这三个结点组成的局部堆而言,只需保证这三者中的最小值处在根结点这个位置上即可保持堆序性。至此,可以得出若N < MIN(L(N), R(N))不被满足,则将N与MIN(L(N), R(N))呼唤位置即可保持堆序性。同插入处理,在进行一次调整后还需继续对新形成的局部堆进行调整,循环往复,直至局部堆恢复堆序性或结点N成为了叶子结点。这样的一个过程也称为堆的下滤(percolateDown)
      代码如下:
    template<typanme T>
    void percolateDown(T *s, size_t rank, size_t size)
    {
    	size_t lastInternal = (size-1)/2; //最后一个内部结点的秩
    	while (rank < lastInternal) 
    	{
    		size_t lChild = rank*2+1; //左孩子的秩
    		size_t rChild = rank*2+2; //右孩子的秩
    		size_t LChild = s[lChild] < s[rChild] ? lChild : rChild; //子结点中最小者才有可能成为父结点
    		if (s[lChild] < s[rank])  //若违反堆序性
    		{
    			swap(s[LChild], s[rank]); //交换
    			rank = LChild;  //继续考察
    		}
    		else 
    			break;
    	}
    	
    	if (rank == lastInternal)  //如果被调整成了最后一个内部结点,则需要判断是否有右孩子
    	{
    		size_t lChild = rank*2+1;
    		size_t rChild = rank*2+2;
    		size_t LChild = s[lChild] < s[rChild] ? lChild : rChild;
    		if (rChild == size) //右孩子越界
    			LChild = lChild;
    		else
    			LChild = s[lChild] < s[rChild] ? lChild : rChild;
    		if (s[LChild] < s[rank])
    			swap(s[Lchild], s[rank]);
    	}
    }
    
    1. 时间复杂度,渐进意义上O(logn),其内部操作比上滤过程而言要多一些,故其常系数部分略高。

    利用一个已有的序列建立一个堆

    1. 这个问题可以通过建立一个空堆,然后逐个将序列中的元素插入至堆中来完成,大致地可以得出时间复杂度为O(nlogn)。如果将这样的操作原地进行,则相当于依次从首元素到尾元素执行上滤操作,暂且将这样的方式称之为自上而下的上滤。
    2. 是否可以使用下滤来实现这一功能呢?从最后一个内部结点开始,逐个对所有的内部结点进行下滤操作,完成后就可以得到一个堆。
    3. 在此,不妨将对内部结点下滤的过程视为该内部结点与其左右子堆的合并成一个堆的过程。设内部结点为N,左右子堆分别用HL和HR来表示。既是堆,那么HL与HR都满足堆序性,事实上在从最后一个内部结点开始时,HL与HR都至多包含一个元素,只拥有一个元素的堆自然是有序的。等到所有叶子结点的父结点都与其左右子堆(堆中只有一个元素)合并后,才会出现HL和HR中包含多个元素的情况,而经过下滤调整的子堆都是满足堆序性的。至此可以证明通过这样的方式可以使得整个堆恢复堆序性。不妨将这样的方式称之为自下而上的上滤。
    4. 时间复杂度为O(n),是的这可能与大家直观的感觉不一致,证明过程需要使用归纳法,在此就不进行下去了。不过呢可以通过与自上而下的上滤算法来进行简单的对比:首先上滤建堆需要对所有的元素都执行上滤操作,而且越是接近堆底的元素可能需要交换的次数就越多,这意味这可能会有较多的元素需要进行较多次数的交换;而下滤建堆只需对所有内部结点进行下滤操作,这在操作的元素数量上就少了一半,其次越接近堆底的内部结点所需要的交换次数越少,这意味大多数的内部结点只需执行较少的交换,只有离堆顶越近的元素才需要较多的交换,而越接近堆顶,元素数量越少。由此可以看出自下而上的下滤建堆算法在时间复杂度的渐进意义上来讲要优于自上而下的上滤算法。事实上自下而上的下来吧建堆算法称之为弗洛伊德建堆法
      代码如下
    template<typename T>
    void heapify(T *s, size_t size)
    {
        int rank;
        auto getLastInternal = [size] {return (size-1)>>1;};
        if ((rank = getLastInternal()) < 0) //获取最后一个内部节点
            return ;
            
        while (rank>= 0)  //对每一个内部结点做下滤
        {
            percolateDown(s, rank, size);
            --rank;
        }
    }
    

    记录学习历程,各路大神若有指教,可留言探讨,感激不尽!

    展开全文
  • 大根堆与堆排序堆分为大根堆和小根堆,是完全二叉树。 完全二叉树我们知道,就是不太满的满二叉树;大根,小跟代表,父节点和子节点的关系;如果每一个父节点都不小于它的两个子节点,就可以认为是大根堆了;堆排序...

    大根堆与堆排序

    堆分为大根堆和小根堆,是完全二叉树。
    完全二叉树我们知道,就是不太满的满二叉树;大根,小跟代表,父节点和子节点的关系;如果每一个父节点都不小于它的两个子节点,就可以认为是大根堆了;

    堆排序的思路

    从定义看,我们就知道了,对于大根堆来说,根节点一定是最大的,那我们就每次把根节点拿走,让大根堆重新排序,然后再取得最大值就可以了嘛;

    那么重要的问题就来了,大根堆是怎么从一个普通的堆转换过来的的呢?
    其实也很简单,就是说父节点如果比子节点小,就交换一下,如果交换之后,发现下面还有一层,就继续;

    然后呢,由于是完全二叉树,就会有这么一个关系:
    K[i]是K[2i]和K[2i+1]的父节点;也就是说父节点的位置,和子节点位置是固定的,所以就可以用数组来表示大根堆了;因为位置是确定的嘛;
    代码上的话,一定要注意边界,还有就是数组起始位置的0;

    代码

     public class HeapSort {
        public static void main(String[] args) {
            int[] array = new int[]{14,4,14};
            HeapSort heapSort = new HeapSort();
            heapSort.heapSort(array, array.length);
            System.out.println(Arrays.toString(array));
        }
    
        /**
         * 堆排思路,利用大根堆头结点最大的特性<br>
         * 首先将数组调换为大根堆,然后把头结点扔出去<br>
         *     重复这个过程
         * @param array
         * @param n
         * @return
         */
        public int[] heapSort(int[] array, int n) {
            array = buildMaxHeap(array, n);
            for (int i = array.length-1;i>0;i--) {
                swap(array, 0, i);
                adjustHeap(array, 0, i);
            }
            return array;
        }
    
        private int[] buildMaxHeap(int[] array, int n) {
            //这个边界坑坏我了,数组长度是从一开始计算的;
            //直接除以二就行了,其实k的起始边界并不重要;
            //很可能第一次压根就不会进行调换,实际上因为数组从零开始,
            // 所以有时会多一次调换
            for (int k = array.length >> 1; k >= 0; k--) {
                adjustHeap(array, k, array.length);
            }
            return array;
        }
    
        private void adjustHeap(int[] array, int k, int length) {
            int temp = array[k];
            for (int j = 2 * k + 1; j < length; j = 2 * k + 1) {
                if (j < length-1 && array[j] < array[j + 1]) {
                    j++;
                }
                if (temp > array[j]) {
                    break;
                } else {
                    array[k] = array[j];
                    k = j;
                }
            }
            array[k] = temp;
        }
    
    }

    收获

    1. 清楚地弄明白了堆排序的原理
    2. 不敲代码,你完全无法想象调整堆时对边界的限制到底意味着什么;
    3. 原来的代码居然有问题,我都不想活了
    展开全文
  • 大根堆:又称最大堆、大顶堆。指根节点值最大的二叉堆 小根堆:又称最小堆、小顶堆。指根节点值最小的二叉堆 二叉堆举例 此图为大根堆 存储方式 存储方式:数组。需注意:堆存储从下标0开始还是1开始,以下例子,从...

    二叉堆算法详解

    基础知识

    二叉堆的应用:找出最大/最小值
    二叉堆定义:堆是完全二叉树。父结点的键值总是大于等于(小于等于)任何一个子节点的键值。
    大根堆:又称最大堆、大顶堆。指根节点值最大的二叉堆
    小根堆:又称最小堆、小顶堆。指根节点值最小的二叉堆

    二叉堆举例

    此图为大根堆
    ALT

    存储方式

    存储方式:数组。需注意:堆存储从下标0开始还是1开始,以下例子,从下标0开始存储。
    假设父节点下标为i,左孩子节点为2i+1,右孩子结点为2i+2。上图二叉堆的存储形式为:在这里插入图片描述

    二叉堆基本操作

    上浮和下沉都以大根堆为例。如果不懂建议看第三条参考资料。

    上浮

    可用插入结点
    思路(大根堆):

    1. 将插入的结点放到二叉堆的最后,即数组的最后一位
    2. 将插入结点的值A和父结点的值B比较。
    3. 如果A>B,A的值等于B的值。
    4. 重复步骤2、3,直至A<=B或插入结点无父节点。

    代码

    public void add(int[] array){
            int childIndex=array.length-1;
            int parentIndex=(childIndex-1)/2;
            int tmp=array[childIndex];
            while(childIndex>0 && tmp>array[parentIndex]){
                array[childIndex]=array[parentIndex];
                childIndex=parentIndex;
                parentIndex=(parentIndex-1)/2;
            }
            array[childIndex]=tmp;
        }
    

    下沉

    思路:和上浮相反

    1. 需要下沉的结点A和左右孩子中值最大的结点比较。
    2. 若需要下沉,则将父节点的值改为子节点的值
    3. 直到结束循环

    代码:

     public void down(int[] array,int index,int len){
            int tmp=array[index];
            int parentIndex=index,childIndex=2*parentIndex+1;
            while(childIndex<len){
                //判断有无右孩子,如果有的话,childIndex指向左右孩子中值最大的结点
                if(childIndex+1<len && array[childIndex]<array[childIndex+1])
                    childIndex++;
                if (tmp>=array[childIndex])
                    break;
                array[childIndex]=array[parentIndex];
                parentIndex=childIndex;
                childIndex=childIndex*2+1;
    
            }
            array[parentIndex]=tmp;
    
        }
    

    构建堆

    思路:
    从最后一个非叶结点开始做下沉操作
    代码:
    down函数为下沉函数,代码见上方

    public void build(int[] array){
         for(int i=(array.length-2)/2;i>=0;i++){
             down(array,i,array.length);
         }
     }
    

    参考资料

    1.五分钟学算法:动画 | 什么是二叉堆?
    2.脚本之家:《一文说透数据结构》系列之什么是堆?看这一篇就够了
    3.程序员小灰:漫画:什么是二叉堆?

    展开全文
  • 大根堆

    2018-07-09 00:23:50
    public class BigHeap { //默认初始化长度 private static final int DEFAULT_INIYIAL_CAPACITY = 10;... //使用的长度 private int currentSize; //最大长度 private int capacity; private int [] qu...
  • 大根堆和小根堆

    千次阅读 2018-10-12 18:52:31
    大根堆 用数组方法实现: 下沉函数,核心函数,将以t为根的且左右子树均为大根堆的树调整为大根堆。 void siftdown(int t,int n) { if(t&amp;amp;gt;(n-1)/2) return ; int lchild=t*2+1; int ...
  • 堆排序—大根堆,小根堆

    千次阅读 2015-02-02 20:40:02
    2.大根堆 若根节点存在左子女则根节点的值大于左子女的值;若根节点存在右子女则根节点的值大于右子女的值。 3.结论 (1)堆是一棵完全二叉树(如果公有h层,那么1~h-1层均满,在h层连续缺失若干个右叶子)。 (2)...
  • 数组实现的大根堆

    2019-06-18 10:21:32
    大根堆 根节点是所有节点中数值最大的节点 父节点的值总比子节点大 基本操作 Insert 向堆中插入一个值 Update 更新 Heapify 堆化 RemoveTop 删除堆顶元素 GetTop 获得堆顶元素 辅助操作 获得父节点 获得左孩子 ...
  • 因为插入一个元素时,列表已经是一个大根堆,所以当出现父元素大于自己时,就没有必要继续,因为父元素的父元素值更大。 shift down 删除一个元素时,把该元素和列表的最后一个元素交换。然后列表的长度减一(如果...
  • 堆、大根堆、小根堆

    千次阅读 2017-01-11 13:30:37
    堆是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于(或不小于)其左孩子和右孩子节点的值。 根结点(亦称为堆顶)的关键字是...根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆
  • 大根堆,小根堆,优先队列,堆排序,模版。
  • 大根堆: 根节点value不小于子节点的value,满足这条性质的二叉树即为大根堆。 小根堆:根节点value不大于子节点的value,满足这条性质的二叉树即为小根堆。 从大根堆的定义可知:在大根堆里要得到最大值只需o(1)的...
  • STL应用之大根堆小根堆

    万次阅读 2014-10-15 21:24:26
    STL应用之大根堆小根堆 定义: priority_queue xxx 大根堆 priority_queue, greater> xxxx 小根堆
  • 大根堆就是其中每个节点的值都大于或等于其子节点。 大根堆既是大根树又是完全二叉树。 像下图这样: 大根堆的类中的数据成员是,heap数组(一个类型为T的一维数组),arrayLength(数组heap的容量),heapSize(堆...
  • 优先级队列--大根堆和小根堆

    千次阅读 2019-08-10 16:43:41
    比如大根堆是最大的元素先出队,小根堆是最小的元素先出队。 堆是实现优先级队列效率很高的数据结构(当然我们也可以使用无序的线性表或者有序链表来实现,但是它们的删除、插入的时间复杂度至少有一个是O(n))。堆是...
  • //建立大根堆,结果是从小到大排序 public static void heapSort(int[] arr) { buildHeap(arr); //size是当前堆最后一个元素的下标 int size = arr.length - 1; while (size &gt; 0) { int tem...
  • 如何构建一个大根堆

    千次阅读 多人点赞 2020-06-18 18:18:23
    数组可以看成是一个完全二叉树,大根堆是一个完全二叉树 构造大根堆 例子1:[O(N)---->从下到上] 因为堆是对父节点-左/右孩子节点之间的约束,所以从最后一个非叶子节点开始调整。 注意每次交换后,都要对下一...
  • 堆排序(大根堆

    2020-06-16 19:35:29
    #include #include using namespace std; void Swap(int *heap, int... i--) { //构建大根堆 BuildMaxHeap(a, 0, i); //交换首尾结点 int temp = a[i-1]; a[i-1] = a[0]; a[0] = temp; } for (i = 0; i ; i++) { cout 
  • 大根堆排序 实现的五个基本功能: 插入一个数:heap[++sz]=x; up(sz); 尾部插入 求集合中的最大值:heap[1] 删除最大值:heap[1]=heap[sz]; sz– – ; down(1); 尾部代替头部 删除任一个结点为k的元素:heap[k]=...
  • 大根堆创建于排序

    2019-05-23 17:18:21
    创建大根堆 static void buildBigHeap(int[] array, int last) { //从最大的非叶子节点开始(last - 1 /2),到根节点终止 for (int i = (last -1) / 2; i >= 0; i--) { int k = i; //判断是否超过数组...
  • 序列——堆排序-大根堆(堆大顶)

    千次阅读 2015-07-18 12:15:00
    1.小根堆 如果根是儿童的存在留下的根值左孩子小于值;如果根是儿童的权利的存在的根值比他们的孩子的权利少值。 ...(2)小根堆的根节点的值是最小值,大根堆的根节点的值是最大值。 (3...
  • 大根堆的实现!
  • 方式1:重载”<“运算符 值得注意的是,无论是大根对... //大根堆 struct NodeDistCloser { float d; int id; NodeDistCloser(float d, int id) : d(d), id(id) {} bool operator<(const NodeDistCloser&a
  • 大根堆算法

    千次阅读 2016-06-20 10:21:12
    待补充该算法的过程
  • 我们可以创立一个大根堆,然后每次将堆顶的元素取出来,然后将他减去烘干机的烘的湿度之后再将它压回大根堆内,因为洪完之后可能这个最大的就被烘干了,并且还有其他衣服没有烘干,我们就判断一下加入当前堆顶元素也...
  • 2)完全二叉树中,如果每棵子树的 最大值都在顶部,是 大根堆 3)完全二叉树中,如果每棵子树的 最小值都在顶部,是 小根堆 4)堆结构的 heapInsert 与 heapify 操作 5)堆结构的增大和减少 6)优先级队列结构,就是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,857
精华内容 2,342
关键字:

判断大根堆