首页 > itarticle > priorityqueue in java

priorityqueue in java

admin 11月 12, 2020 0

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering (Default), or by a Comparator provided at queue construction time, depending on which constructor is used. If multiple elements are tied for least value, the head is one of those elements – ties are broken arbitrarily.
The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

Fields

//initialize default capacity 
private static final int DEFAULT_INITIAL_CAPACITY = 11;  
//heap
private transient Object[] queue;  
//current capacity  
private int size = 0;  
//comparator
private final Comparator<? super E> comparator;  
//modify times
private transient int modCount = 0;

Functions

//add
public boolean add(E e)   
//get the peek element(not delete)
public E peek()  
//poll the top element(delete)  
public E poll()  
//delete
public boolean remove(Object o)  
//if contains certain element
public boolean contains(Object o)  
//clear 
public void clear()  
//grow capacity
private void grow(int minCapacity)  
//index of
private int indexOf(Object o)

Constructors

PriorityQueue()
Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue(Collection<? extends E> c)
Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(int initialCapacity)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue<? extends E> c)
Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet<? extends E> c)
Creates a PriorityQueue containing the elements in the specified sorted set.

How to use priority queue

Queue<Integer> qi = new PriorityQueue<Integer>();
qi.add(5);
qi.add(2);
qi.add(1);
qi.add(10);
qi.add(3);
while (!qi.isEmpty()) {
	System.out.print(qi.poll() + ",");
}
System.out.println();

// self-define comparator, define the compare order
Comparator<Integer> cmp = new Comparator<Integer>() { 
	public int compare(Integer e1, Integer e2) {
		return e2 - e1;
	}
};
Queue<Integer> q2 = new PriorityQueue<Integer>(5, cmp);
q2.add(2);
q2.add(8);
q2.add(9);
q2.add(1);
while (!q2.isEmpty()) {
	System.out.print(q2.poll() + ",");
}

Example

Top K Frequent Elements (Leetcode347)

We use a map to get each frequency of element, and use a priority queue to poll the top k
In order to sort the map data according to values, use priority queue

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            for (int i = 0; i < k; i++) {
                ans.add(-1);
            }
            return ans;
        }
        // element => frequency
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        while (!pq.isEmpty()) {
            ans.add(pq.poll().getKey());
        }
        return ans;
    }
}