美文网首页
数据结构与算法笔记day19:递归树|堆|堆排序|堆的应用

数据结构与算法笔记day19:递归树|堆|堆排序|堆的应用

作者: 楠楠喜欢泡枸杞 | 来源:发表于2019-06-10 15:21 被阅读0次

        1递归树

            这节课我们用递归树分析了递归代码的时间复杂度,之前我们在排序那一节也讲过递推公式的时间复杂度分析方法,现在已经学习了两种递归代码的时间复杂度分析方法啦。

            我们把递归的一层一层的分解过程画成图,就是一棵树,它就是递归树

            如下图:

            计算时间复杂度的方法是,知道这棵树的高度h,用高度h乘以每一层的时间消耗n,就可以得到总的时间复杂度O(n*h)

            归并排序的时间复杂度、快速排序的最好情况时间复杂度适合用递推公式来分析;快速排序的平均时间复杂度适合用递归树来分析。

        2堆和堆排序

            这节课学习了堆这种数据结构,堆是一种完全二叉树,它最大的特性是:每个节点的值都大于等于(或小于等于)其子树节点的值。因此,堆被分成了两类,大顶堆小顶堆

            堆中比较重要的两个操作是插入一个数据和删除堆顶元素,这两个操作都要用到堆化。插入一个数据的时候,我们把新插入的数据放到数组的最后,然后从下往上堆化;删除堆顶元素的时候,我们把数组中的最后一个元素放到堆顶,然后从上往下堆化。这两个操作的时间复杂度都是O(logn)

            另外还学习了堆的一个经典应用:堆排序。堆排序包含两个过程,建堆排序。我们将下标从n/21的节点,依次进行从上到下的堆化操作,然后就可以将数组中的数据组织成堆这种数据结构。接下来,迭代地将堆顶的元素放到堆的末尾,并将堆的大小减一,然后再堆化,重复这个过程,直到堆中只剩下一个元素,整个数组中的数据就都有序排列了。

            那么为什么快速排序要比堆排序的性能好?

            1.堆排序数据访问的方式没有快速排序友好。堆排序要跳着访问。

            2.对于同样的数据,在排序过程中,堆排序算法的数据交换次数要多于快速排序。堆排序第一步是建堆,建堆的过程会打乱数据原有的相对先后顺序,导致原数据的有序度降低(尤其是对于一组已经有序的数据来说,经过建堆之后数据会变得更加无序)。

        3堆的应用

            这节课学习了堆的几个重要应用,它们分别是:优先级队列、求TOP K问题和求中位数问题。

            优先级队列是一种特殊的队列,优先级高的数据先出队,而不再像普通的队列那样,先进先出。实际上,堆就可以看做优先级队列,只是称谓不一样罢了。

            求Top K问题又可以分为针对静态数据和针对动态数据,只需要利用一个堆,就可以做到非常高效率的查询Top K的数据。

            求中位数实际上还有很多变形,比如求99百分位数据、90百分位数据,处理的思路都是一样的,即利用两个堆,一个大顶堆,一个小顶堆,随着动态的数据添加,动态调整两个堆中的数据,最后大顶堆的堆顶元素就是要求的数据。

    相关文章

      网友评论

          本文标题:数据结构与算法笔记day19:递归树|堆|堆排序|堆的应用

          本文链接:https://www.haomeiwen.com/subject/kwsjxctx.html