3-14(堆的完结以及二叉树的遍历)
16lz
2021-03-15
今天主要完成了堆的实现、排序以及堆的增删操作。并且学习了二叉树的遍历，以及完成了二叉树的一道算法题。
1、堆
首先堆是一个二叉树；另外堆分为大堆和小堆，大堆是每个根都不小于其子树，小堆是每个根都不大大于其子树，也就是说大堆的root为最大值，同理，小堆的root为最小值；
再者，堆排序可以将一个数组进行降序或升序排序，降序使用小堆，升序使用大堆，因为建立一个小堆，其根节点为最小值，这样把根节点和最后一个节点对换，就得到了最小值，再利用向下排序，找出第二个小的值。同理，大堆具有最大值为root，对换后，最大值就出来了，所以适合升序。
另外 堆最大特点是适合用来招数。
如topK问题：
找出n个数里面的前k的最大值。
方案1：利用建个n个数的大堆，每次将最大值与最后一个元素对换，再利用向下调整，找出最大的k个数。时间复杂度为0(n+(k-1)*logn),因为建堆的时间复杂度为0(n)，每次向下调整的时间复杂度为0(logn)。但是此方案的空间复杂度太高，不推荐使用。
方案2：减小堆，建立k个元素的小堆，将剩下的数依次与root比较，如果比root大，就替换root，然后向下调整，再将堆里面的最小值送到root上面，这样比较完成后，其堆里面都是k个大值。这个方案最好，推荐使用。
2、二叉树
二叉树的遍历有前序遍历，中序遍历，后序遍历，层次遍历。 这里面需要注意的是左，右都是表示左子树，右子树，
而不是单纯的左右。
每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- 学习感悟一
- java集合【7】——— iterator和Iterable异同详解
- 《Golang从入门到跑路》之map的初识
- 103. 二叉树的锯齿形层序遍历
- 从数组中移除元素，要求时间复杂度为O(N)空间复杂度为O(1)
- 2021-02-26：一个数组arr是二叉树的中序遍历结果，每条边的开销是父
- 数据结构与算法专题——第六题 树状数组
- 遍历 Dictionary，你会几种方式？
- Windows 遍历查找文件夹文件