Loading... **以下代码基于最小堆实现的最小优先队列** > 二叉堆实现参见 --> [二叉堆、堆排序](/index.php/archives/44/) ### 自定义实现优先队列 ```java /** * @ClassName 最小优先队列 * @Description 基于最小堆堆实现的优先队列 * @Author Deng PeiLin * @Date 2022/1/13 15:47 **/ public class 优先队列 { private int[] arr; private int size; public 优先队列 () { this.arr = new int[1]; } /** * 入队 */ public 优先队列 add(int data){ if (size >= arr.length) { resize(); } arr[size ++] = data; upAdjust(); return this; } /** * 出队 */ public int out(){ if (size <= 0){ throw new RuntimeException("队列中无数据"); } int firstData = arr[0]; arr[0] = arr[--size]; downAdjust(); return firstData; } /** * 上浮调整 */ private void upAdjust() { int childIndex = size - 1; int parentIndex = (childIndex - 1) / 2; // temp 用于保存插入的叶子节点值, 用于最后的赋值 int temp = arr[childIndex]; while (childIndex > 0 && temp < arr[parentIndex]) { // 无需真正交换, 单项赋值即可 arr[childIndex] = arr[parentIndex]; childIndex = parentIndex; parentIndex = (parentIndex - 1) / 2; } arr[childIndex] = temp; } /** * 下沉调整 */ private void downAdjust() { int parentIndex = 0; // temp 用于保存插入的叶子节点值, 用于最后的赋值 int temp = arr[parentIndex]; int childIndex = parentIndex * 2 + 1; while (childIndex < size) { // 如果有右节点, 且右节点小于左节点的值, 则定位到右节点 if (childIndex + 1 < size && arr[childIndex + 1] < arr[childIndex]) { childIndex++; } // 如果父节点小于子节点的值则跳出, 不需要调整 if (temp < arr[childIndex]) { break; } arr[parentIndex] = arr[childIndex]; parentIndex = childIndex; childIndex = childIndex * 2 + 1; } arr[parentIndex] = temp; } private void resize() { arr = Arrays.copyOf(arr, size * 2); } public int getSize() { return size; } @Override public String toString() { return Arrays.toString(Arrays.copyOfRange(arr, 0, size)); } } ``` ### 测试代码 ```java public static void main(String[] args){ 优先队列 queue = new 优先队列(); queue.add(5).add(8).add(9).add(11).add(999).add(1); System.out.println("队列数据: " + queue); int out = queue.out(); System.out.println("出队元素: " + out); System.out.println("队列数据: " + queue); int out2 = queue.out(); System.out.println("出队元素: " + out2); System.out.println("队列数据: " + queue); } ``` 测试结果 >>> **以最小堆实现的最小优先队列, 队列头部皆为最小数据** ```java 队列数据: [1, 8, 5, 11, 999, 9] 出队元素: 1 队列数据: [5, 8, 9, 11, 999] 出队元素: 5 队列数据: [8, 11, 9, 999] Process finished with exit code 0 ``` 最后修改:2022 年 05 月 23 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请点个赞吧~