## 集合數組實現堆 ~~~ /** * 實現堆 * * @Author: mango * @Date: 2022/4/30 2:24 下午 */ public class Heap<T extends Comparable> { // 集合，存數據的 private List<T> data; // 堆大小 private int size; // 比較器 private Comparator<T> comparator; public Heap() { this.data = new ArrayList<>(); this.size = 0; this.comparator = null; } public Heap(Comparator<T> comparator) { this.data = new ArrayList<>(); this.size = 0; this.comparator = comparator; } /** * 判斷棧是否為空 * * @return */ public boolean isEmpty() { return this.size == 0; } private void swap(int i, int j) { T temp = this.data.get(i); this.data.set(i, this.data.get(j)); this.data.set(j, temp); } /** * 加入元素到棧 * * @param t */ public void insert(T t) { this.data.add(t); int index = this.size; // 向上堆化 while (index>0 && this.compare(index,(index-1)/2)) { swap(index, (index - 1) / 2); index = (index - 1) / 2; } this.size++; } private boolean compare(int i,int j){ if(null == comparator){ return this.data.get(i).compareTo(this.data.get(j)) < 0 ? true : false; }else{ return comparator.compare(this.data.get(i),this.data.get(j)) < 0 ? true : false; } } /** * 彈出棧頂元素 * * @return */ public T pop() { // 取棧頂0位置 T result = this.data.get(0); swap(0, this.size-1); this.data.set(this.size-1,null); this.size--; heapfiy(0, this.size); return result; } /** * 向下堆化 * @param index 起始下標 * @param size 堆大小 */ public void heapfiy(int index, int size) { int left = index * 2 + 1; while (left < size) { int the = left + 1 < size && this.compare(left+1,left) ? left + 1 : left; the = this.compare(the,index) ? the : index; if (the == index) { break; } swap(the, index); index = the; left = index * 2 + 1; } } } ~~~ ``` public static void main(String[] args) { Heap<Integer> heap = new Heap<>(((o1, o2) -> o2 - o1)); heap.insert(1); heap.insert(6); heap.insert(5); heap.insert(9); heap.insert(2); heap.insert(33); while (!heap.isEmpty()){ System.out.println(heap.pop()); } } ```