注册新公司网上核名网站成都企业模板网站开发
堆
逻辑上是一棵完全二叉树（依次遍满或者全满）。
数组可以转为完全二叉树，完全二叉树某结点左孩子(2*i+1)，右孩子(i*2+2)，父结点((i-1/)2)，根节点的父还是自己。
如何将数组转化为堆（大根堆）：
1. 初始heapsize = 0，堆的尺寸
2. 给我一个5，我放在0位置，heapsize++
3. 再给我一个3，放在heapsize位置，heapsize++
4.给我一个6，同样，形成[5 3 6]，6需要跟其父结点比较，如果大于父则交换
5. 也就是说，当加入一个新数时，不断和自己的父结点比较，若大于父则交换，直到小于等于父
时间复杂度：O(logN)
如果拿掉了大根堆堆顶，怎么重新构造：
1. 先将数组最后一个数字放于0处，heapsize--
2. 从头结点开始，在左孩子和右孩子的最大值交换
3. 直到该结点成为叶子结点或者大于其左孩子和右孩子
时间复杂度：O(logN)
改变数组某位置的数据，怎么重新构造：
1. 判断变大了还是变小了
2. 若变小了，往下移
3. 若变大了，往上移
4. 不判断就两个全做即可
时间复杂度：O(logN)
堆排序
依次放入数组中的数，构造大根堆（小根堆），数组第一个元素与最后元素交换，heapsize--，重新构造，依次下次，直到堆的大小减为0，则实现排序。
时间复杂度：O(NlogN)
空间复杂度：O(1)
如何不通过添数的方式，依次heapify即可构造堆。时间复杂度O(N)
QUESTION
1. 准备一个小根堆，遍历数组，遍历前k+1个数构造
2. 小根堆的堆顶一定要在0位置，这时候弹出堆顶，加入下一个元素
3. 依次下去即可
桶排序（不基于比较的排序）
数据范围小的时候可以使用计数排序，一个数组统计数字频次，依次输出即可。
基数排序（可以通过词频统计完成入桶出桶操作）
1. 先看最大数字有几位，然后通过前补0，将所有数字变为该位
2. 准备10个（按进制来）的队列，根据数字最低位数放入对应队列
3. 从左到右取出队列数字
4. 按十位数放如对应序列，再从左到右取出
5. 下次下去，直到超过最大位数，排序完成