【剑指offer2】 chap9 堆

• 堆是一种特殊的树形数据结构，通常用完全二叉树实现

• 分为最大堆和最小堆+应用

  • 最大堆：根节点是最大值，k个最小的元素，比堆顶大就不插入，剩下小的

  • 最小堆：根节点是最小值，k个最大的元素，比堆顶小就不插入，剩下大的

• 相关规律：元素下标为 i 

  • 父节点 为（i-1）/2

  • 左右子节点为 2i+1、2i+2

• 时间复杂度：O(log·n)

  • 插入

  • 删除

• Java接口类型：PriorityQueue（默认：最小堆）

  • 最大堆：调用构造函数传入Comparator

  • 常用函数：

• 剑指 Offer II 059. 数据流的第 K 大数值

//返回第k大的元素
class KthLargest {    
  private PriorityQueue minHeap;    
  private int size;    
  
  public KthLargest(int k, int[] nums) {        
    size = k;        
    minHeap = new PriorityQueue<>();        
    for(int num:nums){            
      add(num);        
    }    
  }    
  public int add(int val) {        
    if(minHeap.size() < size){            
      minHeap.offer(val);        
    }else if(val > minHeap.peek()){            
      minHeap.poll();            
      minHeap.offer(val);        
    }        
    return minHeap.peek();    
  }
}

• 剑指 Offer II 060. 出现频率最高的 k 个数字

//注意是同号
Queue> minHeap = new PriorityQueue<>(        (e1, e2) -> e1.getValue() - e2.getValue());

• 剑指 Offer II 061. 和最小的 k 个数对

//创建最小堆
Queue minHeap = new PriorityQueue<>(        
  (p1, p2) -> nums1[p1[0]] + nums2[p1[1]] - nums1[p2[0]] - nums2[p2[1]]);

• 剑指 Offer II 061. 和最小的 k 个数对

//创建最大堆（排序规则），注意这里是反向，和最小堆区分开来
Queue maxHeap = new PriorityQueue<>(
  (p1, p2) -> p2[0] + p2[1] - p1[0] - p1[1]);
——————————————————————————————————————————————————————————————————————————————
class Solution {
    public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //创建最大堆
        Queue maxHeap = new PriorityQueue<>(
                (p1, p2) -> p2[0] + p2[1] - p1[0] - p1[1]);
        //两层嵌套，注意只需要前k个
        for (int i = 0; i < Math.min(k, nums1.length); ++i) {
            for (int j = 0; j < Math.min(k, nums2.length); ++j) {
                //分两种情况
                if (maxHeap.size() < k) {
                    maxHeap.offer(new int[]{nums1[i], nums2[j]});
                } else {
                    int[] root = maxHeap.peek();
                    if (root[0] + root[1] > nums1[i] + nums2[j]) {
                        maxHeap.poll();
                        maxHeap.offer(new int[]{nums1[i], nums2[j]});
                    }
                }
            }
        }
        //结果输出
        List> result = new LinkedList<>();
        while (!maxHeap.isEmpty()) {
            int[] vals = maxHeap.poll();
            result.add(Arrays.asList(vals[0], vals[1]));
        }
        return result;
    }
}