Priority-Queue

介绍优先级队列，是0个或多个元素的集合，集合中的每个元素都有一个权重值，每次出队都弹出优先级最大或最小的元素。 一般来说，优先级队列使用堆来实现。 源码分析主要属性 // 默认容量 private static final int DEFAULT_INITIAL_CAPACITY = 11; // 存储元素的地方 transient Object[] queue; // non-private to simplify nested class access // 元素个数 private int size = 0; // 比较器 private final Comparator<? super E> comparator; // 修改次数 transient int modCount = 0; // non-private to simplify nested class access默认容量是11；queue，元素存储在数组中，这跟我们之前说的堆一般使用数组来存储是一致的；comparator，比较器，在优先级队列中，也有两种方式比较元素，一种是元素的自然顺序，一种是通过比较器来比较；modCount，修改次数，有这个属性表示PriorityQueue也是fast-fail的；入队入队有两个方法，add(E e)和offer(E e)，两者是一致的，add(E e)也是调用的offer(E e)。 public boolean add(E e) { return offer(e);}public boolean offer(E e) { // 不支持null元素 if (e == null) throw new NullPointerException(); modCount++; // 取size int i = size; // 元素个数达到最大容量了，扩容 if (i >= queue.length) grow(i + 1); // 元素个数加1 size = i + 1; // 如果还没有元素 // 直接插入到数组第一个位置 // 这里跟我们之前讲堆不一样了 // java里面是从0开始的 // 我们说的堆是从1开始的 if (i == 0) queue[0] = e; else // 否则，插入元素到数组size的位置，也就是最后一个元素的下一位 // 注意这里的size不是数组大小，而是元素个数 // 然后，再做自下而上的堆化 siftUp(i, e); return true;}private void siftUp(int k, E x) { // 根据是否有比较器，使用不同的方法 if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x);}@SuppressWarnings("unchecked")private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { // 找到父节点的位置 // 因为元素是从0开始的，所以减1之后再除以2 int parent = (k - 1) >>> 1; // 父节点的值 Object e = queue[parent]; // 比较插入的元素与父节点的值 // 如果比父节点大，则跳出循环 // 否则交换位置 if (key.compareTo((E) e) >= 0) break; // 与父节点交换位置 queue[k] = e; // 现在插入的元素位置移到了父节点的位置 // 继续与父节点再比较 k = parent; } // 最后找到应该插入的位置，放入元素 queue[k] = key;}入队不允许null元素；如果数组不够用了，先扩容；如果还没有元素，就插入下标0的位置；如果有元素了，就插入到最后一个元素往后的一个位置（实际并没有插入哈）；自下而上堆化，一直往上跟父节点比较；如果比父节点小，就与父节点交换位置，直到出现比父节点大为止；由此可见，PriorityQueue是一个小顶堆。扩容private void grow(int minCapacity) { // 旧容量 int oldCapacity = queue.length; // Double size if small; else grow by 50% // 旧容量小于64时，容量翻倍 // 旧容量大于等于64，容量只增加旧容量的一半 int newCapacity = oldCapacity + ((oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code // 检查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // 创建出一个新容量大小的新数组并把旧数组元素拷贝过去 queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}当数组比较小（小于64）的时候每次扩容容量翻倍；当数组比较大的时候每次扩容只增加一半的容量；出队出队有两个方法，remove()和poll()，remove()也是调用的poll()，只是没有元素的时候抛出异常。 ...

PHP 的 SPL 库内置了 SplPriorityQueue优先级队列，是以Heap堆特性实现的，默认为MaxHeap模式，即priority越大越优先出队，同时可以通过重写compare方法来使用MinHeap（优先级越低越优先出队，场景貌似很少吧）。SplPriorityQueue堆特性这里需要注意并理解：SplPriorityQueue是以堆数据结构来实现的，当我们出队时会拿出堆顶的元素，此时堆的特性被破坏，堆会进行相应的调整至稳定态(MaxHeap or MinHeap)，即会将最后一个元素替换到堆顶，然后进行稳定态验证，不符合堆特性则继续调整，或者我们就得到了一个稳定态的堆，所以当优先级相同，出队顺序并不会按照入队顺序。源码示例：<?php$splPriorityQueue = new \SplPriorityQueue();// 设定返回数据的meta信息// \SplPriorityQueue::EXTR_DATA 默认 只返回数// \SplPriorityQueue::EXTR_PRIORITY 只返回优先级// \SplPriorityQueue::EXTR_BOTH 返回数据和优先级// $splPriorityQueue->setExtractFlags(\SplPriorityQueue::EXTR_DATA);$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 1);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 1);$splPriorityQueue->insert(“task5”, 1);echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;echo $splPriorityQueue->extract() . PHP_EOL;//执行结果task1task5task4task3task2可以看到，虽然 5 个任务的优先级相同，但队列并没有按照入队顺序返回数据，因为堆的特性使然：1、入队 task1, task2, task3, task4, task5，因为优先级相同，所以堆一直处于稳定态。2、出队，得 task1，堆先将结构调整为 task5, task2, task3, task4，已然达到了稳定态。3、出队，得 task5，堆先将结构调整为 task4, task2, task3，已然达到了稳定态。4、出队，得 task4，堆先将结构调整为 task3, task2，已然达到了稳定态。5、出队，得 task3，堆先将结构调整为 task2，已然达到了稳定态。4、出队，得 task2。Iterator, CountableSplPriorityQueue实现了 Iterator, Countable接口，所以我们可以foreach/count函数操作它，或者使用rewind,valid,current,next/count方法。注意，因为是堆实现，所以rewind方法是一个no-op没有什作用的操作，因为头指针始终指向堆顶，即current始终等于top，不像List只是游走指针，出队是会删除堆元素的，extract = current + next（current出队，从堆中删除）。<?php$splPriorityQueue = new \SplPriorityQueue();$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5);echo “Countable： " . count($splPriorityQueue) . PHP_EOL;// 迭代的话会删除队列元素 current 指针始终指向 top 所以 rewind 没什么意义for ($splPriorityQueue->rewind(); $splPriorityQueue->valid();$splPriorityQueue->next()) { var_dump($splPriorityQueue->current()); var_dump($splPriorityQueue->count()); $splPriorityQueue->rewind();}var_dump(“is empty:” . $splPriorityQueue->isEmpty());Extract出队extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据。<?php$splPriorityQueue = new \SplPriorityQueue();// data priority$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5);echo “Countable： " . count($splPriorityQueue) . PHP_EOL;while (! $splPriorityQueue->isEmpty()) { var_dump($splPriorityQueue->extract()); echo $splPriorityQueue->count() . PHP_EOL;}自定义优先级处理方式重写compare方法定义自己的优先级处理机制。<?phpclass CustomedSplPriorityQueue extends SplPriorityQueue{ public function compare($priority1, $priority2): int { // return $priority1 - $priority2;//高优先级优先 return $priority2 - $priority1;//低优先级优先 }}$splPriorityQueue = new \CustomedSplPriorityQueue();$splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);$splPriorityQueue->insert(“task1”, 1);$splPriorityQueue->insert(“task2”, 2);$splPriorityQueue->insert(“task3”, 1);$splPriorityQueue->insert(“task4”, 4);$splPriorityQueue->insert(“task5”, 5); echo “Countable： " . count($splPriorityQueue) . PHP_EOL;while (!$splPriorityQueue->isEmpty()) { var_dump($splPriorityQueue->extract());} ...

题目要求Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:postTweet(userId, tweetId): Compose a new tweet.getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.follow(followerId, followeeId): Follower follows a followee.unfollow(followerId, followeeId): Follower unfollows a followee.Example:Twitter twitter = new Twitter();// User 1 posts a new tweet (id = 5).twitter.postTweet(1, 5);// User 1’s news feed should return a list with 1 tweet id -> [5].twitter.getNewsFeed(1);// User 1 follows user 2.twitter.follow(1, 2);// User 2 posts a new tweet (id = 6).twitter.postTweet(2, 6);// User 1’s news feed should return a list with 2 tweet ids -> [6, 5].// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.twitter.getNewsFeed(1);// User 1 unfollows user 2.twitter.unfollow(1, 2);// User 1’s news feed should return a list with 1 tweet id -> [5],// since user 1 is no longer following user 2.twitter.getNewsFeed(1);设计一个迷你推特，要求能够支持以下几个方法：发布推特，关注用户，取关用户，查看最近的十条关注用户发送的推特。思路和代码这道题目本质上是考察是否能将数据结构的知识灵活的运用于现实生活中。从最直观的想法来看，我们会有一个用户实体，每个用户会记录自己关注的用户的id，以及记录自己发表的所有tweet。这里唯一的难点在于我们如何按照时间顺序获取tweet流。这么一想，这题其实就转换为如何将N个有序排列的数组汇合成一个有序的数组。这题等价于我们每次都会比较当前所有被关注者发布的最新未读tweet，选出结果后将其插入结果集。这里我们可以利用等价队列帮助我们更快的完成选择的过程。public class Twitter { public Twitter() { users = new HashMap<>(); } public static int timestamp = 0; private Map<Integer, User> users; /** Compose a new tweet. / public void postTweet(int userId, int tweetId) { if(!users.containsKey(userId)) { User user = new User(userId); users.put(userId, user); } User user = users.get(userId); user.tweet(tweetId); } /* Retrieve the 10 most recent tweet ids in the user’s news feed. * Each item in the news feed must be posted by users who the user followed or by the user herself. * Tweets must be ordered from most recent to least recent. * / public List<Integer> getNewsFeed(int userId) { List<Integer> result = new ArrayList<Integer>(); if(!users.containsKey(userId)) { return result; } User user = users.get(userId); PriorityQueue<Tweet> queue = new PriorityQueue<>(user.followed.size()); for(int followee : user.followed) { User tmp = users.get(followee); if(tmp != null && tmp.headTweet != null) { queue.offer(tmp.headTweet); } } while(!queue.isEmpty() && result.size() < 10) { Tweet t = queue.poll(); result.add(t.tweetId); if(t.next != null) { queue.offer(t.next); } } return result; } /* Follower follows a followee. If the operation is invalid, it should be a no-op. / public void follow(int followerId, int followeeId) { if(!users.containsKey(followerId)) { User user = new User(followerId); users.put(followerId, user); } if(!users.containsKey(followeeId)) { User user = new User(followeeId); users.put(followeeId, user); } User user = users.get(followerId); user.follow(followeeId); } /* Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ public void unfollow(int followerId, int followeeId) { if(!users.containsKey(followerId) || followerId == followeeId) { return; } User user = users.get(followerId); user.unfollow(followeeId); } public static class User{ int userId; Set<Integer> followed; Tweet headTweet; public User(int userId) { this.userId = userId; this.followed = new HashSet<>(); follow(userId); } public void follow(int userId) { followed.add(userId); } public void unfollow(int userId) { followed.remove(userId); } public void tweet(int tweetId) { Tweet tweet = new Tweet(tweetId); tweet.next = headTweet; headTweet = tweet; } } public static class Tweet implements Comparable<Tweet>{ int tweetId; Tweet next; int time; public Tweet(int tweetId) { this.tweetId = tweetId; this.time = timestamp++; } @Override public int compareTo(Tweet o) { return o.time - this.time; } }} ...

题目要求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(); }} ...