堆

数据结构	入队	出队
普通线性结构	O(1)	O(N)
顺序线性结构	O(N)	O(1)
堆	O(logn)	O(logn)

数组实现堆

public class MaxHeap<E extends Comparable<E>> {
  private Array<E> data;
  public MaxHeap(int capacity){
    data = new Array<>(capacity);
  }

  public int size(){
    return data.size();
  }
  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 2 * index + 1;
  }
  //返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
  private int rightChild(int index){
    return 2 * index + 2;
  }
}

Sift Up 上浮

public void add(E e) {
  // 添加到最后的位置
  data.addLast(e);
  siftUp(data.getSize()-1);
}

public void siftUp(int k) {
  while(k > 0 && data.get(parent(k))).compareTo(data.get(k)) < 0) {
    // data 在这里实现交换
    data.swap(k,parent(k));
    k = parent(k);
  }
}

Sift Down

public E findMax() {
  if(data.getSize() == 0) {
    throw new IllegalArumentException("Con not findMax");
  }
  return data.get(0);
}
public E getMax() {
  // 获取最大值
  E e = findMax();
  // 与最后一个元素交换位置
  data.swap(0,data.size() - 1);
  // 删除最后一个元素
  data.removeLast();
  // 从第一个元素开始下沉
  siftDown(0);
  return e;
}
// 下沉
private void siftDown(int k) {
  int size = data.getSize();
  // 左孩子索引比右孩子索引大的时候循环终止
  while(leftChild(k) < size) {
		// 保存要交换的索引
    int j = leftChild(k);
    if(j + 1 < size && data.get(j + 1).compateTo(data.get(j)) > 0) {
      j++;
    }
    // 如果当前节点比最大的节点都要大，那么跳出循环
    if(data.get(k).compateTo(data.get(j)) >= 0) {
       break;
    }
    // 下沉操作
    data.swap(k,j);
    // 节点索引值改变
    k = j;
  }
}

Replace

• 取出最大元素之后，放入一个新的元素
• 实现： 可以先extractMax,在add,两次O(logn)的操作
• 实现： 可以直接将堆顶替换之后进行siftDown,一次O(logn)的操作

public E replace(E e) {
  E ret = findMax();
  data.set(0,e);
  siftDown(0);
  return ret;
}

Heapify

• 将任意的数组整理成堆的形状
• 实现：从最后一个非叶子节点之前的元素进行siftdown操作。
• 找到最后一个非叶子节点，就是最后一个节点的父亲节点。

public MaxHeap(E[] arr) {
  data = new Array<>(arr);
  for(int i = parent(arr.length - 1); i >= 0; i--) {
    siftDown(i);
  }
}
// 在arry中构造
pullic Array(E[] arr) {
  data = (E[])new Object[arr.length];
  for(int i = 0; i < arr.length; i++) {
    data[i] = arr[i];
  }
}

优先队列PriorityQueue

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

在N个元素中选出前M大个元素？

class Solution {
	private class Freq  implements Comparable<Freq> {
		int e,freq;
		public Freq(int e,int freq) {
			this.e = e;
			this.freq = freq;
		}
		@Override
		public int compareTo(Freq another) {
			return this.freq - another.freq;
		}
	}
    public List<Integer> topKFrequent(int[] nums, int k) {
        
        Map<Integer> map = new TreeMap<>();
        for(int key: map) {
            if(map.containKey(value)) {
                map.put(key,map.get(key) + 1);
            } else {
                map.put(key,1);
            }
        }
        PriorityQueue<Freq> queue = new PriorityQueue<>();
		for(int key:map.keySet()) {
			if(queue.getSize() < k){
				queue.enqueue(new Freq(key,map.get(key));
			} else if(map.get(key) > queue.getFront().freq){
				queue.dequeue();
				queue.enqueue(new Freq(key,map.get(key)));
			}
		}
		LinkedList<Integer> res = new LinkedList<>();
		while(!queue.isEmpty())
		res.add(pq.dequeue().e);
		return res;
    }
}

比较器实现

// 使用匿名内部类简化代码
PriorityQueue<Freq> pq = new PriorityQueue<>(new Comparator<Freq>() {
    @Override
    public int compare(Freq a,Freq b) {
        return a.freq - b.freq;
    }
})；

// 变量补获
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Freq>() {
    @Override
    public int compare(Integer a,Integer b) {
    	// 可以获取全局变量中不可变得值
        return map.get(a) - map.get(b);
    }
})；
// lamdar
PriorityQueue<Integer> pq = new PriorityQueue<>(
    (a,b) -> map.get(a) - map.get(b)
)；