刷题
刷题
learn
learn
日期
Aug 31, 2024
堆结构：
- 完全二叉树和数组前缀范围的对应，大小由单独的变量
size来控制
i的父亲结点：(i-1)/2，i的左孩子：i * 2 + 1，i的右孩子：i * 2 + 2
- 堆的定义（大根堆、小根堆）
- 堆的调整：
heapInsertion（向上调整）、heapify（向下调整） 如果某个位置的元素变大了，那么只可能向上调整；如果变小了，那么只可能向下调整
heapInsert、heapify方法的单次调用，时间复杂度，完全二叉树的结构决定的
堆排序：
- 从顶到底建堆，时间复杂度， 或者用增倍分析法：建堆的复杂度分析+子矩阵数量的复杂度分析
- 从底到顶建堆，时间复杂度，总打哀家就是简单的等比数列关系。
为什么会有差异？
- 建好堆之后的调整阶段，从最大值到最小值依次归位，时间复杂度
时间复杂度，不管以什么方式建堆，调整阶段的时间复杂度都是这个，所以整体复杂度也是这个
额外空间复杂度是，因为堆直接建立在了要排序的数组上，所以没有什么额外空间
注意：堆结构比堆排序有用的多，尤其是和比较器结合之后！
- 向上和向下调整操作的时间复杂度分析：因为对于一个建好的堆，如果有个元素，堆最高为层，而由于调整操作最差情况也只需要遍历完一条边，个数是，所以调整操作时间复杂度就是