堆

1 前言在之前的文章里，我分享了Js版的堆实现和C语言版的堆实现, 了解的话，堆的实现其实并不难，以大顶堆为例，简略演绎就是插入时候，比节点小，就一直向下沉，让更大的上浮，直到最大的上浮到根节点。 1. 数据与构造与算法: 堆 C语言形容 2. 数据结构与算法: 堆 优先队列 JavaScript语言形容 优先队列基于堆实现，顾名思义是一个有优先级的队列，最高优先级的最先出列，低优先级最初出列（如果是最小堆则刚好相同）。明天咱们就用堆和优先队列高效解决一些问题，别离是经典的TopK问题-堆解法，以及3D接雨水-优先队列解法。 2 TopK问题-堆解法题目：215. 数组中的第K个最大元素 2.1 思路在之前的文章里，我分享了基于Partition和ThreePartition算法的原地排序，来高效求解TopK问题，原地排序，没有应用额定的空间，空间复杂度很低，然而工夫复杂度稳定比拟大，如果随机取的基准值很现实，那么效率超高，但如果数组里值散布很发散，随机取的基准值也很不现实，那么这种极其状况下，那么效率就不是很高,尽管《算法导论》证实了Partition算法是近似线性，但其线性常数项相对比1大多了； 而堆解法呢，就是稳固的工夫空间复杂度，建堆的最差复杂度是确定的，遍历一遍的复杂度只有O(N),能够确定在kLog(k) + O(N)。 2.2 C语言形容先建设一个容量为k的最小堆，后续的元素，只有比堆顶大的，才入堆，否则间接略过，最初堆顶元素就是第K大元素。 typedef struct MinHeap { int *data; //数据域 int size; //长度 int max;//最大长度} MinHeap;void insert(struct MinHeap *p, int item){ if (p->size == p->max) { printf("******:\n"); return; } int i = ++p->size; for (; p->data[i/2] > item; i/=2) { if (i <= 1) { break; } p->data[i] = p->data[i/2]; } p->data[i] = item;}void delete(struct MinHeap *p){ p->data[1] = p->data[p->size--]; int i = 1; int tmp; while(2*i <= p->size){ //如果有右节点 if (2*i + 1 <= p->size) { if (p->data[2*i + 1] < p->data[i] || p->data[2*i] < p->data[i]) { if (p->data[2*i + 1] < p->data[2*i]) { tmp = p->data[i]; p->data[i] = p->data[2*i + 1]; p->data[2*i + 1] = tmp; i = 2*i + 1; }else{ tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; } }else{ return; } }else{ //只有左节点 if (p->data[2*i] < p->data[i]) { tmp = p->data[i]; p->data[i] = p->data[2*i]; p->data[2*i] = tmp; i = 2*i; }else{ return; } } }}int findKthLargest(int* nums, int numsSize, int k){ struct MinHeap *heap; heap=(struct MinHeap *)malloc(sizeof(struct MinHeap)); if (heap == NULL) { printf("malloc error \n"); return 0; } heap->size = 0; heap->max = k + 1; heap->data = (int*)malloc(sizeof(int)*heap->max); if(heap->data == NULL) { printf("malloc error \n"); return 0; } heap->data[0] = 9999; for (int i = 0; i < numsSize; ++i) { if(i < k){ insert(heap, nums[i]); }else{ if(nums[i] > heap->data[1]){ delete(heap); insert(heap, nums[i]); } } } return heap->data[1];} ...

前言在学习ScheduledThreadPoolExecutor时，发现该线程池应用的队列为DelayedWorkQueue，DelayedWorkQueue是一个基于堆构造实现的延时队列和优先级队列，为了搞明确DelayedWorkQueue的实现，本篇文章先对堆数据结构进行学习，并且基于堆数据结构实现一个优先级队列以加深对堆数据结构的了解。 注释一. 堆的定义堆的定义如下所示。 堆是一颗齐全二叉树；父节点的元素如果总是大于等于子节点，称之为大根堆；父节点的元素如果总是小于等于子节点，称之为小根堆。要了解堆，首先须要理解什么是齐全二叉数。齐全二叉树定义为：如果二叉树的深度为h，那么除第h层外，其余第1到h-1层的节点数都达到最大值，第h层的所有节点都间断集中在右边。一颗齐全二叉树如下所示。 大根堆如下所示。 小根堆如下所示。 通常，堆中元素用一个数组来寄存。以上图的小根堆为例，节点旁边的数字代表以后节点在数组中的索引，能够发现其法则就是：依照层序遍历的形式遍历齐全二叉树，并每遍历一个节点就将以后节点的元素增加到数组中。所以上图的小根堆以数组示意如下。 最初，能够依据堆中某个节点在数组中的索引来计算这个节点的左右子节点和父节点在数组中的索引。计算的Java代码如下所示。 public class HeapTry { public int getLeft(int i) { return (i + 1) * 2 - 1; } public int getRigth(int i) { return (i + 1) * 2; } public int getParent(int i) { if (i == 0) { return 0; } return (i - 1) / 2; } ......}二. 堆的性质大根堆的性质：父节点的元素总是大于等于子节点。小根堆的性质：父节点的元素总是小于等于子节点。以小根堆为例，思考这样一个场景：给定一个小根堆，而后将根节点的元素删除并为根节点增加一个新的元素，新的元素不满足小于等于子节点的元素，此时小根堆的性质受到毁坏。图示如下。 对于上述场景，如果须要复原小根堆的性质，则以根节点作为第一个父节点，依照如下步骤执行。 将父节点与子节点的元素进行比拟并失去元素最小的节点，如果元素最小的节点是父节点，那么曾经复原小根堆的性质，执行完结；如果元素最小的节点是某个子节点，执行步骤2；将父节点与元素最小的子节点调换元素，因为调换元素后子节点有可能毁坏小根堆性质，因而从子节点开始，执行步骤1，直到复原小根堆性质。图示如下。 将复原小根堆性质的算法用Java代码实现如下。 ...

堆是一种常见的数据结构。其底层就是一个用数组实现的二叉树。然而没有父指针和子指针。 依据堆属性来进行排序。分为最小堆和最大堆。 最小堆：父节点的值比每个子节点的值都要小最大堆：父节点的值比每一个子节点的值都要大个别利用在以下场景： 疾速排序(取最大值 最小值)优先队列最大堆/最小堆spl中SplHeap抽象类实现了堆数据结构。SplMaxHeap和SplMinHeap继承自SplHeap，别离用来实现最大堆和最小堆。以下代码以最大堆为例做阐明，最小堆的时候和最大堆相似 // 最大堆$maxheap = new SplMaxHeap();// 插入节点并重建堆$maxheap->insert(12);$maxheap->insert(3);$maxheap->insert(222);$maxheap->insert(2);$maxheap->insert(312);$maxheap->insert(3);$maxheap->insert(13);$maxheap->insert(32);$maxheap->insert(3);$maxheap->insert(1);echo "最大推顶层元素：" . $maxheap->top() . PHP_EOL;// extract提取顶层元素// 取出节点并重建堆 echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "extract：" . $maxheap->extract() . PHP_EOL;echo "判断是否是空堆：" . PHP_EOL;var_dump($maxheap->isEmpty());// 当堆长度为0 的时候该堆为空堆echo "以后堆长度：" . $maxheap->count() . PHP_EOL;实现自定义推排序很多时候，单纯的数字大小比拟不能满足咱们对于堆数据结构的要求。比方咱们要基简单数组实现堆排序。SplHeap 类提供了compare形象办法，只有咱们实现本人的compare办法，就能够对任意数据类型进行最小堆最大堆排序 class MmaxHead extends SplHeap{ /** * 假如推中为关联数组 保留学生信息 依据成绩排名 * ['name'=>'Bob',score=>99.2] * * @param mixed $value1 * @param mixed $value2 * * @return int */ protected function compare($value1, $value2) { if ($value1['score'] > $value2['score']) { return 1; } elseif ($value1['score'] < $value2['score']) { return -1; } else { return 0; } }}$myheap = new MmaxHead();$myheap->insert(['name' => "bob1", "score" => 65]);$myheap->insert(['name' => "bob2", "score" => 34.3]);$myheap->insert(['name' => "bob3", "score" => 99.3]);$myheap->insert(['name' => "bob4", "score" => 23.4]);$myheap->insert(['name' => "bob5", "score" => 55]);$myheap->insert(['name' => "bob6", "score" => 66]);echo "问题最高的是" . PHP_EOL;var_dump($myheap->top());echo "顺次排名：" . PHP_EOL;while (!$myheap->isEmpty()) { var_dump($myheap->extract());}上一篇：双向链表,堆栈,队列 ...

前K个高频元素，这是一个很有代表性的问题，在理论生存中的利用场景其实也很多，比方微博里每天统计实时热点信息等。 先看下题： 给你一个整数数组 nums 和一个整数 k ，请你返回其中呈现频率前 k 高的元素。你能够按 任意程序 返回答案。 示例 1: 输出: nums = [1,1,1,2,2,3], k = 2输入: [1,2] 进阶：你所设计算法的工夫复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 <!--more--> 这道题的进阶要求工夫复杂度要优于O(nlogn)，那个别的快排，归并等就能够摈弃了。 而对于logn这个工夫复杂度咱们能很疾速的联想到二分，二叉搜寻树和堆。前两个想了下本场景实用不了。 使用堆因而咱们来推导下堆是否能够小于O(nlogn)？答案是必定的，堆能够在O(nlogk)(k<n)的工夫复杂度下等到后果. 桶排序那除了堆，咱们还有其余方法解决么？当然是有的，那就是桶排序。 思路咱们来理一下为什么能够用堆和桶排序两种实现失去答案。我的推导过程如下，大家能够当做参考，有好的计划也欢送和我探讨。 首先要统计前k个高频元素，咱们必须至多要将整个数组遍历一次。这个咱们很快就想到Map去记录每个元素呈现的次数，这个在字母异位词那题外面做过。 而后须要去从Map外面的value进行排序，排序后从大到小的前k个元素就是后果。而造成解法差别就是在排序的实现上。 你能够是各种排序，快排，归并，插入，桶，冒泡，希尔，堆排序等，而各种排序的工夫复杂度决定了最初的工夫复杂度。 而后因为在各个排序里小于进阶要求O(nlogn)的就只有堆排序的O(nlogk)和桶排序的O(n). 具体实现堆法一int[] topK = new int[k];Map<Integer, Integer> countMap = new HashMap<>();//第一个为数组值，第二个为呈现次数PriorityQueue<int[]> priQueue = new PriorityQueue<>((o1,o2)->(o2[1]-o1[1]));for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1);}for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) { int value = entry.getKey(), count = entry.getValue(); priQueue.offer(new int[]{value, count});}for (int i = 0; i < k; i++) { topK[i] = priQueue.poll()[0];}return topK;这个是我一开始写的一种谬误的写法，应该是初学者比拟容易犯的谬误。这个解法的工夫复杂度是O(nlogn)而不是O(nlogk)，至于为什么，看下一个解法我会阐明。而且这外面PriorityQueue的泛型类型用的是int[]，这个写的其实还是有点不优雅的，没必要新开构造去记录，间接用现有的Map.Entry<Integer,Integer>即可。 ...