PriorityQueue

Heap

二叉堆（Binary Heap）是一棵完全二叉树

public class MaxHeap> {

    private Array data;

    public MaxHeap(int capacity){
        data = new Array(capacity);
    }

    public MaxHeap(){
        data = new Array();
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }
}

向堆中添加元素和Sift up

    // 向堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k){

        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) 

取出堆中的最大元素和Sift Down

1. Sift Down
2. 用最小元素替换堆顶元素，然后删除之前的最小元素位置
3. 最小元素和子树中最大元素，比较，交换位置
4. 下沉完毕

   // 看堆中的最大元素
    public E findMax(){
        if(data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0);
    }

    // 取出堆中最大元素
    public E extractMax(){

        E ret = findMax();

        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    private void siftDown(int k){

        while(leftChild(k)  0 )
            // j + 1 = 0 )
                break;

            data.swap(k, j);
            k = j;
        }
    }

Heapify和Replace

1. Heapify
2. 从最后一个非叶子节点开始计算（如何获得节点？答：拿到最后一个节点，然后拿到他的父亲节点）
3. 然后不断下沉

    public MaxHeap(E[] arr){
        data = new Array(arr);
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --) // i是倒数第一个非叶子节点
            siftDown(i);
    }

Test

import java.util.Random;

public class Main {

    private static double testHeap(Integer[] testData, boolean isHeapify){

        long startTime = System.nanoTime();

        MaxHeap maxHeap;
        if(isHeapify)
            maxHeap = new MaxHeap(testData);
        else{
            maxHeap = new MaxHeap();
            for(int num: testData)
                maxHeap.add(num);
        }

        int[] arr = new int[testData.length];
        for(int i = 0 ; i 

基于堆的优先队列

public class PriorityQueue> implements Queue {

    private MaxHeap maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap();
    }

    @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();
    }
}

在 100 0000个元素中选出前100名？（Leetcode347前K个高频元素）

 private class Freq implements Comparable{

        public int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another){
            if(this.freq  another.freq)
                return -1;
            else
                return 0;
        }
    }

    public List topKFrequent(int[] nums, int k) {

        TreeMap map = new TreeMap();
        for(int num: nums){
            if(map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }

        PriorityQueue pq = new PriorityQueue();
        for(int key: map.keySet()){
            if(pq.getSize()  pq.getFront().freq){
                pq.dequeue();
                pq.enqueue(new Freq(key, map.get(key)));
            }
        }

        LinkedList res = new LinkedList();
        while(!pq.isEmpty())
            res.add(pq.dequeue().e);
        return res;
    }

    private static void printList(List 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));
    }
}

Java中的PriorityQueue

Java的Priority是最小堆

/// 347. Top K Frequent Elements
/// https://leetcode.com/problems/top-k-frequent-elements/description/

import java.util.*;

public class Solution2 {

    private class Freq{

        public int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }
    }

    private class FreqComparator implements Comparator{

        @Override
        public int compare(Freq a, Freq b){
            return a.freq - b.freq;
        }
    }

    public List topKFrequent(int[] nums, int k) {

        TreeMap map = new TreeMap();
        for(int num: nums){
            if(map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }

        PriorityQueue pq = new PriorityQueue(new FreqComparator());
        for(int key: map.keySet()){
            if(pq.size()  pq.peek().freq){
                pq.remove();
                pq.add(new Freq(key, map.get(key)));
            }
        }

        LinkedList res = new LinkedList();
        while(!pq.isEmpty())
            res.add(pq.remove().e);
        return res;
    }

    private static void printList(List 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));
    }
}

优化

/// 347. Top K Frequent Elements
/// https://leetcode.com/problems/top-k-frequent-elements/description/

import java.util.*;

public class Solution2 {

    private class Freq{

        public int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }
    }

    public List topKFrequent(int[] nums, int k) {

        TreeMap map = new TreeMap();
        for(int num: nums){
            if(map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
        }
        // 将只使用一次的类声明写成一个匿名类（变量捕获，拿到所有的不可改变的变量）
        // 优点：可以方便的使用匿名类改变类型
        // 只获取元素Integer，然后根据元素获取频率
        PriorityQueue pq = new PriorityQueue(new Comparator(){
                @Override
                public int compare(Integer a,Integer b){
                    return map.get(a) - map.get(b);
            }
        });
        // lamba表达式
//        PriorityQueue pq = new PriorityQueue(
//                (a,b) -> map.get(a) - map.get(b);
//        );
        for(int key: map.keySet()){
            if(pq.size()  map.get(pq.peek())){
                pq.remove();
                pq.add(key);
            }
        }

        LinkedList res = new LinkedList();
        while(!pq.isEmpty())
            res.add(pq.remove());
        return res;
    }

    private static void printList(List 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));
    }
}

拓展