数据结构:堆和优先级队列

优先级队列(堆):按照优先级的大小动态出队(动态指的是元素个数动态变化,而非固定)

普通队列:FIFO按照元素的入队顺序出队,先入先出 

 操作系统的任务调度(优先级队列):

   系统的任务优先级要比普通的应用要高

   CPU内存等资源有限的,当资源不够用,优先让优先级高的应用获取资源 

   1.是一颗完全二叉树,基于数组存储

2.关于节点值

 a. 堆中根节点值>=子树中的节点值(最大堆)

 b.堆中根节点值<= 子树中节点的值(最小堆)

JDK中的PriorityQueue默认是基于最小堆实现的

 3.堆是基于数组存储的,节点之间的关系通过数组下标来表示,从0开始编号,数组下标也是

假设节点编号为i,且存在父子节点:

 1.父节点的编号:parent = (i - 1) / 2

 2.左子树的编号:left = 2 * i + 1

 3.右子树的编号:right = 2 * i +2 

public class MaxHeap {
    //存储元素
    private List elmentData;
    //元素个数
    int size;

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int size) {
        elmentData = new ArrayList<>(size);
    }
    //节点个数
    public int getSize(){
        return size;
    }
    //判断是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    //找到结点k对应的父节点的索引
    private int parent(int k){
       return (k - 1) >> 2;
    }
    //找到结点k对应的左子树的索引
    private int leftChild(int k){
        return (k << 2) + 1;
    }
    //找到结点k对应的右子树的索引
    private int rightChild(int k){
        return (k << 2) + 2;
    }

    @Override
    public String toString() {
        return elmentData.toString();
    }
}

   向堆添加元素sitfUp(上浮):

 新增一个元素52,此时堆仍然是一个完全二叉树,但此时不是最大堆了

 因此需要进行元素的上浮操作,让新元素到合适的位置

 public void add(int val){
        elmentData.add(val);
        size++;
        //上浮操作
        siftUp(size - 1);
    }

 private void siftUp(int k) {
        while (k > 0 && elmentData.get(k) > elmentData.get(parent(k))){
             swap(k,parent(k));
             k = parent(k);
        }
    }

 private void swap(int k, int parent) {
        int child = elmentData.get(k);
        int parentVal =  elmentData.get(parent);

        elmentData.set(k,parentVal);
        elmentData.set(parent,child);
    }

 取出堆中的最大值(下浮操作):

//取出当前堆的最大值
    public int extractMax(){
        if(size == 0){
            throw new NoSuchElementException("空元素");
        }
        //取出最大值
        int max = elmentData.get(0);
        //将数组末尾元素顶到树根
        elmentData.set(0,size - 1);
        //将数组末尾元素删除
        elmentData.remove(size - 1);
        size--;
        //下沉操作开始
        siftDown(0);
        return max;
    }
 //下沉操作
private void siftDown(int k) {
        //还存在子树
        while (leftChild(k) < size){
            int left = leftChild(k);
            if(left + 1 < size && elmentData.get(left+1) > elmentData.get(left) ){
                //右子树的值比左子树大
                left++;
            }
            if(elmentData.get(k) >= elmentData.get(left)){
                // 当前元素 >= 左右子树最大值，下沉结束，元素k落在了最终位置
                break;
            }else {
                swap(k,left);
                k = left;
            }
        }
    }

heapify-堆化  

//将任意数组调整为最大堆
    public MaxHeap(int [] arr){
       elmentData = new ArrayList<>();
       //1.将所有元素复制到data数组中
        for (int i: arr) {
            elmentData.add(i);
            size++;
        }
        //2.从最后一个非叶子节点开始进行siftDown操作
        for (int i = parent(size - 1); i >= 0 ; i--) {
            siftDown(i);
        }
    }

Topk问题 

Tok问题都可以使用优先级队列解决:

   取前k个最大元素用最小堆解决

   取前k个最小元素用最大堆解决 

取出前4个元素构造一个大小为4的堆

1.若此时队列的元素个数 < k,直接添加到队列中

2.若此时元素个数 = k

 a.新扫描到的元素val >= 堆顶元素,一定大于堆中的所有元素,则val直接跳过

 b.若此时val < 堆顶元素,堆顶元素出队,将新元素添加到队列中

 c.重复上述过程,直到集合扫描完毕,队列中就保存了前k个最小值

随着堆顶元素不断交换,堆顶元素会不断变小,队列扫描结束,就存放了最小的k个数 

public class Num17_14 {
    public int[] smallestK(int[] arr, int k) {
         int[] ret = new int[k];
          if(arr.length == 0 || k == 0){
              return ret;
          }
         //默认最小堆,修改为最大堆
        Queue queue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            if(queue.size() < k){
               queue.offer(arr[i]);
            }else {
                int max = queue.peek();
                if(arr[i] < max){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
           int i = 0;
           while (!queue.isEmpty()){
              ret[i++] =  queue.poll();
           }
           return ret;
    }
}

自定义类型在堆中存储 

class Freq implements Comparable{

    int key;
    int val;

    public Freq(int key, int val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public int compareTo(Freq o) {
        return this.val - o.val;
    }
}
public class Num347 {

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        Map map = new HashMap();
        //遍历数组存入到map集合中
        for(int i: nums){
            if(map.containsKey(i)){
                int times = map.get(i);
                map.put(i,times+1);
            }else {
                map.put(i,1);
            }
        }

        Queue queue = new PriorityQueue();
        for(Map.Entry entry : map.entrySet()){
            if(queue.size() < k){
                 queue.offer(new Freq(entry.getKey(),entry.getValue()));
              }else {
                 Freq freq = queue.peek();
                 if(entry.getValue() > freq.val){
                     queue.poll();
                     queue.offer(new Freq(entry.getKey(),entry.getValue()));
                 }
              }
        }
        int j = 0;
        while (!queue.isEmpty()){
            ret[j++] = queue.poll().key;
        }
        return ret;
    }
}