搞得简单一点。主要是heapInsert(往堆里面插入数据),heapify(调整堆)这两个函数。
/** * @Author lyuWalle * @Date 2020/9/16 11:05 * @Version 1.0 * 简单自定义优先级队列,采用ArrayList实现。 * 主要实现: * add(Integer i) * peek(); * poll(); * size(); * */ public class MyPriorityQueue { private int cap; private List<Integer> list; public MyPriorityQueue(){ this.cap = 10; list = new ArrayList<>(10); } public MyPriorityQueue(int capacity){ this.cap = capacity; list = new ArrayList<>(this.cap); } public void add(int num){ //将一个新的值插入到大根堆里面 list.add(num); heapInsert(list, list.size() - 1); } private void heapInsert(List<Integer> list, int i) { while(list.get(i) > list.get((i - 1)/2)){ Collections.swap(list, i, (i - 1)/2); i = (i - 1)/2; } } public void heapify(List<Integer> list, int top, int end){ int left = top * 2 + 1; while(left < end){ int largest = left + 1 <= end && list.get(left + 1) > list.get(left) ? left + 1 : left; if(list.get(largest) > list.get(top)){ Collections.swap(list, top, largest); }else{ break; //说明不需要调整堆 } top = largest; left = 2 * top + 1; } } public int peek(){ if(list.size()>0){ return list.get(0); }else{ return -1; //假设队列为空时返回-1 } } public int poll(){ if(list.size()>0){ int top = list.get(0); list.remove(0); heapify(list, 0, list.size() - 1); return top; }else{ return -1; } } public int size(){ return list.size(); } //for test public static void main(String[] args) { MyPriorityQueue mpq = new MyPriorityQueue(); mpq.add(1); mpq.add(2); mpq.add(3); mpq.add(4); System.out.println(mpq.peek()); mpq.poll(); System.out.println(mpq.peek()); System.out.println(mpq.size()); mpq.add(5); System.out.println(mpq.poll()); System.out.println(mpq.peek()); } }