Heap

原文地址：Go 逃逸分析 堆和栈要理解什么是逃逸分析会涉及堆和栈的一些基本知识，如果忘记的同学我们可以简单的回顾一下： 堆（Heap）：一般来讲是人为手动进行管理，手动申请、分配、释放。堆适合不可预知大小的内存分配，这也意味着为此付出的代价是分配速度较慢，而且会形成内存碎片。栈（Stack）：由编译器进行管理，自动申请、分配、释放。一般不会太大，因此栈的分配和回收速度非常快；我们常见的函数参数（不同平台允许存放的数量不同），局部变量等都会存放在栈上。栈分配内存只需要两个CPU指令：“PUSH”和“RELEASE”，分配和释放；而堆分配内存首先需要去找到一块大小合适的内存块，之后要通过垃圾回收才能释放。 通俗比喻的说，栈就如我们去饭馆吃饭，只需要点菜（发出申请）--》吃吃吃（使用内存）--》吃饱就跑剩下的交给饭馆（操作系统自动回收），而堆就如在家里做饭，大到家，小到买什么菜，每一个环节都需要自己来实现，但是自由度会大很多。 什么是逃逸分析在编译程序优化理论中，逃逸分析是一种确定指针动态范围的方法，简单来说就是分析在程序的哪些地方可以访问到该指针。 再往简单的说，Go是通过在编译器里做逃逸分析（escape analysis）来决定一个对象放栈上还是放堆上，不逃逸的对象放栈上，可能逃逸的放堆上；即我发现变量在退出函数后没有用了，那么就把丢到栈上，毕竟栈上的内存分配和回收比堆上快很多；反之，函数内的普通变量经过逃逸分析后，发现在函数退出后变量还有在其他地方上引用，那就将变量分配在堆上。做到按需分配（哪里的人民需要我，我就往哪去~~，一个党员的呐喊）。 为何需要逃逸分析ok，了解完堆和栈各自的优缺点后，我们就可以更好的知道逃逸分析存在的目的了： 减少gc压力，栈上的变量，随着函数退出后系统直接回收，不需要gc标记后再清除。减少内存碎片的产生。减轻分配堆内存的开销，提高程序的运行速度。如何确定是否逃逸在Go中通过逃逸分析日志来确定变量是否逃逸，开启逃逸分析日志： go run -gcflags '-m -l' main.go-m 会打印出逃逸分析的优化策略，实际上最多总共可以用 4 个 -m，但是信息量较大，一般用 1 个就可以了。-l 会禁用函数内联，在这里禁用掉内联能更好的观察逃逸情况，减少干扰。逃逸案例案例一：取地址发生逃逸package maintype UserData struct { Name string}func main() { var info UserData info.Name = "WilburXu" _ = GetUserInfo(info)}func GetUserInfo(userInfo UserData) *UserData { return &userInfo}执行 go run -gcflags '-m -l' main.go 后返回以下结果： # command-line-arguments.\main.go:14:9: &userInfo escapes to heap.\main.go:13:18: moved to heap: userInfoGetUserInfo函数里面的变量 userInfo 逃到堆上了（分配到堆内存空间上了）。GetUserInfo 函数的返回值为 *UserData 指针类型，然后 将值变量userInfo 的地址返回，此时编译器会判断该值可能会在函数外使用，就将其分配到了堆上，所以变量userInfo就逃逸了。 ...

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。且完全二叉树可以基于数组存储（父子节点的关系可以用数组下标表示），加持上堆的特性，故可以做堆排序。满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树；即每一层节点数都达到最大值；即深度为 k 的二叉树节点个数为 2^k-1，则为满二叉树；完全二叉树：若设二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，且第 k 层所有的结点都连续集中在最左边，这就是完全二叉树。堆：基于完全二叉树，分为大顶堆/小顶堆。各节点的数值皆大于其左右子节点的数值（大顶堆），或各节点的数值皆小于其左右子节点的数值（小顶堆）堆的特性大顶堆，节点的数值皆大于子节点的数值，下文都以大顶堆为实例讲解。因为是基于完全二叉树的，所以堆还有一些相应的特性：1、位序为 n 的节点，其父节点位序为 (int) n/22、位序为 n 的节点，其左子节点位序为 2n，右子节点位序为 2n+1（这是按照位序从1开始计算，但对编程语言不太友好，如果位序从0开始计算，则左子节点位序为 2n+1, 右子节点位序为 2n+2）按照数组下标的方式去编号的话如下： 0 / \ 1 2 / \ / \ 3 4 5 6 … / floor(n/2) … / n / \2n+1 2n+2可以发现，所有非叶子节点的序号都会落在 0 ~ (int) N/2-1 区间中，N为节点总数，例如：1、有4个节点，节点编号为03，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。2、有5个节点，节点编号为04，非叶子节点编号区间值为 01，即编号为 0，1 的节点为非叶子节点。3、有6个节点，节点编号为05，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。4、有7个节点，节点编号为06，非叶子节点编号区间值为 02，即编号为 0，1，2 的节点为非叶子节点。可以很方便的获取完全二叉树的非叶子节点的序号集合，从 k-1 层开始，依次将各非叶子节点及其左右子节点视为一个完全二叉树，将其调整至大顶堆，直至根节点，这时整个二叉树就是一个大顶堆我们有了非叶子节点的序号及获取左右节点序号的算式，所以很容易就可以将各非叶子节点及其左右子节点组成的完全二叉树调整至大顶堆。同时要注意如果非叶子节点同其左右子节点发生了调整，其左右子节点如果也是非叶子节点的话，也要检测是否破坏了堆特性，如破坏也需进行调整。堆排序堆排序：将初始待排序关键字序列(R0,R1….Rn-1)构建成大顶堆，此堆为初始的无序区将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R1,…,Rn-2)和新的有序区(Rn-1),且满足R[1,2…n-2]<=R[n-1]由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R1,…,Rn-2)调整为新堆，然后再次将R[0]与无序区最后一个元素交换，得到新的无序区(R0,R1….Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1（第n-1次调整时完全二叉树只有2个节点，即可有序化），则整个排序过程完成。即堆排序的过程:将待排序数组映射到完全二叉树中，通过调整完全二叉树至大顶堆，获取根节点的值（节点最大值）。那大顶堆的构建如何做呢？我用比较白话的方式讲一下1、从 k 层开始，将每一层子节点的最大值与其父节点的值进行比较调整（如发生交换且子节点为非叶子节点，也要检查子节点的树是否满足了父节点大于子节点的特性）2、重复第一步骤直到根节点，此时根节点的值即为完全二叉树节点中的最大值，即生成了大顶堆源码实例package mainimport ( “fmt”)func main() { // 待排序数组 go 的数组传参是值拷贝 我们用切片引用传值更方便些 var arr = []int{1, 6, 2, 4, 5, 3, 7, 9, 8} HeapSort(arr) fmt.Print(arr)}// 堆排序func HeapSort(arr []int) { arrLength := len(arr) // 每一次的堆构建都能得到一个节点中的最大值（根节点）对于N个待排序数列，N-1次堆构建即可得出有序数列 for i := 0; i < arrLength; i++ { // 无序区长度 arrLengthUnsorted := arrLength - i // 无序区构建为完全二叉树后非叶节点的下标的范围 unLeafNodeIndexRange := int(arrLengthUnsorted/2 - 1) // 从 k - 1 层开始 将非叶节点的子树分治递归构建成大顶堆 for j := unLeafNodeIndexRange; j >= 0; j– { HeapBuild(arr, j, arrLengthUnsorted) } // 打印下标 0 ~ arrLengthUnsorted-1 的数列 fmt.Println(“current heap: “, arr[0:arrLengthUnsorted]) // 一次大顶堆构建完成，根节点为堆最大值，与无序区堆的最后一个节点交换 // 无序区节点数-1 // 破坏了堆结构 开始对新无序区做大顶堆构建 SwapItemOfArray(arr, 0, arrLengthUnsorted-1) }}// 将子树调整为大顶堆func HeapBuild(arr []int, nodeIndex int, arrLengthUnsorted int) { // 完全二叉树子节点下标同父节点下标的关系式 leftChildNodeIndex, rightChildNodeIndex := nodeIndex2+1, nodeIndex2+2 // 防止子节点下标越界 && 子节点数值大于父节点 则交换节点值 if leftChildNodeIndex < arrLengthUnsorted && arr[leftChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, leftChildNodeIndex, nodeIndex) HeapBuild(arr, leftChildNodeIndex, arrLengthUnsorted) //左子树根节点改变 需调整堆结构 } if rightChildNodeIndex < arrLengthUnsorted && arr[rightChildNodeIndex] > arr[nodeIndex] { SwapItemOfArray(arr, rightChildNodeIndex, nodeIndex) HeapBuild(arr, rightChildNodeIndex, arrLengthUnsorted) //右子树根节点改变 需调整堆结构 }}// 交换数组两个元素func SwapItemOfArray(arr []int, indexX int, indexY int) { temp := arr[indexX] arr[indexX] = arr[indexY] arr[indexY] = temp} ...

题目要求Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the kth distinct element.Example:matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,return 13.Note: You may assume k is always valid, 1 ≤ k ≤ n2.在一个从左到右，从上到下均有序的二维数组中，找到从小到第k个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列1,2,2,3，则第三个数字是2而不是3。思路一：优先队列当涉及到从一个集合中查找一个元素这样的问题时，我们往往会立刻想到查找的几种方式：有序数组查找，无序数组查找，堆排序。这里如果将二维数组转化为一维有序数组，成本未免太大了。同理，将其中所有元素都转化为堆，也会存在内存不足的问题。因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第k个元素的值进行堆排序就可以了。 public int kthSmallest(int[][] matrix, int k) { //优先队列 PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>(); //将每一行的第一个元素放入优先队列中 for(int i = 0 ; i<matrix.length ; i++) { queue.offer(new Tuple(i, 0, matrix[i][0])); } //对优先队列执行k次取操作，取出来的就是第k个值 for(int i = 0 ; i<k-1 ; i++) { Tuple t = queue.poll(); //判断是否到达行尾，若没有，则将下一个元素作为潜在的第k个元素加入优先队列中 if(t.y == matrix[0].length-1) continue; queue.offer(new Tuple(t.x, t.y+1, matrix[t.x][t.y+1])); } return queue.poll().value; } /** * 存储矩阵中x，y和该下标上对应的值的Tuple */ public static class Tuple implements Comparable<Tuple>{ int x; int y; int value; public Tuple(int x, int y, int value) { this.x = x; this.y = y; this.value = value; } @Override public int compareTo(Tuple o) { // TODO Auto-generated method stub return this.value - o.value; } }思路二：二分法查找二分查找的核心问题在于，如何找到查找的上界和下届。这边我们可以矩阵中的最大值和最小值作为上界和下界。然后不停的与中间值进行比较，判断当前矩阵中小于该中间值的元素有几个，如果数量不足k，就将左指针右移，否则，就将右指针左移。直到左右指针相遇。这里需要注意，不能在数量等于k的时候就返回mid值，因为mid值不一定在矩阵中存在。 public int kthSmallest2(int[][] matrix, int k){ int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1]; while(low <= high) { int mid = low + (high - low) / 2; int count = 0; int i = matrix.length-1 , j = 0; //自矩阵左下角开始计算比mid小的数字的个数 while(i>=0 && j < matrix.length){ if(matrix[i][j]>mid) i–; else{ count+=i+1; j++; } } if(count < k) { low = mid + 1; }else{ high = mid - 1; } } return low; } ...

ProblemMedian is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.Examples: [2,3,4] , the median is 3[2,3], the median is (2 + 3) / 2 = 2.5Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.For example,Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.Window position Median————— —–[1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6Therefore, return the median sliding window as [1,-1,-1,3,5,6].Note: You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.Solutionclass Solution { //minHeap存大于median的数 //maxHeap存小于median的数 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b)->(b.compareTo(a))); public double[] medianSlidingWindow(int[] nums, int k) { int n = nums.length-k+1; if (n <= 0) return new double[0]; double[] res = new double[n]; for (int i = 0; i <= nums.length; i++) { if (i >= k) { res[i-k] = getMedian(); remove(nums[i-k]); } if (i < nums.length) { add(nums[i]); } } return res; } private void add(int num) { if (num < getMedian()) maxHeap.offer(num); else minHeap.offer(num); //保证minHeap总比maxHeap的size相等或多一个元素 if (maxHeap.size() > minHeap.size()) minHeap.offer(maxHeap.poll()); if (maxHeap.size() < minHeap.size()-1) maxHeap.offer(minHeap.poll()); } private void remove(int num) { if (num < getMedian()) maxHeap.remove(num); else minHeap.remove(num); if (maxHeap.size() > minHeap.size()) minHeap.offer(maxHeap.poll()); if (maxHeap.size() < minHeap.size()-1) maxHeap.offer(minHeap.poll()); } private double getMedian() { if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0; if (maxHeap.size() == minHeap.size()) return ((double) maxHeap.peek() + (double) minHeap.peek()) / 2.0; else return (double) minHeap.peek(); }} ...

题目要求You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.Define a pair (u,v) which consists of one element from the first array and one element from the second array.Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.两个单调递增的整数数组，现分别从数组1和数组2中取一个数字构成数对，求找到k个和最小的数对。思路这题采用最大堆作为辅助的数据结构能够完美的解决我们的问题。观察数组我们可以看到，从nums1中任意取一个数字，其和nums2中的数字组成的最小数对一定是<nums1[k], nums2[0]>，同理，我们可以知道，<nums1[k], nums2[t+1]>的值一定比nums1[k], nums2[t]大。因此在优先队列中，我们存储所有的nums1中数字所能够构成的最小数对。每从堆中取走一个数对<nums1[k], nums2[t]>，就插入<nums1[k], nums2[t+1]>，从而确保堆中的数对都可以从小到大遍历到。 public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) { List<int[]> result = new ArrayList<int[]>(); if(nums1.length == 0 || nums2.length == 0 || k == 0) return result; PriorityQueue<int[]> heap = new PriorityQueue<int[]>(new Comparator<int[]>(){ @Override public int compare(int[] o1, int[] o2) { return o1[0] + o1[1] - o2[0] - o2[1]; }}); for(int i = 0 ; i<nums1.length ; i++){ heap.offer(new int[]{nums1[i], nums2[0], 0}); } while(k– != 0 && !heap.isEmpty()) { int[] min = heap.poll(); result.add(new int[]{min[0], min[1]}); if(min[2] == nums2.length) continue; heap.offer(new int[]{min[0], nums2[min[2]+1], min[2] + 1}); } return result; } ...