算法与数据结构系列之[优先队列]

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法与数据结构系列之[优先队列]，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1135字，纯文字阅读大概需要2分钟。

内容图文

前面我们介绍了队列这种数据结构，不过我们在前面所介绍的队列只是一种普通的队列，即元素先进先出，其实队列还可以分优先级，优先级高的元素先出，比如操作系统的调度，会将优先级高的任务先调度执行，这种队列就叫做优先队列。

那么优先队列底层该如何实现呢？

1.优先队列可以使用普通的线性结构，比如动态数组，入队时的时间复杂度为O(1),出队时需要遍历元素，找到优先级最大的元素出队，时间复杂度为O(n)。

2.使用顺序线性结构，入队时需要按优先级大小排序存储，所以时间复杂度为O(n)，出队时只需要按优先级大小出队即可，时间负责度为O(1)。

3.使用堆这种数据结构，其入队和出队的时间复杂度都为O(logn)。数据量大时，这种使用堆这种数据结构非常高效。

优先队列的java代码实现(这里用最大堆，jdk的优先队列是用最小堆实现的)：

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;  //用最大堆实现

    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize() {
        return maxHeap.getSize();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }
}

内容总结

以上是互联网集市为您收集整理的算法与数据结构系列之[优先队列]全部内容，希望文章能够帮你解决算法与数据结构系列之[优先队列]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---