堆 (优先级队列)

堆 (Heap) 是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

每一棵子树的根结点最大的堆 (即根节点大于等于子节点) 叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

优先级队列 (PriorityQueue) 与比较器

	public static class MyComparator implements Comparator<Integer> {

		// 负数,第一个参数在前
		// 正数,第二个参数在前
		// 0,不作交换
		@Override
		public int compare(Integer o1, Integer o2) {
			if (o1 > o2) {
				return -1;
			} else if (o2 > o1) {
				return 1;
			} else {
				return 0;
			}
		}

	}

	public static void main(String[] args) {
		PriorityQueue<Integer> heap = new PriorityQueue<>(); // 默认小根堆的优先队列
		heap.add(5);
		heap.add(3);
		heap.add(8);
		heap.add(1);
		System.out.println(heap.peek()); // 查看队头
		for (Integer integer : heap) {
			System.out.print(integer + " ");
		}
		System.out.println();

//		PriorityQueue<Integer> heap2 = new PriorityQueue<>(new MyComparator()); // 大根堆的优先队列 构造时传入比较器
		PriorityQueue<Integer> heap2 = new PriorityQueue<>((o1,o2)-> o2-o1); // 大根堆的优先队列 构造时传入比较器
		heap2.add(5);
		heap2.add(3);
		heap2.add(8);
		heap2.add(1);
		System.out.println(heap2.peek()); // 查看队头
		for (Integer integer : heap2) {
			System.out.print(integer + " ");
		}
		System.out.println();

	}

数组实现大根堆

	public static class MyMaxheap {
		private int[] heap;
		private final int limit; // heap的最大值
		private int size; // heap当前大小

		public MyMaxheap(int limit) {
			this.limit = limit;
			heap = new int[limit];
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

		public void push(int value) {
			if (size == limit) {
				throw new RuntimeException("当前堆已满!");
			}
			heap[size] = value;
			heapInsert(heap, size++);
		}

		public int pop() {
			int ans = heap[0];
			swap(heap, 0, --size);
			heapify(heap, 0, size);
			return ans;
		}

		// 向下沉
		private void heapify(int[] heap, int index, int size) {
			int left = index * 2 + 1;
			while (left < size) { // 存在左孩子时 有可能存在右孩子
				int largest = left + 1 < size && heap[left + 1] > heap[left] ? left + 1 : left; // 判断是否有右孩子 并且挑出最大值的下标
				largest = heap[largest] > heap[index] ? largest : index; // 如果孩子大于当前push节点 则赋值下标 否则下标为index
				if (largest == index) { // 最大值是自身 无需下沉
					break;
				}
				swap(heap, largest, index); // 存在孩子大于当前push节点 交换并下沉(使最大值孩子成为根节点,push节点成为孩子)
				index = largest; // 继续与下面孩子进行比较
				left = index * 2 + 1; // 是否存在左孩子 由while循环决定

			}

		}

		private void swap(int[] heap, int i, int j) {
			int temp = heap[i];
			heap[i] = heap[j];
			heap[j] = temp;
		}

		// 向上移动
		private void heapInsert(int[] heap, int index) {
			while (heap[index] > heap[(index - 1) / 2]) { // 如果当前push的节点比它的根节点大则
				swap(heap, index, (index - 1) / 2); // 进行交换
				index = (index - 1) / 2;
			}
		}

	}
	
	public static class RightMaxHeap {
		private int[] arr;
		private final int limit;
		private int size;

		public RightMaxHeap(int limit) {
			arr = new int[limit];
			this.limit = limit;
			size = 0;
		}

		public boolean isEmpty() {
			return size == 0;
		}

		public boolean isFull() {
			return size == limit;
		}

		public void push(int value) {
			if (size == limit) {
				throw new RuntimeException("heap is full");
			}
			arr[size++] = value;
		}

		public int pop() {
			int maxIndex = 0;
			for (int i = 1; i < size; i++) {
				if (arr[i] > arr[maxIndex]) {
					maxIndex = i;
				}
			}
			int ans = arr[maxIndex];
			arr[maxIndex] = arr[--size];
			return ans;
		}

	}

	public static class MyComparator implements Comparator<Integer> {

		@Override
		public int compare(Integer o1, Integer o2) {
			return o2 - o1;
		}

	}

	public static void main(String[] args) {

		// 小根堆
		PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
		heap.add(5);
		heap.add(5);
		heap.add(5); //堆是可以添加重复元素的
		heap.add(3);
		// 5 , 3
		System.out.println(heap.peek());
		heap.add(7);
		heap.add(0);
		heap.add(7);
		heap.add(0);
		heap.add(7);
		heap.add(0);
		System.out.println(heap.peek());
		while (!heap.isEmpty()) {
			System.out.println(heap.poll());
		}

		int value = 1000;
		int limit = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			int curLimit = (int) (Math.random() * limit) + 1;
			MyMaxheap my = new MyMaxheap(curLimit);
			RightMaxHeap test = new RightMaxHeap(curLimit);
			int curOpTimes = (int) (Math.random() * limit);
			for (int j = 0; j < curOpTimes; j++) {
				if (my.isEmpty() != test.isEmpty()) {
					System.out.println("Oops!");
				}
				if (my.isFull() != test.isFull()) {
					System.out.println("Oops!");
				}
				if (my.isEmpty()) {
					int curValue = (int) (Math.random() * value);
					my.push(curValue);
					test.push(curValue);
				} else if (my.isFull()) {
					if (my.pop() != test.pop()) {
						System.out.println("Oops!");
					}
				} else {
					if (Math.random() < 0.5) {
						int curValue = (int) (Math.random() * value);
						my.push(curValue);
						test.push(curValue);
					} else {
						if (my.pop() != test.pop()) {
							System.out.println("Oops!");
						}
					}
				}
			}
		}
		System.out.println("finish!");

	}

堆排序

1. 0~N 范围上变成大根堆，heapsize = 需排序数组长度
2. 0 与 N 进行交换值
3. 0~N-1 范围上变成大根堆，再进行 0 与 N-1 交换，直到 heapsize-- 成为 1 (只剩下 0~0 没进行 heapInster)

时间复杂程度：O (N*logN)

不断的缩小要排序数组的大小 每次将堆顶 (大根堆即最大值) 放置到末尾 并断开连接 (下次排序此元素不参与)

自底向上变成大根堆

在上面堆排序我们使用的从根节点到底部叶子节点 headpSort 时间复杂程度为：O (N*logN)

而我们从底部 headpSort 时 叶子节点只需根自己比较即是大根堆 时间复杂程度为：O (N) 因为大量的节点存在于叶子节点 N 个数就要操作 N*logN 次 而自底向上只需要 N 次操作

注意：自底向上建堆必须给定一个具体数组（必须知晓叶子节点），无法像自顶向下建堆灵活一个一个建立

public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}

		// 自顶向下插入堆 O(N*logN)
//	 for (int i = 0; i < arr.length; i++) {
//		heapInster(arr,i);
//	}

		// 自底向上推进堆 O(N)
		for (int i = arr.length - 1; i >= 0; i--) { // 整个堆的最后的叶子节点此操作 无需下沉
			heapify(arr, i, arr.length);
		}
		int heapsize = arr.length;
		swap(arr, 0, --heapsize); // heapInster后第一个为大根堆最大值 直接丢到数组末端并heapsize-- 下次操作不包括此元素
		while (heapsize > 0) {
			heapify(arr, 0, heapsize);// 向下沉
			swap(arr, 0, --heapsize); // 交换
		}
	}

	// 向下移动
	private static void heapify(int[] arr, int i, int heapsize) {
		int left = i * 2 + 1;
		while (left < heapsize) {
			int largest = left + 1 < heapsize && arr[left + 1] > arr[left] ? left + 1 : left;
			largest = arr[i] < arr[largest] ? largest : i;
			if (largest == i) {
				break;
			}
			swap(arr, i, largest);
			i = largest;
			left = i * 2 + 1;

		}

	}

	// 向上移动
	private static void heapInster(int[] arr, int i) {
		while (arr[i] > arr[(i - 1) / 2]) {
			swap(arr, i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;

	}

线段最大重合问题

给定很多线段，每个线段都有两个数[start, end]，
表示线段开始位置和结束位置，左右都是闭区间
规定：
1）线段的开始和结束位置一定都是整数值
2）线段重合区域的长度必须>=1
返回线段最多重合区域中，包含了几条线段

	//暴力解法
	public static int maxCover1(int[][] lines) {
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < lines.length; i++) { //找出线段最小值和最大值
			min = Math.min(min, lines[i][0]);
			max = Math.max(max, lines[i][1]);
		}
		int cover = 0;
		for (double p = min + 0.5; p < max; p += 1) {  //每个隔0.5
			int cur = 0;
			for (int i = 0; i < lines.length; i++) {
				if (lines[i][0] < p && lines[i][1] > p) { //数有多少条线处于这0.5中 即有多少条重合线段
					cur++;
				}
			}
			cover = Math.max(cover, cur); //返回最大重合的数
		}
		return cover;
	}
	
	
	//堆解法
	public static int maxCovcer2(int[][] lines) {
		//比如, m = { {5,7}, {1,4}, {2,6} } 跑完如下的code之后变成：{ {1,4}, {2,6}, {5,7} }
		Arrays.sort(lines,(o1,o2) -> (o1[0] - o2[0])); //以线段开始点 排序
		//准备小根堆
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
		int max = 0;
		for (int[] line : lines) {
			//堆不为空 并且当前线段开头 大于等于 堆顶
			while(!heap.isEmpty() && heap.peek() <= line[0]) {
				heap.poll(); //删除堆顶
			}
			heap.add(line[1]); //添加线段结束点到堆中
			max = Math.max(max, heap.size());
		}
		return max;
	}

加强堆

1. 系统提供的堆只能删除头节点 (pop) 无法快速删除其他位置的节点
2. 加强堆建立一个反向索引 通过值查找堆中索引 可以更快删除 删除之后与最后一个节点进行交换 再进行上移和下沉 保存堆的完整结构

需要提供一个比较器，来定义大根堆还是小根堆

public class HeapGreater<T> {

	private ArrayList<T> heap;
	private HashMap<T, Integer> indexMap; // 反向索引表
	private int heapSize;
	private Comparator<? super T> comp;

	public HeapGreater(Comparator<T> comp) {
		heap = new ArrayList<>();
		indexMap = new HashMap<>();
		heapSize = 0;
		this.comp = comp;
	}

	public boolean isEmpty() {
		return heapSize == 0;
	}

	public int size() {
		return heapSize;
	}

	public boolean contains(T obj) { // 返回此元素的索引是否存在
		return indexMap.containsKey(obj);
	}

	public T peek() {
		return heap.get(0); // 获取堆顶
	}

	public void push(T obj) { // 往堆添加元素
		heap.add(obj);
		indexMap.put(obj, heapSize); // 反向索引表
		heapInsert(heapSize++);
	}

	public void heapInsert(int index) {
		// 使用比较器比较当前元素 与它的根节点大小,当前元素大则进入循环体
		while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
			swap(index, (index - 1) / 2);
			index = (index - 1) / 2;
		}

	}

	public void swap(int i, int j) {
		T o1 = heap.get(i); // 获取值
		T o2 = heap.get(j);
		heap.set(i, o2); // 增加替换指定索引
		heap.set(j, o1);
		indexMap.put(o2, i);// 更新反向索引
		indexMap.put(o1, j);

	}

	public T pop() { // 删除并返回堆顶
		T ans = heap.get(0);
		swap(0, heapSize - 1); // 堆顶与尾元素交换
		indexMap.remove(ans); // 删除索引
		heap.remove(--heapSize); // 与尾元素断开连接
		heapify(0);
		return ans;
	}

	// 下沉
	private void heapify(int index) {
		int left = index * 2 + 1;
		while (left < heapSize) {
			// 查找左右孩子最大值下标
			int best = left + 1 < heapSiz e && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
			best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
			if (best == index) {
				break;
			}
			// 与当前节点交换
			swap(best, index);
			index = best; // 继续下沉
			left = index * 2 + 1;

		}

	}

	// 从堆中删除用户给定的值 并保存堆完整性
	public void remove(T obj) {
		T replace = heap.get(heapSize - 1); // 获取尾元素
		int index = indexMap.get(obj); // 获取要删除的索引
		indexMap.remove(obj); // 删除索引
		heap.remove(--heapSize); // 删除尾元素 前面已经缓存了尾元素值
		if (obj != replace) {
			heap.set(index, replace); // 直接更新堆替换为尾元素
			indexMap.put(replace, index); // 更新索引表
			resign(replace);

		}

	}

	// 更新了一个堆中元素 保存堆完整性
	public void resign(T replace) {
		heapInsert(indexMap.get(replace)); // 上移
		heapify(indexMap.get(replace)); // 下沉总会发生一个事件
	}

	public List<T> getAllElements() {
		List<T> ans = new ArrayList<>();
		for (T t : heap) {
			ans.add(t);
		}
		return ans;
	}

}

加强堆面试题

做一个加强堆的题目，给定一个整型数组，int[] arr；和一个布尔类型数组，boolean[] op
两个数组一定等长，假设长度为N，arr[i]表示客户编号，op[i]表示客户操作
arr= [3,3,1,2,1,2,5…
op = [T,T,T,T,F,T,F…
依次表示：
3用户购买了一件商品
3用户购买了一件商品
1用户购买了一件商品
2用户购买了一件商品
1用户退货了一件商品
2用户购买了一件商品
5用户退货了一件商品…
一对arr[i]和op[i]就代表一个事件：
用户号为arr[i]，op[i] == T就代表这个用户购买了一件商品
op[i] == F就代表这个用户退货了一件商品
现在你作为电商平台负责人，你想在每一个事件到来的时候，
都给购买次数最多的前K名用户颁奖。
所以每个事件发生后，你都需要一个得奖名单（得奖区）。
得奖系统的规则：
1，如果某个用户购买商品数为0，但是又发生了退货事件，
     则认为该事件无效，得奖名单和上一个事件发生后一致，例子中的5用户
2，某用户发生购买商品事件，购买商品数+1，发生退货事件，购买商品数-1
3，每次都是最多K个用户得奖，K也为传入的参数
      如果根据全部规则，得奖人数确实不够K个，那就以不够的情况输出结果
4，得奖系统分为得奖区和候选区，任何用户只要购买数>0，
      一定在这两个区域中的一个
5，购买数最大的前K名用户进入得奖区，
      在最初时如果得奖区没有到达K个用户，那么新来的用户直接进入得奖区
6，如果购买数不足以进入得奖区的用户，进入候选区
7，如果候选区购买数最多的用户，已经足以进入得奖区，
     该用户就会替换得奖区中购买数最少的用户（大于才能替换），
     如果得奖区中购买数最少的用户有多个，就替换最早进入得奖区的用户
     如果候选区中购买数最多的用户有多个，机会会给最早进入候选区的用户
8，候选区和得奖区是两套时间，
     因用户只会在其中一个区域，所以只会有一个区域的时间，另一个没有
     从得奖区出来进入候选区的用户，得奖区时间删除，
     进入候选区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
     从候选区出来进入得奖区的用户，候选区时间删除，
     进入得奖区的时间就是当前事件的时间（可以理解为arr[i]和op[i]中的i）
9，如果某用户购买数==0，不管在哪个区域都离开，区域时间删除，
     离开是指彻底离开，哪个区域也不会找到该用户
     如果下次该用户又发生购买行为，产生>0的购买数，
     会再次根据之前规则回到某个区域中，进入区域的时间重记
请遍历arr数组和op数组，遍历每一步输出一个得奖名单
public List<List<Integer>>  topK (int[] arr, boolean[] op, int k)

// 封装对象
	public static class Customer {
		public int id;
		public int buy;
		public int enterTime;

		public Customer(int id, int buy, int enterTime) {
			this.id = id;
			this.buy = buy;
			this.enterTime = enterTime;
		}

	}

	public static class CandidateComparator implements Comparator<Customer> {

		@Override
		public int compare(Customer o1, Customer o2) {

			// 如果待选区的购买时间相同 则以购买金额比较(从大到小排序 第一个元素为最大值) 否则以时间则比较
			return o1.buy != o2.buy ? (o2.buy - o1.buy) : (o1.enterTime - o2.enterTime);
		}

	}

	public static class DaddyComparator implements Comparator<Customer> {

		@Override
		public int compare(Customer o1, Customer o2) {
			// 如果待选区的购买时间相同 则以购买金额比较(从小到大排序 第一个元素为最小值) 否则以时间则比较
			return o1.buy != o2.buy ? (o1.buy - o2.buy) : (o1.enterTime - o2.enterTime);
		}

	}

	public static class WhoYourDaddy {
		private HashMap<Integer, Customer> customers; // 反向索引表
		private HeapGreater<Customer> candHeap; // 待选区
		private HeapGreater<Customer> daddyHeap; // 得奖区
		private final int daddyLimit; // 得奖区大小

		public WhoYourDaddy(int daddyLimit) {
			this.daddyLimit = daddyLimit;
			customers = new HashMap<>();
			candHeap = new HeapGreater<>(new CandidateComparator());
			;
			daddyHeap = new HeapGreater<>(new DaddyComparator());
		}

		public void operate(int time, int id, boolean buyOrRefund) {
			// 退货操作 并且索引表(即两个区都没有记录)没有 不用进行扣减不存在负数的记录
			if (!buyOrRefund && !customers.containsKey(id)) {
				return;
			}
			// 两个区都不存在此记录 先精灵索引
			if (!customers.containsKey(id)) {
				// 以id为索引 初始化值后面修改
				customers.put(id, new Customer(id, 0, 0));
			}
			Customer c = customers.get(id); // 以id在索引表查找出对象 进行修改
			if (buyOrRefund) {
				// 是购买记录(即为T) 购买数++
				c.buy++;
			} else {
				// 是退货记录
				c.buy--;
			}
			if (c.buy == 0) {
				// 如果目前对象进行增减操作后购买数为仍0 则要移除 从索引表删除
				customers.remove(id);
			}

			//多种情况分别讨论
			if (!candHeap.contains(c) && !daddyHeap.contains(c)) {
				//此对象 待选区和得奖区都不存在 
				
				//得奖区有空闲位置 直接丢入得奖区
				if(daddyHeap.size() < daddyLimit) {
					c.enterTime = time;
					daddyHeap.push(c);
				} else {
					//得奖区已满 丢人待选区
					c.enterTime = time;
					candHeap.push(c);
					
				}
			} else if(candHeap.contains(c)) {
				//此对象 存在于待选区
				
				if(c.buy == 0) {
					//为0 从待选区移除
					candHeap.remove(c);
				} else {
					//进行 上移和下沉操作 重新保持堆的完整性
					candHeap.resign(c);
				}
			} else {
				//此对象 存在于得奖区
				if(c.buy == 0) {
					daddyHeap.remove(c);
				} else {
					daddyHeap.resign(c);
				}
			}
			
			daddyMove(time); //本次添加对象已经整合完毕 进行待选区与得奖区的比较
		}

		private void daddyMove(int time) {
			//待选区为空 结束操作
			if(candHeap.isEmpty()) {
				return;
			}
			//如果得奖区还有空位 则以待选区 堆顶元素 丢入得奖区
			if(daddyHeap.size() < daddyLimit) {
				Customer p =  candHeap.pop(); //删除并获取待选区堆顶
				p.enterTime = time; //重新设置当前为当前时间
				daddyHeap.push(p); //丢入得奖区
			} else {
				//比较 待选区最大值 与 得奖区最小值的大小
				if(candHeap.peek().buy > daddyHeap.peek().buy) {
					Customer oldDaddy = daddyHeap.pop(); //得奖区最小值
					Customer newDaddy = candHeap.pop(); //待选区最大值
					oldDaddy.enterTime = time; //重置时间
					newDaddy.enterTime = time;
					daddyHeap.push(newDaddy); //将待选区最大值丢入得奖区
					candHeap.push(oldDaddy); //将得奖区最小值丢回待选区
				}
			}
			
		}
		
		//获取得奖区的全部id(用户)
		public List<Integer> getDaddies(){
			List<Customer> customers = daddyHeap.getAllElements(); //获取得奖区的全部对象
			List<Integer> ans = new ArrayList<>();
			for (Customer c : customers) {
				ans.add(c.id);
			}
			return ans;
		}

	}
	
	public static List<List<Integer>> topK(int[] arr,boolean[] op,int k){
		List<List<Integer>> ans = new ArrayList<>();
		WhoYourDaddy whoDaddies = new WhoYourDaddy(k);
		for (int i = 0; i < arr.length; i++) {
			whoDaddies.operate(i, arr[i], op[i]);
			ans.add(whoDaddies.getDaddies());
		}
		return ans;
	}
	
	


	// 暴力破解法
	// 干完所有的事，模拟，不优化
		public static List<List<Integer>> compare(int[] arr, boolean[] op, int k) {
			HashMap<Integer, Customer> map = new HashMap<>();
			ArrayList<Customer> cands = new ArrayList<>();
			ArrayList<Customer> daddy = new ArrayList<>();
			List<List<Integer>> ans = new ArrayList<>();
			for (int i = 0; i < arr.length; i++) {
				int id = arr[i];
				boolean buyOrRefund = op[i];
				if (!buyOrRefund && !map.containsKey(id)) {
					ans.add(getCurAns(daddy));
					continue;
				}
				// 没有发生：用户购买数为0并且又退货了
				// 用户之前购买数是0，此时买货事件
				// 用户之前购买数>0， 此时买货
				// 用户之前购买数>0, 此时退货
				if (!map.containsKey(id)) {
					map.put(id, new Customer(id, 0, 0));
				}
				// 买、卖
				Customer c = map.get(id);
				if (buyOrRefund) {
					c.buy++;
				} else {
					c.buy--;
				}
				if (c.buy == 0) {
					map.remove(id);
				}
				// c
				// 下面做
				if (!cands.contains(c) && !daddy.contains(c)) {
					if (daddy.size() < k) {
						c.enterTime = i;
						daddy.add(c);
					} else {
						c.enterTime = i;
						cands.add(c);
					}
				}
				cleanZeroBuy(cands);
				cleanZeroBuy(daddy);
				cands.sort(new CandidateComparator());
				daddy.sort(new DaddyComparator());
				move(cands, daddy, k, i);
				ans.add(getCurAns(daddy));
			}
			return ans;
		}

		public static void move(ArrayList<Customer> cands, ArrayList<Customer> daddy, int k, int time) {
			if (cands.isEmpty()) {
				return;
			}
			// 候选区不为空
			if (daddy.size() < k) {
				Customer c = cands.get(0);
				c.enterTime = time;
				daddy.add(c);
				cands.remove(0);
			} else { // 等奖区满了，候选区有东西
				if (cands.get(0).buy > daddy.get(0).buy) {
					Customer oldDaddy = daddy.get(0);
					daddy.remove(0);
					Customer newDaddy = cands.get(0);
					cands.remove(0);
					newDaddy.enterTime = time;
					oldDaddy.enterTime = time;
					daddy.add(newDaddy);
					cands.add(oldDaddy);
				}
			}
		}

		public static void cleanZeroBuy(ArrayList<Customer> arr) {
			List<Customer> noZero = new ArrayList<Customer>();
			for (Customer c : arr) {
				if (c.buy != 0) {
					noZero.add(c);
				}
			}
			arr.clear();
			for (Customer c : noZero) {
				arr.add(c);
			}
		}

		public static List<Integer> getCurAns(ArrayList<Customer> daddy) {
			List<Integer> ans = new ArrayList<>();
			for (Customer c : daddy) {
				ans.add(c.id);
			}
			return ans;
		}

		// 为了测试
		public static class Data {
			public int[] arr;
			public boolean[] op;

			public Data(int[] a, boolean[] o) {
				arr = a;
				op = o;
			}
		}

		// 为了测试
		public static Data randomData(int maxValue, int maxLen) {
			int len = (int) (Math.random() * maxLen) + 1;
			int[] arr = new int[len];
			boolean[] op = new boolean[len];
			for (int i = 0; i < len; i++) {
				arr[i] = (int) (Math.random() * maxValue);
				op[i] = Math.random() < 0.5 ? true : false;
			}
			return new Data(arr, op);
		}

		// 为了测试
		public static boolean sameAnswer(List<List<Integer>> ans1, List<List<Integer>> ans2) {
			if (ans1.size() != ans2.size()) {
				return false;
			}
			for (int i = 0; i < ans1.size(); i++) {
				List<Integer> cur1 = ans1.get(i);
				List<Integer> cur2 = ans2.get(i);
				if (cur1.size() != cur2.size()) {
					return false;
				}
				cur1.sort((a, b) -> a - b);
				cur2.sort((a, b) -> a - b);
				for (int j = 0; j < cur1.size(); j++) {
					if (!cur1.get(j).equals(cur2.get(j))) {
						return false;
					}
				}
			}
			return true;
		}

		public static void main(String[] args) {
			int maxValue = 10;
			int maxLen = 100;
			int maxK = 6;
			int testTimes = 100000;
			System.out.println("测试开始");
			for (int i = 0; i < testTimes; i++) {
				Data testData = randomData(maxValue, maxLen);
				int k = (int) (Math.random() * maxK) + 1;
				int[] arr = testData.arr;
				boolean[] op = testData.op;
				List<List<Integer>> ans1 = topK(arr, op, k);
				List<List<Integer>> ans2 = compare(arr, op, k);
				if (!sameAnswer(ans1, ans2)) {
					for (int j = 0; j < arr.length; j++) {
						System.out.println(arr[j] + " , " + op[j]);
					}
					System.out.println(k);
					System.out.println(ans1);
					System.out.println(ans2);
					System.out.println("出错了！");
					break;
				}
			}
			System.out.println("测试结束");
		}

23. 合并 K 个升序链表 (opens new window)

public class ListNode {
		int val;
		ListNode next;

		ListNode() {
		}

		ListNode(int val) {
			this.val = val;
		}

		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}

	public ListNode mergeKLists(ListNode[] lists) {
		PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((o1, o2) -> o1.val - o2.val); //自定义比较器的最小堆
		for (ListNode listNode : lists) { //遍历链表数组
			if (listNode != null) { 
				heap.add(listNode); //非空则push到最小堆
			}
		}
		if (heap.isEmpty()) { //堆中没有
			return null;
		}
		ListNode head = heap.poll(); // 弹出最小堆头
		ListNode pre = head;
		if (pre.next != null) {
			heap.add(pre.next); // 如果pre下一跳 不为空 直接push到最小堆中
		}
		while (!heap.isEmpty()) { //最小堆不为空
			ListNode cur = heap.poll(); //弹出栈顶 即最小值
			pre.next = cur; //下一跳 连接
			pre = cur; //更新当前节点
			if (cur.next != null) { //当前节点 下一跳不为空则添加到最小堆中
				heap.add(cur.next);
			}
		}
		return head;

	}