Java使用小堆模拟实现简单的优先队列

爱被打了一巴掌 2023-09-28 23:21 92阅读 0赞

> **今天简单的使用堆模拟实现一下优先队列。**

**关于优先队列和堆的相关知识可以去：**  
[优先队列PriorityQueue中的方法和使用细节][PriorityQueue]  
[堆 超详细的带图总结][Link 1]

**代码实现：**

package PriorityQueue;
    
    //小堆模拟实现优先队列
    // 堆的定义：要求每个位置都比它的两个孩子（如果存在的话）要小
    
    public class MyPriorityQueue {
        
        // 元素类型使用 long 类型
        // 暂时不考虑扩容的情况
        private final long[] array = new long[1000];
        private int size;       // 元素的个数
    
        public MyPriorityQueue() {
        
            //空的优先级队列
            size = 0;
        }
    
        // 查看优先级队列中最小值
        // O(1)
        public long peek() {
        
            if (size <= 0) {
        
                throw new RuntimeException("该堆为空！！！");
            }
            return array[0];
        }
    
        // 把 e 添加到堆中（优先级队列）
        // 同时维护好最小堆的性质
        // 最坏情况：从叶子 -> 根 时间复杂度即堆的深度
        // O(log(n))
        public void offer(long e) {
        
            array[size++] = e;
    
            int index = size - 1;
            // index == 0 说明是根，不需要调整了
            while (index > 0) {
        
                // 求双亲的下标
                int pIdx = (index - 1) / 2;
                // 比较要调整的位置和双亲的大小
                if (array[pIdx] <= array[index]) {
        
                    break;
                }
                swap(array, pIdx, index);
                index = pIdx;
            }
        }
    
        // 删除堆顶元素
        // 同时维护好最小堆的性质
        // O(log(n))
        public long poll() {
        
            if (size <= 0) {
        
                throw new RuntimeException("该堆为空！！！");
            }
            long e = array[0];
            size--;
            array[0] = array[size];
            adjustDown(0);
            return e;
        }
    
        public void adjustDown(int index) {
        
            //2 * index + 1 < size 说明不是叶子节点
            while (2 * index + 1 < size) {
        
                int minIdx = 2 * index + 1;
                int rightIdx = minIdx + 1;
                if (rightIdx < size && array[minIdx] > array[rightIdx]) {
        
                    minIdx = rightIdx;
                }
                if (array[minIdx] >= array[index]) {
        
                    return;
                }
                swap(array, minIdx, index);
                index = minIdx;
            }
        }
    
        public void swap(long[] array, int i, int j) {
        
            long tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    
        //验证
        public static void main(String[] args) {
        
            MyPriorityQueue q = new MyPriorityQueue();
    
            q.offer(3);
            q.offer(9);
            q.offer(7);
            q.offer(2);
            q.offer(6);
            q.offer(8);
            q.offer(5);
            q.offer(4);
            q.offer(3);
    
            System.out.println(q.poll());
            q.offer(1);
            System.out.println(q.poll());
            q.offer(1);
            q.offer(0);
            System.out.println(q.poll());
            System.out.println(q.poll());
        }
    }

[PriorityQueue]: https://blog.csdn.net/qq_53130059/article/details/126750351?spm=1001.2014.3001.5501
[Link 1]: https://blog.csdn.net/qq_53130059/article/details/127630619?spm=1001.2014.3001.5501