堆
# 堆基础
堆概念
- 堆是一个完全二叉树
- 堆中每一个结点的值都必须大于等于(或者小于等于)其子树中每个结点的值。
- 大于等于是 大堆顶
- 小于等于是小堆顶
- 堆顶大的称为大堆顶，堆顶小的称为小堆顶
堆的实现
元素存储
完全二叉树，借用数组存储。
- ==下标与父子关系==
- 设数组中存储下标从1开始
- 数组中下标为$i$的节点的左子节点，就是下标为$i2$的节点，右子节点就是下标为$i2+1$的节点，父节点就是下标为 $i/2$ 的节点。
- 下标从$n/2$开始，不包括$n/2$,后面的都是叶子结点
- ==下标与父子关系==
插入一个元素
往堆中插入一个元素后，需要调整堆的结构，要让堆符合特性，这一过程称为堆化。
自下而上的堆化
例如，在数组最后插入元素22，然后调整堆的结构
插入代码
/** * 堆中插入元素--自下而上的堆化--大堆顶 * 数组下标从1开始计数 * @param nums 数组 * @param count 数组中已有元素个数 * @param value 待插入的值 */ public void insert(int[] nums, int count, int value) { if (count > nums.length) { System.out.println("数组中元素已满，请扩容数组"); return; } //数组最后插入元素 int height = count + 1; nums[height] = value; int parent; //自下而上开始堆化 while (height > 1) { parent = height / 2; if (nums[height] > nums[parent]) { swap(nums, height, parent); height = parent; }else { break; } } }
删除堆顶元素
将数组最后一个放到堆顶，然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。这就是从上往下的堆化。
删除代码
/** * 删除堆顶元素-- 自上而下的堆化--大堆顶 * @param nums 数组 * @param count 数组中元素个数 */ public void deleteHeapTop(int[] nums, int count) { if (count < 1) return; // 将最后一个元素放到堆顶 nums[1] = nums[count]; nums[count] = 0; heapify(nums, 1, count); } /** * 自上而下的堆化 * @param nums 数组 * @param height 当前值的下标 */ public void heapify(int[] nums, int height, int count) { while (true) { int maxPos = height; //当前值不光要与左子树比较还要与右子树比较 if (height * 2 <= count && nums[maxPos] < nums[height * 2]) maxPos = height * 2; if (height * 2 + 1 <= count && nums[maxPos] < nums[height * 2 + 1]) maxPos = height * 2 + 1; if (maxPos == height) break; swap(nums, height, maxPos); height = maxPos; } }
堆排序
建堆——原地排序
不借助另外一个数组，在自己的数组基础上进行元素调整
建堆时间复杂度为O(n)
从上往下堆化----------自下而上的堆化
尽管数组中包含 n 个数据，但是我们可以假设，起初堆中只包含一个数据，就是下标为 1 的数据。然后，我们调用前面讲的插入操作，将下标从 2 到 n 的数据依次插入到堆中。这样我们就将包含 n 个数据的数组，组织成了堆。
从下往上堆化----------自上而下的堆化
从后往前处理数组，并且每个数据都是从上往下堆化。直接从最后一个非叶子节点开始，依次堆化就行了。
代码
/** * 建堆 * @param nums 数组 * @param count 数组内元素 */ public void bulidHeap(int[] nums, int count) { for (int i = count / 2; i >= 1; i--) { heapify(nums, i, count); } }
排序
建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置。 然后对剩余元素，继续堆化，不断的交换元素，直到堆中只剩下一个元素为止。
排序过程时间复杂度O(nlogn)
所以堆排序整体过程时间复杂度为O(nlogn)
代码
public void sort(int[] nums, int count) { int num = count; while (num > 1) { //建堆 bulidHeap(nums, num); //取堆顶元素，放入最后 swap(nums, num, 1); num --; } }
为什么快速排序要比堆排序性能好？
堆排序数据访问的方式没有快速排序友好。
堆排序时，访问元素是跳跃式访问，对cpu缓存不友好，
而快排是局部顺序访问。
对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。
建堆的过程，会打乱原先的相对的先后顺序，导致有序度降低。
从而堆排序比快速排序交换次数多。
# 优先级队列
java-----PriorityQueue
一个堆就可以看作一个优先级队列。
往优先级队列中插入一个元素，就相当于往堆中插入一个元素,然后堆化；
从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素,然后堆化。
队列内部无序，但是队首元素，一定是优先级最高的，每次取走队首元素，都会对剩余元素进行堆化
代码
public static void testPriorityQueue() { //优先级队列(默认是小堆顶) //队列内部无序，但是队首元素，一定是最小的，每次取走队首元素，都会对剩余元素进行堆化 //堆化方式是，将最后一个元素放入队首，自上而下的堆化 PriorityQueue<Integer> queue = new PriorityQueue<>(); //插入的时候是按照完全二叉树的构造方式插入的 queue.add(5); queue.add(3); queue.add(1); queue.add(2); queue.add(4); System.out.println(queue);//[1, 2, 3, 5, 4] queue.poll(); System.out.println(queue);//[2, 4, 3, 5] queue.poll(); System.out.println(queue);//[3, 4, 5] }合并有序小文件
问题描述
假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。
解决办法
我们取100个小文件的第一个元素，构建一个大小为100的小堆顶。那堆顶的元素，也就是优先级队列队首的元素，就是最小的字符串。
我们将这个字符串放入到大文件中，并将其从堆中删除。然后再从小文件中(取走的字符串所属的小文件)取出下一个字符串，放入到堆中。循环这个过程，就可以将 100 个小文件中的数据依次放入到大文件中。
高性能定时器
问题描述
假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。
但是，这样每过 1 秒就扫描一遍任务列表的做法比较低效。
解决方法
我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。
这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。这样，定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。
当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。**优先级队列取走队首元素后，会对剩余元素堆化，在次将最小的放在队首，保证每次从队首拿的都是最小的时间。**然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。
# 求Topk
静态数据
问题描述
如何在一个包含 n 个数据的数组中，查找==前 K 大数据==呢？
解决方法
- 遍历数组，先取前K个元素，构建==小堆顶==。堆顶元素是K个元素中最小的。
- 从第K+1个元素，继续遍历数组，从数组中取出数据与堆顶元素比较。
- 如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中，然后堆化，构造小堆顶。
- 堆顶元素是最小的，也就是最危险的，只要来了比它大的，就淘汰它。
- 如果比堆顶元素小，则不做处理，继续遍历数组。
- 堆顶元素是最小的，你比我还小，怎么可能进的来？
- 如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中，然后堆化，构造小堆顶。
- 这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。
时间复杂度：
遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，时间复杂度就是 O(nlogK)。
代码
public static void topK() { int[] nums = {3,2,4,7,9,0,54,1,435,245,344}; int[] top = new int[5 + 1]; //建堆 int index; for (index = 0; index < 5; index ++) { top[index + 1] = nums[index]; } Heap.bulidHeap(top,5, 0); //遍历剩余数组元素，维护堆 for (;index < nums.length; index ++) { if (nums[index] > top[1]) { top[1] = nums[index]; Heap.bulidHeap(top,5, 0); } } System.out.println(Arrays.toString(top)); }
动态数据
问题描述
针对动态数据求得 Top K 就是实时 Top K。一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前 K 大数据。
如果每次询问前 K 大数据，我们都基于当前的数据重新计算的话，那时间复杂度就是 O(nlogK)，n 表示当前的数据的大小。
解决方法
我们可以一直都维护一个 K 大小的小顶堆，**当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。**如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理。这样，无论任何时候需要查询当前的前 K 大数据，我们都可以立刻返回给他。
# 求中位数
问题描述
对于一组静态数据，中位数是固定的，我们可以先排序，第 2n 个数据就是中位数。每次询问中位数的时候，我们直接返回这个固定的值就好了。
但是，如果我们面对的是动态数据集合，中位数在不停地变动，如果再用先排序的方法，每次询问中位数的时候，都要先进行排序，那效率就不高了。
借助堆这种数据结构，我们不用排序，就可以非常高效地实现求中位数操作。
解决方法
初始化堆
我们需要维护两个堆，一个大顶堆，一个小顶堆。
大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。大堆顶元素即为中位数。
如果 n 是奇数，情况是类似的，大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据。
动态变换
如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。
这个时候就有可能出现，两个堆中的数据个数不符合前面约定的情况，我们可以从一个堆中不停地将堆顶元素移动到另一个堆，通过这样的调整，来让两个堆中的数据满足上面的约定。
代码
对确定数组求中位数
public static void getMid() { int[] nums = {3,2,4,7,9,10,54,1,435,245,344}; int count = nums.length; int bigCount = 11 / 2 + 1; int littleCount = 11 / 2; int[] bigNum = new int[bigCount + 1];//存储大堆顶 int[] littleNum = new int[littleCount + 1];//存储小堆顶 int i; Arrays.sort(nums); for (i = 1; i < bigCount + 1; i++) { bigNum[i] = nums[i - 1]; } //构建大堆顶 Heap.bulidHeap(bigNum, bigCount, 1); for (;i < nums.length + 1; i++) { littleNum[i - bigCount] = nums[i - 1]; } //构建小堆顶 Heap.bulidHeap(littleNum, littleCount, 0); //中位数即，大堆顶的顶部元素 System.out.println(bigNum[1]); }对流动数组求中位数，以及堆的实现
自定义堆的实现，使用一个变量控制大顶堆还是小顶堆 使用动态数组扩容
// 对数据流求中位数 class MedianFinder { Heap minQueue; Heap maxQueue; public MedianFinder() { // 默认是小堆顶 minQueue = new Heap(false); maxQueue = new Heap(true); } // 大顶堆中的元素要小于小顶堆 public void addNum(int num) { // 当两个堆中的元素个数不等时，往大顶堆中添加元素；当相等时，往小顶堆中添加元素。 // 在往大顶堆添加元素时，先将其放入小顶堆，然后取小堆顶堆顶元素放入大顶堆 // 同理，当往小顶堆添加元素时，先将其放入大顶堆，然后取大顶堆堆顶元素，放入小顶堆 // 尝试放入大顶堆 if (minQueue.size == maxQueue.size) { if (!minQueue.isEmpty() && num > minQueue.peek()) { minQueue.offer(num); maxQueue.offer(minQueue.poll()); } else { maxQueue.offer(num); } return; } // 尝试放入小顶堆 if (num < maxQueue.peek()) { maxQueue.offer(num); minQueue.offer(maxQueue.poll()); } else { minQueue.offer(num); } } public double findMedian() { if (maxQueue.size == minQueue.size) { return (maxQueue.peek() + minQueue.peek()) / 2.0; } // return (double)maxQueue.peek(); return maxQueue.peek(); } } // 建堆 /** * @ClassName heap * @Date 2023/6/21 15:28 * @Author diane * @Description 手动建立堆 * @Version 1.0 */ // 自定义堆实现 // 上浮，下潜，动态数组 class Heap { int[] nums; int size; // true 表示大顶堆；false 表示小顶堆 boolean max; public Heap(boolean maxbool) { size = 0; max = maxbool; nums = new int[3]; } // 添加元素 public void offer(int num) { // 数组满了，扩容 if (size == nums.length) { grow(); } // 上浮，num,使之满足堆的特性 int child = size; while (child > 0) { int parent = (child - 1) / 2; if (max ? nums[parent] < num : nums[parent] > num) { nums[child] = nums[parent]; } else { break; } // 更新孩子指针 child = parent; } nums[child] = num; size++; } // 移除元素 public int poll() { // 不正常移除 if (size == 0) { return -1; } // 交换堆顶元素和最末尾元素，然后移除最末尾元素，最后重新堆化-下潜 int temp = nums[0]; swap(0, size - 1); size--; down(0); return temp; } // 元素下潜 public void down(int p) { int left = 2 * p + 1; int right = left + 1; int maxOrMin = p; if (left < size && (max ? (nums[left] > nums[maxOrMin]) : (nums[left] < nums[maxOrMin]))) { maxOrMin = left; } if (right < size && (max ? (nums[right] > nums[maxOrMin]) : (nums[right] < nums[maxOrMin]))) { maxOrMin = right; } // 如果最大或者最小不是原父指针，则递归调用 if (maxOrMin != p) { swap(maxOrMin, p); down(maxOrMin); } } // 返回堆顶远古三 public int peek() { return nums[0]; } // 判空 public boolean isEmpty() { return size == 0; } // 交换元素 public void swap(int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } // 数组扩容 public void grow() { // 1.5倍扩容 int cap = size + (size >> 1); int[] newNums = new int[cap]; System.arraycopy(nums, 0, newNums, 0, size); nums = newNums; } // 测试 public static void main(String[] args) { Heap heap = new Heap(false); heap.offer(11); heap.offer(5); heap.offer(3); heap.offer(10); heap.offer(1); System.out.println(Arrays.toString(heap.nums)); System.out.println(heap.poll()); System.out.println(heap.poll()); System.out.println(heap.poll()); System.out.println(heap.poll()); System.out.println(heap.poll()); System.out.println(heap.poll()); } }扩展
利用两个堆不仅可以快速求出中位数，还可以快速求其他百分位的数据，原理是类似的。
例如求99%响应时间
一个大顶堆，一个小顶堆。假设当前总数据的个数是 n，大顶堆中保存 n99% 个数据，小顶堆中保存 n1% 个数据。大顶堆堆顶的数据就是我们要找的 99% 响应时间。
