优先队列的实现

电玩女神 2021-09-23 22:34 346阅读 0赞

# 基于堆的优先队列 #

package MaxHeap;
    
    import Queue.Queue;
    
    public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { 
    
        private MaxHeap<E> maxHeap;
    
        public PriorityQueue() { 
            maxHeap = new MaxHeap<E>();
        }
    
        @Override
        public int getSize() { 
            return maxHeap.size();
        }
    
        @Override
        public boolean isEmpty() { 
            return maxHeap.isEmpty();
        }
    
        @Override
        public E getFront() { 
            return maxHeap.findMax();
        }
    
        @Override
        public void enqueue(E e) { 
            maxHeap.add(e);
        }
    
        @Override
        public E dequeue() { 
            return maxHeap.extractMax();
        }
    }

# 优先队列的经典问题 #

## 1、如何在1000000个元素中选出钱100名(在N个元素中选出前M个) ##

![在这里插入图片描述][20200215163428210.png]

## **LeetCode与之类似的问题：** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

package LeetCode.前k个高频元素347;/// 347. Top K Frequent Elements
    /// https://leetcode.com/problems/top-k-frequent-elements/description/
    
    import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    import java.util.TreeMap;
    
    public class Solution { 
    
        private class Freq implements Comparable<Freq>{ 
    
            public int e, freq;
    
            public Freq(int e, int freq){ 
                this.e = e;
                this.freq = freq;
            }
    
            public int compareTo(Freq another){ 
                if(this.freq < another.freq)
                    return -1;
                else if(this.freq > another.freq)
                    return 1;
                else
                    return 0;
            }
        }
    
        public List<Integer> topKFrequent(int[] nums, int k) { 
    
            TreeMap<Integer, Integer> map = new TreeMap<>();
            for(int num: nums){ 
                if(map.containsKey(num))
                    map.put(num, map.get(num) + 1);
                else
                    map.put(num, 1);
            }
    
            PriorityQueue<Freq> pq = new PriorityQueue<>();
            for(int key: map.keySet()){ 
                if(pq.size() < k)
                    pq.add(new Freq(key, map.get(key)));
                else if(map.get(key) > pq.peek().freq){ 
                    pq.remove();
                    pq.add(new Freq(key, map.get(key)));
                }
            }
    
            LinkedList<Integer> res = new LinkedList<>();
            while(!pq.isEmpty())
                res.add(pq.remove().e);
            return res;
        }
    
        private static void printList(List<Integer> nums){ 
            for(Integer num: nums)
                System.out.print(num + " ");
            System.out.println();
        }
    
        public static void main(String[] args) { 
    
            int[] nums = { 1, 1, 1, 2, 2, 3};
            int k = 2;
            printList((new Solution()).topKFrequent(nums, k));
        }
    }

[20200215163428210.png]: /images/20210923/589449af0474498dbf2c8b4b78c0c9f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/0d203e8ba5c1402893c4436f803332db.png