java data structures

  • PriorityQueue

heap

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package design;
import java.util.ArrayList;
import java.util.List;
/**
 * Created by tao on 10/18/17.
 */
public class MyPriorityQueue {
    List<Integer>nums = null;
    public MyPriorityQueue(){
        nums=new ArrayList<>();
        nums.add(0);
    }
    public int getLeft(int ind){
        return ind*2;
    }
    public int getRight(int ind){
        return ind*2+1;
    }
    public int getParent(int ind){
        return ind/2;
    }
    public void heapify(int ind){
        int size = nums.size();
        if(size<=2)
            return;
        int l = getLeft(ind);
        int r = getRight(ind);
        int minInd = ind;
        if(l<size && nums.get(l)<nums.get(minInd))
            minInd = l;
        if(r<size && nums.get(r)<nums.get(minInd))
            minInd = r;
        if(minInd!=ind){
            int tmp = nums.get(minInd);
            nums.set(minInd,nums.get(ind));
            nums.set(ind,tmp);
            heapify(minInd);
        }
    }
    public void buildHeap(){
        int n = (nums.size()-1)/2;
        for(int i=n;i>=1;--i)
            heapify(i);
    }
    public int peek(){
        if(isEmpty())
            throw new IndexOutOfBoundsException();
        buildHeap();
        return nums.get(1);
    }
    public void offer(int ele){
        nums.add(ele);
    }
    public int pop(){
        if(isEmpty())
            throw new IndexOutOfBoundsException();
        buildHeap();
        int val = nums.get(1);
        int size = nums.size();
        nums.set(1,nums.get(size-1));
        nums.remove(size-1);
        return val;
    }
    public boolean isEmpty(){
        return nums.size()<=1;
    }
}