【数据结构】优先级队列（堆）1.优先级队列2.优先级队列的模拟实现3.常用接口介绍4.Top-K问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class TestHeap {
    public int[] elem;
    public int usedSize;//有效的数据个数
    public static final int DEFAULT_SIZE = 10;
    public TestHeap() {
        elem = new int[DEFAULT_SIZE];
    }
    public void initElem(int[] array){
        for(int i = 0;i < elem.length;i++){
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void createHeap(){
        for(int parent = ((usedSize-1)-1)/2;parent >= 0;parent--){
            shiftdown(parent,usedSize);
        }
    }
    //parent:表示每棵子树的节点
    //len表示没课字数调整的结束位置，不能大于len
    public void shiftdown(int parent,int len){
        int  child= parent * 2 +1;
        //孩子的下标必须小于有效长度，保证有左孩子
        while(child < len){
            //child+1 < len保证有右孩子
            if(child+1 < len && elem[child] < elem[child +1]){
                child ++;
            }
            if(elem[child]>elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 *parent + 1;
            }else{
                break;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void offer(int val){
        //如果满了就扩容
        if(isFull()){
            elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        elem[usedSize] = val;
        usedSize++;
        //调整为大根堆
        shiftup(usedSize-1);
    }
    public void shiftup(int child){
        int parent = (child-1)/2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child -1)/2;
            }else{
                break;
            }
        }
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int pop(){
        if(isEmpty()){
            throw new isEmptyExpection("堆空异常!");
        }
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        shiftdown(0,usedSize);
        return tmp;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }

1
2
3
4
5
6
7
8
9
public int[] smalllestK(int[] arr,int k){
        Arrays.sort(arr);
        int[] tmp = new int[k];
        for(int i = 0; i< k;i++){
            tmp[i] = arr[i];
        }
        return tmp;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] smallestK1(int[] arr,int k){
        //1.建一个堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        //2.取出数组中的每个元素，存放到小根堆中
        for(int i = 0;i < k;i++){
            minHeap.offer(arr[i]);
        }
        //3.弹出k个元素，存放到数组当中。
        int[] tmp = new int[k];
        for(int i = 0;i < k;i++){
            tmp[i] = arr[i];
        }
        return tmp;
    }