精华内容
下载资源
问答
  • 堆实现优先级队列 Java实现

    千次阅读 2016-03-19 00:14:47
    优先级队列分为最大优先级队列和最小优先级队列。本文介绍基于大根堆实现最大优先级队列。关于堆的介绍见另一篇博文: 堆这种数据结构 Java实现 最小优先级队列的实现可以在本文最后给出的github地址里找到。

    优先级队列分为最大优先级队列和最小优先级队列。本文介绍基于大根堆实现最大优先级队列。关于堆的介绍见另一篇博文:
    堆这种数据结构 Java实现
    最小优先级队列的实现可以在本文最后给出的github地址里找到。
    最大优先级队列包含四个操作:
    heapMaximum()返回队列中最大的元素;
    heapExtractMax()返回队列中最大的元素并从队列中删除此元素;
    heapIncreaseKey(int i, T key)增加队列中下标为i的元素的值为key;
    maxHeapInsert(T key)向队列中插入元素key。
    接下来分别介绍如何实现这四个操作。
    首先给出我的最大优先级队列实现类中的域及构造函数:

    public class MaxPriorityQueue<T extends Comparable<T>> {
        private T[] heap;
        private int heapLength;
        // 用于提供堆的操作
        private MaxHeap<T> maxHeap = new MaxHeap<>();
        public MaxPriorityQueue(T[] a, int heapLength) {
            super();
            maxHeap.buildHeap(a, heapLength);
            this.heap = a;
            this.heapLength = heapLength;
        }
    }

    (1)heapMaximum()
    返回队列中的最大元素是很简单的,因为最大优先队列是基于大根堆实现的,所以只需要返回数组的第一个元素即可。
    Java代码如下:

        public T heapMaximum() {
            return this.heap[0];
        }

    (2)heapExtractMax()
    不仅需要返回队列中最大的元素,还需要删除该元素,要做到这一点,首先保存数组的第一个元素,然后把数组的最后一个元素放到数组的第一个位置,堆的长度减1,对堆的第一个元素调用大根堆的heapify方法,使第一个元素满足大根堆的性质。
    Java代码如下:

        public T heapExtractMax() {
            if (this.heapLength < 1) {
                return null;
            }
            T max = heap[0];
            heap[0] = heap[heapLength - 1];
            heapLength--;
            maxHeap.heapify(this.heap, 0, heapLength);
            return max;
        }

    (3)heapIncreaseKey(int i, T key)
    把数组中下标为i的元素的值设为key,key必须大于等于该处原来的值,该结点的值发生变化后可能破坏大根堆的性质,所以需要上移该处的值,保持大根堆性质。
    Java代码如下:

        public void heapIncreaseKey(int i, T key) {
            if (key.compareTo(this.heap[i]) < 0) {
                try {
                    throw new Exception("the key is less than heap[i]");
                } catch (Exception e) {
                    e.printStackTrace();
                    return;
                }
            }
            this.heap[i] = key;
            /**
             * 向上移动heap[i]的位置;
             * 移动的条件是heap[i]不是根节点,并且heap[i]比双亲结点大
             */
            while(i > 0 && heap[i].compareTo(this.heap[maxHeap.parent(i)]) > 0){
                T temp = this.heap[i];
                this.heap[i] = this.heap[maxHeap.parent(i)];
                this.heap[maxHeap.parent(i)] = temp;
                i = maxHeap.parent(i);
            }
        }

    (4)maxHeapInsert(T key)
    向队列中插入元素key,首先,堆的长度增加1,然后把key放在堆的最后,对这个元素调用heapIncreaseKey(int i, T key)方法,使之满足堆的性质即可。
    Java代码如下:

        public void maxHeapInsert(T key) {
            this.heapLength++;
            // 如果保存堆的数组已经被填满
            if (this.heapLength == this.heap.length) {
                // 新建一个更大的数组,用于保存旧数组中的元素
                @SuppressWarnings("unchecked")
                T[] temp = (T[]) Array.newInstance(this.heap.getClass().getComponentType(),
                        2 * this.heapLength);
                // 把旧数组中的元素复制进新数组中
                for(int i = 1; i < this.heapLength; i++){
                    temp[i] = this.heap[i];
                }
                this.heap = temp;
    
            }
            this.heap[heapLength] = key;
            this.heapIncreaseKey(heapLength, key);
        }

    最大优先级队列和最小优先级队列的完整可以在下面的github地址处找到:
    https://github.com/l294265421/datastructure-common

    展开全文
  • 优先级队列实现

    2021-04-16 15:48:15
    在Java中,普通队列是由双向链表来实现的,如果优先级队列也使用双向链表,那么通过遍历找优先级最高的节点需要O(n)的时间复杂度,但如果使用二叉,那么入队和出队的时间复杂度都可以降到O(logn)。 接口 ...

    优先级队列(Priority Queue)

    优先级队列本身也是一个队列,只不过常规的队列是先进先出,而优先级队列可以插队,即让队列中优先级最高的元素先出队。在Java中,普通队列是由双向链表来实现的,如果优先级队列也使用双向链表,那么通过遍历找优先级最高的节点需要O(n)的时间复杂度,但如果使用二叉堆,那么入队和出队的时间复杂度都可以降到O(logn)。
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    接口

    方法 功能
    int size() 获取队列大小
    void isEmpty() 是否为空
    void clear() 清空队列
    void offer() 进队
    E poll() 出队
    E peek() 获取队顶元素

    具体实现

    我们可以通过一个二叉堆来实现优先级队列(有关堆见:堆的概念与二叉堆的实现详细图解)。

    在这里插入图片描述
    代码:

    public class PriorityQueue<E> {
        private BinaryHeap<E> heap;
    
        public PriorityQueue(){
            this(null);
        }
    
        //允许传入优先级比较方法
        public PriorityQueue(Comparator<E> comparator){
            heap=new BinaryHeap<>(comparator);
        }
    
        public int size(){
            return heap.size();
        }
    
        public boolean isEmpty(){
            return heap.isEmpty();
        }
    
        public void clear(){
            heap.clear();
        }
    
        /**
         * 入队
         */
        public void offer(E element) {
            heap.add(element);
        }
    
        public E poll() {
            return heap.remove();
        }
    
        public E peek() {
            return heap.get();
        }
    }
    
    展开全文
  • 优先级队列队列遵循先进先出原则,无...优先级队列则不同,每个数都有优先级,我们假设最大的数具有高优先级,则在一个有一数据的优先级队列中,每次出数据出优先级最高的那个数据,也就是每次出数据最大的那个数。

    优先级队列

    队列遵循先进先出原则,无优先级。
    优先级队列则不同,每个数都有优先级,我们假设最大的数具有高优先级,则在一个有一堆数据的优先级队列中,每次出数据出优先级最高的那个数据,也就是每次出数据最大的那个数。
    例:
    优先级队列

    优先级队列的实现

    优先级队列可以通过一个有序数组实现,但是时间复杂度过高,每次有新的数据入队列就需要重新排序,比较慢。
    用堆实现可以将时间复杂度优化到每次入数据在时间复杂度上只需要log2n,可以说是一个非常快的算法了,而且实现起来也不是很复杂,只需要把堆的结构稍加修改就能当作优先级队列使用。
    如果需要大的数据优先出队列则建大堆,小数据优先出队列就建小堆,每次有新的数据入队就根据堆的特性向上调整,有数据出队列就向下调整。
    优先级队列

    入一个100进入队列
    优先级队列

    在没有入100之前,将87出队列
    优先级队列

    看到这,大家可能大概能知道优先级队列的实现了,无非是将堆换个名字来改叫优先级队列,其思想就是堆的思想,下面通过代码实现

    实现代码(戳此下载)

    代码从增删查改四个常规的功能实现

    运行结果

    运行结果

    代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <windows.h>
    #include <assert.h>
    
    #define _SIZE 5
    
    typedef int PQueueDataType;
    
    typedef struct PriorityQueue
    {
        int* _a;
        int _size;
        int _capacity;
    }PQueue;
    
    PQueue* PQueueInit();//初始化优先级队列
    void PQueuePush(PQueue* q, PQueueDataType data);//入队
    void PQueueAdjustUp(PQueue* q, int child);//数据向上调整
    void PQueueAdjustDown(PQueue* q, int parent);//数据向下调整
    void PQueuePop(PQueue* q);//出队列
    PQueueDataType PQueueTop(PQueue* q);//获取队列头数据
    void PQueueDestroy(PQueue* q);//队列销毁
    
    void TestPQueue();//测试用例
    
    PQueue* PQueueInit()
    {
        PQueue* q = (PQueue*)malloc(sizeof(PQueue));
        q->_capacity = _SIZE;
        q->_size = 0;
        q->_a = (PQueueDataType*)malloc(sizeof(PQueueDataType) * q->_capacity);
        return q;
    }
    
    void PQueueCheckCapacity(PQueue* q)
    {
        assert(q);
        if (q->_size == q->_capacity)
        {
            q->_capacity *= 2;
            q->_a = realloc(q->_a, sizeof(PQueueDataType) * q->_capacity);
            assert(q->_a);
        }
    }
    
    void PQueueSwap(PQueueDataType* data1, PQueueDataType* data2)
    {
        assert(data1 && data2);
        *(data1) ^= *(data2);
        *(data2) ^= *(data1);
        *(data1) ^= *(data2);
    }
    
    void PQueueAdjustUp(PQueue* q, int child)
    {
        assert(q);
        PQueueDataType parent = (child - 1) / 2;
        while (child)
        {
            if (*(q->_a + parent) < *(q->_a + child))
            {
                PQueueSwap(q->_a + parent, q->_a + child);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }
    }
    
    void PQueueAdjustDown(PQueue* q, int parent)
    {
        assert(q);
        int child = parent * 2 + 1;
        while (child < q->_size)
        {
            if (child + 1 < q->_size)
            {
                if (*(q->_a + child) < *(q->_a + child + 1))
                {
                    child += 1;
                }
            }
            if (*(q->_a + parent) < *(q->_a + child))
            {
                PQueueSwap(q->_a + parent, q->_a + child);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    
    void PQueuePush(PQueue* q, PQueueDataType data)
    {
        assert(q);
        PQueueCheckCapacity(q);
        *(q->_a + q->_size) = data;
        q->_size++;
        PQueueAdjustUp(q, q->_size - 1);
    }
    
    void PQueuePop(PQueue* q)
    {
        assert(q);
        *(q->_a + 0) = *(q->_a + q->_size - 1);
        q->_size--;
        PQueueAdjustDown(q, 0);
    }
    
    PQueueDataType PQueueTop(PQueue* q)
    {
        assert(q && (q->_size > 0));
        return *(q->_a + 0);
    }
    
    void PQueueDestroy(PQueue* q)
    {
        assert(q);
        free(q->_a);
        free(q);
    }
    
    void TestPQueue()
    {
        PQueueDataType arr[] = { 53,17,78,9,45,65,87,23,31 };
        PQueue* pq = PQueueInit();
        printf("入队列测试:");
        for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        {
            PQueuePush(pq, arr[i]);
        }
        for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        {
            printf("%d ", *(pq->_a + i));
        }
        printf("\n");
        printf("出队列测试:");
        for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        {
            printf("%d ", PQueueTop(pq));
            PQueuePop(pq);
        }
        printf("\n");
        PQueueDestroy(pq);
    }
    展开全文
  • 优先级队列堆实现

    2016-06-11 19:46:21
    优先级队列(priority queue)是0个或多个...(heap)[-数组表示]是实现优先级队列效率很高的数据结构。 即使完全二叉树又是大根树(或小根树),[ps:大根树指树中每个节点的值都大于或等于其子节点的值,小根树则相反]
    优先级队列(priority queue)是0个或多个元素的集合,每个元素都有一个优先权或值。优先级队列中,元素的出队列顺序不是同普通队列一样FIFO(先进先出),而是按照优先级递增或递减顺序,但不是元素进入队列的顺序。
    堆(heap)[-数组表示]是实现优先级队列效率很高的数据结构。
    堆即使完全二叉树又是大根树(或小根树),[ps:大根树指树中每个节点的值都大于或等于其子节点的值,小根树则相反]
    

    以大根堆为例;
    以下是大根堆的类代码:

    class maxHeap
    {
    public:
        maxHeap(unsigned lenth = 50)
        {
            heapLenth = lenth;
            heap= new int[heapLenth];
            heapSize = 0;
        }
        void initialize(int *theheap, int theSize);
        void push(const int& theElement);
        void pop();
        int &top();
        unsigned size()
        {
            return heapSize;
        }
    
        bool empty()
        {
            return heapSize == 0;
        }
    
    private:
        int *heap;
        unsigned heapSize;
        unsigned heapLenth;
    };

    功能实现:
    这里写图片描述
    大根堆的插入:
    如图-上 所示,这里有一棵5元素的大根堆,我们现在将值为21的元素插入其中, 插入过程是这样的:
    把新元素插入新节点,然后沿着新节点到根节点的路径,执行一趟起泡操作,将新元素与其父节点的元素比较交换,直到后者大于或等于前者为止。

    void maxHeap::push(const int &theElement)
    {
        int currentNode;
        currentNode = ++heapSize;
        while(currentNode != 1 && heap[currentNode / 2] < theElement)
        {
            heap[currentNode] = heap[currentNode / 2];
            currentNode /= 2;
        }
        heap[currentNode] = theElement;
    }

    大根堆的删除:
    大根堆中删除一个元素,就是删除根节点的元素。
    如图-下所示, 我们首先将根节点元素删除,我们的大根堆剩下了5个元素。此时的二叉树需要重新组织,以便乃是大根堆(即重构,以对应一棵完全二叉树)
    为此,我们先将位置⑥的元素2取出,然后删除原来2所在的节点,这样就得到了一个完全二叉树,如第三步所示,因为此时的二叉树不是大根树,所以我们还需要做一步下沉的操作,我们将根节点不断向较大的子节点下沉,直到沉到最底部,或根节点的值大于子节点的值。
    代码如下:

    void maxHeap::pop()
    {
        if(0 == heapSize){
            cout << "empty!";
            return ;
            }
        heap[1].~int();
        int lasttheElement = heap[heapSize--];
        int currentNode = 1;
        int child = 2;
        while(chile <= heapSize)
        {
            if(child < heapSize && heap[child] < heap[child + 1])
                child++;
            if(lasttheElement >= heap[child])
                break;
    
            heap[currentNode] = heap[child];
            currentNode =child;
            child *= 2;
        }
        heap[currentNode] = lasttheElement;
    }

    以下是大根堆初始化的代码:

    void maxHeap::initialize(int *theheap, int theSize)
    {
        delete []heap;
        heap = theheap;
        heapSize= theSize;
    
        for(int root = heapSize / 2; root >= 1; root--)
        {
            int rootElement = heap[root];
            int child = root * 2while(child <= heapSize)
            {
                if(child < heapSize && heap[child] < heap[child + 1])
                    child++;
                if(rootElement >= heap[child])
                    break;
    
                heap[child / 2] = heap[child];
                child *= 2;
            }
            heap[child / 2] = rootElement;
        }
    }

    才疏学浅,如有不足,多多指正

    展开全文
  • (一)优先级队列定义 ... * 用堆实现一个优先级队列 * 主要是添加、修改、删除节点 * 节点具有唯一性 * @author HHF * 2014年11月28日 */ public class PriorityQueue { public s...
  • 优先级队列Java实现

    2020-12-23 12:56:45
    优先级队列也是个队列,因此也是提供以下接口 ◼ int size(); // 元素的数量 ◼ boolean isEmpty(); // 是否为空 ◼ void enQueue(E element); // 入队 ◼ E deQueue(); // 出队 ◼ E front(); // 获取队列的头...
  • 这里我们要介绍的“优先级队列”是用“实现的。“优先级队列”不再遵循“先进先出”的规则。小顶堆实现优先级队列遵循“优先级最低的元素最先出列”的原则,大顶堆实现优先级队列遵循“优先级最高的元素最先...
  • JDK中优先级队列PriorityQueue实现分析

    千次阅读 2015-04-21 22:54:55
    Java优先级队列PriorityQueue我们知道,可以实现优先级队列优先级队列可以实现以下功能: 插入一个数值 取出最小的数值(获得数值,并且删除) 我们来看看JDK源码中的PriorityQueue的实现。 首先看一下注释...
  • 优先级队列)C++实现 优先级队列 优先级队列是一种用来维护由一组数据构成的集合的数据结构,其中每个元素都有一个相关的值称为关键字。借助结构可以实现优先级队列。 弹出操作 弹出操作,即取出最大元素操作...
  • 优先级队列(PriorityQueue):1.概念:2.优先级队列的一些基本方法(和队列(Queue)基本相同):3.实现代码: 1.概念: 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,...
  • 优先级队列——

    2019-10-29 08:17:14
    实现优先级队列效率很高的数据结构。是一棵完全二叉树,用二叉树的数组表示法最有效率。在链表结构中,在高度和重量上左高树也适合于表示优先级队列 :是一棵二叉树,且节点数据有顺序要求。最大...
  • 排序及优先级队列Java实现

    千次阅读 2017-03-19 19:46:55
    优先队列之前的一篇关于《编程珠玑》的读书笔试介绍过优先队列排序的一些内容(http://blog.csdn.net/megustas_jjc/article/details/52049845),近期进行算法的复习的时候,想到了对于之前排序的一些优化和想...
  • 首先想到使用数组或者链表来实现优先级队列。 如果使用有序数组,数组按优先级队列排序,出队和队列类似,区别在于入队时要找出新元素的位置,还要移动新元素位置后面的元素;如果使用无序数组,入队与队列类似,...
  • 1.最大优先级队列的一个应用是在一台分时的计算机上进行作业调度, 这种队列要执行的各个作业及它们之间的的相对优先的关系加以记录, 当一个作业完成或者中断的时候,用Extract_Max将其从就绪的要执行的队列中...
  • 最大能够在O(1)的...最大优先级队列的应用实例:基于优先级的作业调度,在所有等待调度的作业中,选择具有最大优先级作业进行处理。同时一个新的作业也可以插入到队列里面去。 例如可以实现自己的基于优先级...
  • 堆实现优先级队列

    2020-04-18 13:41:15
    文章目录1 用堆实现优先级队列 1 用堆实现优先级队列 如果最小键值元素拥有最高的优先级,那么这种优先队列叫作升序优先队列(即总是先删除最小的元素),类似的,如果最大键值元素拥有最高的优先级,那么这种优先...
  • 优先级队列

    2021-03-23 09:36:39
    1优先级队列 1.1 什么是优先级队列? 1.2 PriorityQueue的使用 2什么是? 2.1 概念 2.2 性质 2.3大和小 3 的基本操作 3.1建立 3.2插入元素 3.3获取顶元素 3.4删除顶元素 1优先级队列 1.1...
  • 优先级队列)堆堆的定义大小堆堆的创建向下调整建堆优先级队列模拟实现优先级队列TOPK问题 的定义 把所有元素按照完全二叉树的顺序存储方式存储。 在逻辑上是一个完全二叉树,实质上是一个顺序表。 ...
  • 算法和数据结构项目:优先级队列 以排序向量,未排序向量和的形式实现优先级队列实现之间的比较,显示了Heap数据结构的优点。
  • 在 RxSwift 框架中,在 PriorityQueue.swift 文件中,使用数组实现了一个优先级队列 PriorityQueue。 优先级队列(priority queue)是0个或者多个元素的集合,每个元素有一个优先级,可以在集合中查找或删除优先级...
  • * 优先级队列 * <p> * 优先级队列不再遵循先入先出的原则,而是分为两种情况: * 最大优先级队列,无论入队顺序如何,都是当前最大的元素优先出队 * 最小优先级队列,无论入队顺序如何,都是当前最小的...
  • 泛型优先级队列实现

    千次阅读 2011-10-12 17:05:04
    最近学了一下C++ 的泛型,想实践一下,于是写了一个泛型的优先级队列,并且用优先级队列实现了一个排序,很简洁。欢迎大家提意见。 如何实现一个优先级队列?要解决的两个关键问题便是入队和出队之后仍能保持小...
  • 堆实现优先级队列(Priority Queue)

    千次阅读 2018-04-13 22:52:38
    1.优先级队列定义: 优先级队列(priority queue) 是0个或多个元素的集合,每个元素都有一个优先权,对优先级队列执行的操作有(1)查找...2.优先级队列实现方案 优先级队列实现既要兼顾成本,也要兼顾效率 ...
  • 1.什么是是一种数据结构,底层是一种数组对象,它可以被视为一棵完全二叉树结构  最大:每个父节点的都大于孩子节点;...3.数据结构和优先级队列的代码实现 思想:从第一个非孩子节点的下标开始

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,851
精华内容 20,340
关键字:

优先级队列堆实现