精华内容
下载资源
问答
  • 普通队列完成任务,需要遍历队列所有元素,比较并找出最大值,效率低下; 这时可以使用一种特殊的队列来完成需求,即优先队列。 按照功能需求分两种:1 最大优先队列:获取并删除队列中最大的值;2 最小优先队列:...

    0 优先队列

    1. 普通队列先进先出,队尾加,队头删;
    2. 某些情况下,我们需要找出队列中的最大值或最小值。比如使用一个队列保存计算机的任务,任务需要有优先级,我们需要找出优先级最高的任务先执行,执行完毕后将任务从队列删除。
    3. 普通队列完成任务,需要遍历队列所有元素,比较并找出最大值,效率低下;
    4. 这时可以使用一种特殊的队列来完成需求,即优先队列。
    5. 按照功能需求分两种:1 最大优先队列:获取并删除队列中最大的值;2 最小优先队列:获取并删除队列中最小的值。

    1 最大优先队列

    由于堆可以很方便地删除最大值,因此基于堆实现最大优先队列。

    Java实现:

    public class MaxPriorityQueue<T extends Comparable<T>> {
        //存储堆中的元素
        private T[] items;
        //记录堆中元素的个数
        private int N;
    
        public MaxPriorityQueue(int capacity) {
            this.items = (T[]) new Comparable[capacity+1];
            this.N = 0;
        }
    
        //获取队列中元素的个数
        public int size() {
            return N;
        }
    
        //判断队列是否为空
        public boolean isEmpty() {
            return N==0;
        }
    
        //往堆中插入一个元素
        public void insert(T t) {
            items[++N] = t;
            swim(N);
        }
    
        //删除堆中最大的元素,并返回这个最大元素
        public T delMax() {
            T max = items[1];
            exch(1,N);
            items[N] = null;
            N--;
            sink(1);
            return max;
        }
    
        //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
        private void swim(int k) {
            while(k>1){
                if (less(k/2,k)){
                    exch(k/2,k);
                } else {
                    break;
                }
                k = k/2;
            }
        }
    
        //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
        private void sink(int k) {
            while(2*k<=N){
                int max;
                if (2*k+1<=N){
                    if (less(2*k,2*k+1)){
                        max = 2*k+1;
                    }else{
                        max = 2*k;
                    }
                }else {
                    max = 2*k;
                }
                if (!less(k,max)){
                    break;
                }
                exch(k,max);
                k = max;
            }
        }
    
        //判断堆中索引i处的元素是否小于索引j处的元素
        private boolean less(int i, int j) {
            return items[i].compareTo(items[j])<0;
        }
    
        //交换堆中i索引和j索引处的值
        private void exch(int i, int j) {
            T tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
        }
    }
    
    public class Test {
        public static void main(String[] args) {
            String[] arr = {"S","O","T","E","X","A","M","P","L","E"};
            MaxPriorityQueue<String> maxpq = new MaxPriorityQueue<>(20);
            for (String s: arr) {
                maxpq.insert(s);
            }
            System.out.println(maxpq.size());
            String del;
            while(!maxpq.isEmpty()) {
                del = maxpq.delMax();
                System.out.print(del + ",");
            }
        }
    }
    
    10
    X,T,S,P,O,M,L,E,E,A,
    

    2 最小优先队列

    最大优先队列基于堆的思想实现,堆中存放数据的数组满足如下两个特性:

    1. 最大元素放在数组的索引1处;
    2. 每个结点的数据总是大于等于它的两个子结点的数据。

    为了实现最小优先队列,我们可以用相反的思想实现最小堆,使堆中存放数据的数据满足如下两个特性:

    1. 最小的元素放在数组的索引1处;
    2. 每个结点的数据总是小于等于它的两个子结点的数据。

    Java代码实现:

    public class MinPriorityQueue<T extends Comparable<T>> {
        //存储堆中的元素
        private T[] items;
        //记录堆中元素的个数
        private int N;
    
        public MinPriorityQueue(int capacity) {
            this.items = (T[]) new Comparable[capacity+1];
            this.N=0;
        }
    
        //获取队列中元素的个数
        public int size() {
            return N;
        }
    
        //判断队列是否为空
        public boolean isEmpty() {
            return N == 0;
        }
    
        //往堆中插入一个元素
        public void insert(T t) {
            items[++N] = t;
            swim(N);
        }
    
        //删除堆中最小的元素,并返回这个最小元素
        public T delMin() {
            T min = items[1];
            exch(1,N);
            items[N] = null;
            N--;
            sink(1);
            return min;
        }
    
        //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
        private void swim(int k) {
            //通过循环比较当前结点和其父结点的大小
            while(k>1){
                if (less(k,k/2)){
                    exch(k,k/2);
                } else {
                    break;
                }
                k = k/2;
            }
        }
    
        //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
        private void sink(int k) {
            //通过循环比较当前结点和其子结点中的较小值
            while(2*k<=N){
                //1.找到子结点中的较小值
                int min;
                if (2*k+1<=N){
                    if (less(2*k, 2*k+1)){
                        min = 2*k;
                    }else{
                        min = 2*k+1;
                    }
                }else{
                    min = 2*k;
                }
                //2.判断当前结点和较小值的大小
                if (!less(min,k)){
                    break;
                }
                exch(k,min);
                k = min;
            }
        }
    
        //判断堆中索引i处的元素是否小于索引j处的元素
        private boolean less(int i, int j) {
            return items[i].compareTo(items[j])<0;
        }
    
        //交换堆中i索引和j索引处的值
        private void exch(int i, int j) {
            T tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
        }
    }
    
    public class Test {
        public static void main(String[] args) {
            String[] arr = {"S","O","T","E","X","A","M","P","L","E"};
            MinPriorityQueue<String> minpq = new MinPriorityQueue<>(20);
            for (String s: arr) {
                minpq.insert(s);
            }
            System.out.println(minpq.size());
            String del;
            while(!minpq.isEmpty()) {
                del = minpq.delMin();
                System.out.print(del + ",");
            }
        }
    }
    
    10
    A,E,E,L,M,O,P,S,T,X,
    
    展开全文
  • 使用堆的数据结构,可以很方便的获取当前等待队列中的最大值或最小值,所以对于优先队列可以采用堆的方式完成 一、最大优先队列 每次都获取队列中的最大值 参考代码 package priority; /** * 实现最大优先队列 * ...

    数据结构-优先队列(最大优先队列、最小优先队列、索引优先队列)


    由于队列先进先出的特性,无法灵活按照优先级进行数据的获取。但是在应用中又有此类需求,例如计算机按照优先级进行的任务调度。
    所以需要对于队列进行改进,以满足此类需求
    使用堆的数据结构,可以很方便的获取当前等待队列中的最大值或最小值,所以对于优先队列可以采用堆的方式完成

    一、最大优先队列

    每次都获取队列中的最大值
    参考代码

    package priority;
    
    /**
     * 实现最大优先队列
     * <T extend Comparable> 代表泛型可以使用ComparerTo方法排序
     * @param <T>
     */
    public class MaxPriorityQueue<T extends Comparable> {
        //存储堆中的元素
        private T[] items;
        //记录堆中元素的个数
        private int N;
    
        public static void main(String[] args) {
            String[] arr = {"3","2","7","1", "6", "9"};
            MaxPriorityQueue<String> maxPQ = new MaxPriorityQueue<>(arr.length);
            for (String s : arr) {
                maxPQ.insert(s);
            }
            System.out.println("堆大小:"+maxPQ.size());
            String del = null;
            while (!maxPQ.isEmpty()){
                del = maxPQ.delMax();
                System.out.print(del+",");
            }
        }
        /**
         * 初始化堆
         */
        public MaxPriorityQueue(int capacity) {
            //创建一个items元素数组
            this.items = (T[]) new Comparable[capacity+1];
            this.N = 0;
        }
    
        /**
         * 获取队列中元素的个数
         */
        public int size(){
            return N;
        }
    
        /**
         * 盘对队列是否为空
         */
        public boolean isEmpty(){
            return N == 0;
        }
    
        /**
         * 判断堆中索引i处的元素是否小于索引j处的元素
         * @param i 堆元素索引i
         * @param j 堆元素索引j
         * @return  i是否小于j
         */
        private boolean less(int i,int j){
            return items[i].compareTo(items[j]) < 0;
        }
    
        /**
         * 对堆中索引i处元素和索引j处元素进行交换
         * @param i 堆元素索引i
         * @param j 堆元素索引j
         */
        private void exch(int i,int j){
            T temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        /**
         * 向堆中插入一个元素
         * @param t 待插入的元素
         */
        public void insert(T t){
            //在堆尾创建一个元素
            items[++N] = t;
            //由于新插入的元素破坏了堆的有序状态,需要进行上浮操作,保证堆有序
            swim(N);
        }
    
        /**
         * 删除并获取堆顶元素
         * 1)获取堆顶元素
         * 2)将堆中最后一个元素移动到堆顶
         * 3)删除堆中最后一个元素
         * 4)利用下沉算法,让最后一个元素回到正确的位置
         * 5)堆再次有序
         * @return
         */
        public T delMax(){
            T max = items[1];
            exch(1,N);
            items[N] = null;
            N--;
            sink(1);
            return max;
        }
        /**
         * 对插入元素导致堆无序,进行上浮操作
         * 1)每次与k的父节点相比,如果小于其父节点,则需要交换位置
         * @param k 造成无序的元素
         */
        public void swim(int k){
            //最多上浮的root根结点,即可退出while
            while (k>1){
                //k的父节点小于k,则需要调换两个结点的位置
                if(less(k/2,k)){
                    exch(k/2,k);
                }else{
                    break;
                }
                k = k/2;
            }
        }
    
        /**
         * 对删除堆顶元素后导致堆无序,需要进行下沉操作,保证顺序
         * 1)找到k的左右子树
         * 2)找出k左右子树的最大值
         * 3)比较其与k的大小
         * 4)如果大于k,则交换位置   (下沉)
         * 5)如果不大于k,则无需操作
         * @param k
         */
        public void sink(int k){
            int max = 0;
            //判断k位置的元素具有左右子树
            while (2*k<=N){
                max = 2*k;
                //判断是否有右子结点
                if(2*k+1<=N){
                    if (less(2*k,2*k+1)){
                        max = 2*k+1;
                    }
                }
                //判断当前结点与其子结点中的最大值大小
                if (less(k,max)){
                    exch(k,max);
                }else{
                    break;
                }
                //将k移动到其最大子树上,继续向下判断
                k = max;
            }
        }
    }
    
    

    二、最小优先队列

    每次都获取队列中的最小值
    参考代码

    package priority;
    
    /**
     * 最小优先队列
     */
    public class MinPriorityQueue<T extends Comparable> {
        private T[] items;
        private int N;
    
        public static void main(String[] args) {
            String[] arr = {"3","2","7","1", "6", "9"};
            MinPriorityQueue<String> minPQ = new MinPriorityQueue<>(arr.length);
            for (String s : arr) {
                minPQ.insert(s);
            }
            System.out.println("堆大小:"+minPQ.size());
            String del = null;
            while (!minPQ.isEmpty()){
                del = minPQ.delMin();
                System.out.print(del+",");
            }
        }
        public MinPriorityQueue(int capacity){
            items = (T[]) new Comparable[capacity+1];
            N = 0;
        }
        /**
         * 获取队列中元素的个数
         */
        public int size(){
            return N;
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty(){
            return N == 0;
        }
    
        /**
         * 判断堆中索引i处的元素是否小于索引j处的元素
         */
        private boolean less(int i,int j){
            return items[i].compareTo(items[j])<0;
        }
    
        /**
         * 交换索引i和索引j处的元素
         */
        private void exch(int i,int j){
            T temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        /**
         * 向堆中插入一个新元素
         * @param t
         */
        public void insert(T t){
            items[++N] = t;
            swim(N);
        }
        /**
         * 删除堆中最小的元素
         * @return  堆中最小的元素
         */
        public T delMin(){
            T min = items[1];
            exch(1,N);
            items[N] = null;
            N--;
            sink(1);
            return min;
        }
    
        /**
         * 较小元素上浮操作
         * @param k
         */
        private void swim(int k){
            while (k>1){
                if(less(k,k/2)){
                    exch(k,k/2);
                }else{
                    break;
                }
                k = k/2;
            }
        }
    
        /**
         * 较大元素下沉操作
         * @param k
         */
        public void sink(int k){
            int min = 0;
            while (2*k<=N){
                min = 2*k;
                if(2*k+1<=N){
                    if(less(2*k+1,2*k)){
                        min = 2*k+1;
                    }
                }
                if(less(min,k)){
                    exch(min,k);
                }
                k = min;
            }
        }
    }
    
    

    三、索引优先队列(重点)

    但是无论最大或最小优先队列,都无法通过索引获取其中的其他元素。故应用索引优先队列。该队列可以根据索引获取队列中的元素信息

    • 为实现索引优先队列,我们可以在插入元素时将元素与一个索引相关联,之后便可以使用索引获取元素,但此时就无法保证堆的有序,因为如果要有序势必会移动元素,改变其索引位置。
    • 所以需要创建一个辅助数组,存放元素的索引。形成一个逻辑堆,每次只对逻辑堆进行修改,移动其逻辑堆中实际元素的索引位置,这样便解决了问题
    • 但是这样的话,我们无法通过逻辑堆的索引获取元素的值,因此当我们需要修改元素值时,只能一个一个比较要修改的元素找到其在堆中的位置
    • 所以,我们仍需要一个数组来记录辅助数组与元素之前的关系,可以将新数组的索引作为辅助数组的值,辅助数组的值作为新数组的索引。这样我们可以根据新数组的索引快速定位到要修改的元素在堆中的位置
    • 可以理解为堆中不存放具体的数据,而存放数据的引用
    • 三个数组之间的关系如图在这里插入图片描述
      参考代码
    package priority;
    
    import java.util.Arrays;
    
    /**
     * 索引优先队列
     * 由于最大或最小优先队列每次只能够获得队列中的
     * 最大值或最小值,为了弥补其缺陷,设计了索引优先队列
     * 思想:
     * 建立辅助数组,对元素数组的索引进行移动,逻辑上移动
     * 元素的位置,但同时也会造成查找元素不能使用索引,
     * 故再次建立辅助数组的逆序数组(将辅助数组的下标与元素互换)
     * 所有对于堆的操作其实都是对堆元素items数组的索引进行操作,即pq数组
     */
    public class IndexMinPriorityQueue<T extends Comparable<T>> {
       //存储堆中的元素
        private T items[];
        //存储元素在items数组中的索引,pq数组中需要堆有序
       private int[] pq;    //辅助数组
        //保存pq的逆序,pq的值作为索引,pq的索引作为值
       private int[] qp;    //逆序数组
        private int N;
    
        public static void main(String[] args) {
            String[] arr = {"3","2","7","1", "6", "9"};
            IndexMinPriorityQueue<String> indexMinPQ = new IndexMinPriorityQueue(arr.length);
            for (int i = 0; i < arr.length; i++) {
                indexMinPQ.insert(i,arr[i]);
            }
            System.out.println("初始化后堆大小:"+indexMinPQ.size());
            System.out.println("最小元素在items中的下标:"+indexMinPQ.minIndex());
            indexMinPQ.changeItem(0,"5");
            String minVal = null;
            while (!indexMinPQ.isEmpty()){
                minVal = indexMinPQ.delMin();
                System.out.println("获取堆中最小值:"+minVal);
            }
        }
        public IndexMinPriorityQueue(int capacity) {
            items = (T[]) new Comparable[capacity+1];
            pq = new int[capacity+1];
            qp = new int[capacity+1];
            N = 0;
            //初始化逆序数组,默认其中不存储任何索引
            for (int i = 0; i < qp.length; i++) {
                qp[i] = -1;
            }
        }
        /**
         * 获取队列中元素个数
         */
        public int size(){
            return N;
        }
    
        /**
         * 判断队列是否为空
         */
        public boolean isEmpty(){
           return N == 0;
        }
    
        /**
         * 判断堆中索引pq[i]处元素是否小于索引pq[j]处的元素
         * @param i pq数组的索引
         * @param j pq数组的索引
         * @return
         */
        private boolean less(int i,int j){
            //pq数组中存放的是元素在items数组中的索引
            return items[pq[i]].compareTo(items[pq[j]])<0;
        }
    
        /**
         * 交换堆中索引i和j处的值
         * 实际上是移动的items数组的索引数组pq中的items的元素下标
         * @param i pq[i]
         * @param j pq[j]
         */
        private void exch(int i,int j){
            //交换堆元素的索引位置,保证堆有序
            int temp = pq[i];
            pq[i] = pq[j];
            pq[j] = temp;
            //更新qp数组中的值,存放pq数组的逆序
            //qp的值为pq的索引,qp的索引为pq的值
            qp[pq[i]] = i;
            qp[pq[j]] = j;
        }
    
        /**
         * 判断k对应的元素是否存在
         * 由于pq[k]中存放items[]下标
         * qp[k]中的k代表items[]下标,值代表pq[]索引下标
         */
        public boolean contains(int k){
            //默认情况下,qp中的元素为-1,当qp不为-1,则有元素
            return qp[k] != -1;
        }
    
        /**
         * 最小元素关联的索引
         */
        public int minIndex(){
            //pq数组是逻辑上的堆,最小元素就应该在其索引1处
            return pq[1];
        }
    
        /**
         * 向队列中插入一个元素,并关联items索引i
         * @param i 要关联的索引
         * @param t 待插入的元素
         */
        public void insert(int i,T t){
            //判断i处是否已经有元素,如果有则不让插入
            if(contains(i)){
                throw new RuntimeException("该索引已经存在");
            }
            /**
             * 没有元素,则可以插入
             * 将元素插入items[i]
             * 将其下标放入逻辑堆pq[]
             * 将pq的下标放入其逆序数组qp[]
             */
            N++;
            items[i] = t;
            pq[N] = i;
            qp[i] = N;
            //上浮items[pq[N]],让pq堆有序
            swim(N);
        }
    
        /**
         * 获取并删除堆中最下的元素
         * 1)从逻辑堆上获取要删除元素的下标,根据下标对应找到items中的元素
         * 2)将最小元素获取后删除
         * 3)将逻辑堆堆首元素与堆尾元素交换位置
         * 4)删除逻辑堆中最后一个元素
         * 5)对应删除逆序数组中item元素的下标
         * 6)堆的大小-1
         * 7)对新的堆首元素进行下沉操作,使堆重新有序
         * @return  堆中最小的元素
         */
        public T delMin(){
            T minVal = items[pq[1]];
            items[pq[1]] = null;
            exch(1,N);
            qp[pq[N]] = -1;
            pq[N] = -1;
            N--;
            sink(1);
            return minVal;
        }
    
        /**
         * 删除索引i关联的元素
         * 删除方法:
         *      1)将索引i处的元素与堆的最后一个元素交换位置
         *      2)删除逆序数组中记录的元素位置
         *      3)删除pq[]中最后一个元素,即之前索引i处的元素
         *      4)删除items中真正的元素
         *      5)堆大小-1
         *      6)对堆进行下沉操作,保证堆有序
         * @param i 索引i
         */
        public void delete(int i){
            //找出i索引在pq[]中的索引,为了使删除后的堆重新有序
            int k = qp[i];
            exch(k,N);
            //删除对应索引处的元素索引
            qp[pq[N]] = -1;
            pq[N] = -1;
            items[i] = null;
            N--;
            //由于不清楚k所在堆中的具体位置,
            // 与最后一个元素交换后可能需要下沉也可能需要上浮
            sink(k);
            swim(k);
        }
    
        /**
         * 修改items中索引i处的元素为t
         * @param i 待修改元素的索引
         * @param t 新的元素值
         */
        public void changeItem(int i,T t){
            //修改真实元素
            items[i] = t;
            //获取逻辑堆中元素的下标
            int k = qp[i];
            //对逻辑堆进行下沉和上浮操作
            sink(k);
            swim(k);
        }
        /**
         * 逻辑堆的上浮操作
         * @param k
         */
        public void swim(int k){
            while (k > 1){
                if(less(k,k/2)){
                    exch(k,k/2);
                }else{
                    break;
                }
                k = k/2;
            }
        }
    
        /**
         * 逻辑堆的下沉操作
         * @param k
         */
        public void sink(int k){
            int min = 0;
            while (2*k<=N){
                min = 2*k;
                if(2*k+1<=N){
                    if(less(2*k+1,2*k)){
                        min = 2*k+1;
                    }
                }
                if(less(min,k)){
                    exch(min,k);
                }
                k = min;
            }
        }
    }
    
    展开全文
  • 优先队列最大优先队列)前言一、最大优先队列1、最大优先队列API设计2、代码3、测试用例4、输出结果 前言         普通的队列是一种先进先出的数据结构,元素在队列尾...

    前言

            普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在某些情况下,我们可能需要找出队列中的最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要在这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能,需要每次遍历队列中的所有元素,比较并找出最大值,效率不是很高,这个时候,我们就可以使用一种特殊的队列来完成这种需求,优先队列


    一、最大优先队列

            最大优先队列基于堆的数据结构来实现,可以很方便的删除最大值

    1、最大优先队列API设计

    类名 MaxPriorityQueue
    构造方法 MaxPriorityQueue(int capacity):创建容量为capacity的MaxPriorityQueue对象
    成员方法 1.private boolean less(int i,int j):判断堆中索引i处的元素是否小于索引j处的元素
    2.private void exch(int i,int j):交换堆中i索引和j索引处的值
    3.public T delMax():删除队列中最大的元素,并返回这个最大元素
    4.public void insert(T t):往队列中插入一个元素
    5.private void swim(int k):使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
    6.private void sink(int k):使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
    7.public int size():获取队列中元素的个数
    8.public boolean isEmpty():判断队列是否为空
    成员变量 1.private T[] imtes : 用来存储元素的数组
    2.private int N:记录堆中元素的个数

    2、代码

    package tree;
    
    /**
     * 最大优先队列
     */
    public class MaxPriorityQueue<T extends Comparable<T>> {
    
        private T[] items;
    
        private int n;
    
        public MaxPriorityQueue(int capacity) {
            items = (T[]) new Comparable[capacity + 1];
            n = 0;
        }
    
        /**
         * 判断堆中索引i处的元素是否小于索引j处的元素
         *
         * @param i
         * @param j
         * @return
         */
        private boolean less(int i, int j) {
            return items[i].compareTo(items[j]) < 0;
        }
    
        /**
         * 交换堆中i索引和j索引处的值
         *
         * @param i
         * @param j
         */
        private void exch(int i, int j) {
            T temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        /**
         * 删除队列中最大的元素,并返回这个最大元素
         *
         * @return
         */
        public T delMax() {
            T max = items[1];
            items[1] = items[n];
            items[n] = null;
            n--;
            sink(1);
            return max;
        }
    
        /**
         * 往队列中插入一个元素
         * @param t
         */
        public void insert(T t) {
            items[++n] = t;
            swim(n);
        }
    
        /**
         * 使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
         *
         * @param k
         */
        private void swim(int k) {
            while (k / 2 >= 1) {
                // 如果父节点小于当前节点
                if (less(k / 2, k)) {
                    exch(k / 2, k);
                    k = k / 2;
                } else {
                    break;
                }
            }
        }
    
        /**
         * 使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
         *
         * @param k
         */
        private void sink(int k) {
            while (2 * k + 1 <= n) {
                int maxIndex;
                if (less(2 * k, 2 * k + 1)) {
                    maxIndex = 2 * k +1;
                } else {
                    maxIndex = 2 * k;
                }
                if (less(k, maxIndex)) {
                    exch(k, maxIndex);
                    k = maxIndex;
                }else {
                    break;
                }
            }
        }
    
        /**
         * 获取队列中元素的个数
         *
         * @return
         */
        public int size() {
            return n;
        }
    
        /**
         * 判断队列是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return n == 0;
        }
    
    }
    

    3、测试用例

    package tree;
    
    import org.junit.Test;
    
    public class MaxPriorityQueueTest {
    
        @Test
        public void delMax() {
            int capacity = 10;
            MaxPriorityQueue<Integer> integerMaxPriorityQueue = new MaxPriorityQueue<Integer>(capacity);
            integerMaxPriorityQueue.insert(1);
            integerMaxPriorityQueue.insert(2);
            integerMaxPriorityQueue.insert(5);
            integerMaxPriorityQueue.insert(8);
            integerMaxPriorityQueue.insert(4);
            integerMaxPriorityQueue.insert(2);
            int size = integerMaxPriorityQueue.size();
            for (int i = 0; i < size; i++) {
                System.out.println(integerMaxPriorityQueue.delMax());
            }
        }
    
    }
    

    4、输出结果

    8
    5
    4
    2
    2
    1
    
    展开全文
  • 堆的根结点就是值最大的那一个, 删除最大的那一个就相当于把优先级最高的任务从队列中拿出来 最大优先队列 概念 优先级最大的先拿出来 API设计 代码 感觉和堆的代码没啥区别 === ...

    目录

    优先队列

    使用场景

    基于堆完成

    最大优先队列

    概念

    API设计

    代码

    最小优先队列

    概念

    API设计

    代码

    索引优先队列

    概念

    代码实现

    API设计

    代码


    1. 优先队列

      1. 使用场景

        1. 计算机任务队列
          1. 后来的任务需要在队列中等待, 然后计算机会从等待队列中拿出一个优先级最高的任务去执行, 如何实现从队列中拿出来的就是优先级最高的, 这就是优先队列需要解决的问题
      2. 基于堆完成

        1. 堆的根结点就是值最大的那一个, 删除最大的那一个就相当于把优先级最高的任务从队列中拿出来
    2. 最大优先队列

      1. 概念

        1. 优先级最大的先拿出来
      2. API设计

      3. 代码

        1. 感觉和堆的代码没啥区别
        2. package lq.priority;
          
          public class MaxPriorityQueue<T extends Comparable<T>> {
              //存储堆中的元素
              private T[] items;
              //记录堆中元素的个数
              private int N;
          
          
              public MaxPriorityQueue(int capacity) {
                  this.items = (T[]) new Comparable[capacity + 1];
                  this.N = 0;
              }
          
              //获取队列中元素的个数
              public int size() {
                  return N;
              }
          
              //判断队列是否为空
              public boolean isEmpty() {
                  return N == 0;
              }
          
              //交换堆中i索引和j索引处的值
          
              private void exchange(int i, int j) {
                  T tmp = items[i];
                  items[i] = items[j];
                  items[j] = tmp;
              }
              //往堆中插入一个元素
          
              public void insert(T t) {
                  items[++N] = t;
                  swim(N);
              }
              //删除堆中最大的元素,并返回这个最大元素
          
              public T delMax() {
                  T max = items[1];
                  //最后一个元素放最前面
                  items[1] = items[N];
                  //删除最后一个元素
                  items[N--] = null;
                  //从数组1的位置开始向下沉
                  sink(1);
                  return max;
              }
              //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
          
              private void swim(int k) {
                  while (k > 1) {
                      if (greater(k, k / 2)) {
                          exchange(k, k / 2);
                          k /= 2;
                      } else {
                          break;
                      }
                  }
              }
          
              //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
              private void sink(int k) {
                  while (2 * k <= N) {
                      int max;
                      if (2 * k + 1 <= N) {
                          max = greater(2 * k, 2 * k + 1) ? (2 * k) : (2 * k + 1);
                      } else {
                          max = 2 * k;
                      }
                      if (greater(k, max)) {
                          break;
                      }
                      exchange(k, max);
                      k = max;
                  }
              }
          
              //判断堆中索引i处的元素是否小于索引j处的元素
              private boolean less(int i, int j) {
                  return items[i].compareTo(items[j]) < 0;
              }
          
              private boolean greater(int i, int j) {
                  return items[i].compareTo(items[j]) > 0;
              }
          }
          

           

    3. 最小优先队列

      1. 概念

        1. 优先级最小的先拿出来
      2. API设计

      3. 代码

        1. 和堆没啥区别, 只是把最小的元素往前放而已
        2. package lq.priority;
          
          public class MinPriorityQueue<T extends Comparable<T>> {
              //存储堆中的元素
              private T[] items;
              //记录堆中元素的个数
              private int N;
          
          
              public MinPriorityQueue(int capacity) {
                  this.items = (T[]) new Comparable[capacity + 1];
                  this.N = 0;
              }
          
              //获取队列中元素的个数
              public int size() {
                  return N;
              }
          
              //判断队列是否为空
              public boolean isEmpty() {
                  return N == 0;
              }
          
              //交换堆中i索引和j索引处的值
              private void exchange(int i, int j) {
                  T tmp = items[i];
                  items[i] = items[j];
                  items[j] = tmp;
              }
              //往堆中插入一个元素
          
              public void insert(T t) {
                  items[++N] = t;
                  swim(N);
              }
              //删除堆中最大的元素,并返回这个最大元素
          
              public T delMin() {
                  T min = items[1];
                  //最后一个元素放最前面
                  items[1] = items[N];
                  //删除最后一个元素
                  items[N--] = null;
                  //从数组1的位置开始向下沉
                  sink(1);
                  return min;
              }
              //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
          
              private void swim(int k) {
                  while (k > 1) {
                      if (less(k, k / 2)) {
                          exchange(k, k / 2);
                          k /= 2;
                      } else {
                          break;
                      }
                  }
              }
          
              //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
              private void sink(int k) {
                  while (2 * k <= N) {
                      int min;
                      if (2 * k + 1 <= N) {
                          min = less(2 * k, 2 * k + 1) ? (2 * k) : (2 * k + 1);
                      } else {
                          min = 2 * k;
                      }
                      if (less(k, min)) {
                          break;
                      }
                      exchange(k, min);
                      k = min;
                  }
              }
          
              //判断堆中索引i处的元素是否小于索引j处的元素
              private boolean less(int i, int j) {
                  return items[i].compareTo(items[j]) < 0;
              }
          
              private boolean greater(int i, int j) {
                  return items[i].compareTo(items[j]) > 0;
              }
          }
          

           

    4. 索引优先队列

      1. 概念

        1. 最大或最小优先队列虽然可以获取最大或最小的元素, 但是无法获取任意元素
        2. 给所有的值关联一个唯一的键, 键是元素在数组中所存储的位置, 相当于一个符号表
        3. 在创建一个附加数组pq, 里面仅仅存储键
        4. 在创建一个qp数组, 用来存储pq数组的逆序
          1. qp数组的索引是pq数组的元素, qp数组的元素时pq数组的索引
          2. 如果你修改了items数组里面的一个值, 那么你就需要对堆重新排序, 找到修改的值在堆中什么位置
            1. items --> qp --> pq
        5. 最终需要用到3个数组
          1. items数组存储的是元素的值, qp数组存储的是元素在堆中的位置, 只有pq数组是真正的堆数组
      2. 代码实现

        1. API设计

        2. 代码

          1. package lq.priority;
            
            public class IndexMinPriorityQueue<T extends Comparable<T>> {
                //存储堆中的元素
                private T[] items;
                //保存每个元素在items数组中的索引,pq数组需要堆有序
                private int[] pq;
                //保存qp的逆序,pq的值作为索引,pq的索引作为值
                private int[] qp;
                //记录堆中元素的个数
                private int N;
            
            
                public IndexMinPriorityQueue(int capacity) {
                    this.items = (T[]) new Comparable[capacity + 1];
                    this.pq = new int[capacity + 1];
                    this.qp = new int[capacity + 1];
                    this.N = 0;
                    for (int i = 0; i < capacity + 1; i++) {
                        qp[i] = -1;
                    }
                }
            
                //获取队列中元素的个数
                public int size() {
                    return N;
                }
            
                //判断队列是否为空
                public boolean isEmpty() {
                    return N == 0;
                }
            
                //判断堆中索引i处的元素是否小于索引j处的元素
                private boolean less(int i, int j) {
                    return items[pq[i]].compareTo(items[pq[j]]) < 0;
                }
            
                private boolean greater(int i, int j) {
                    return items[pq[i]].compareTo(items[pq[j]]) > 0;
                }
            
                //交换堆中i索引和j索引处的值
                private void exchange(int i, int j) {
                    //交换pq中的数据
                    int tmp = pq[i];
                    pq[i] = pq[j];
                    pq[j] = tmp;
                    //交换qp中的数据
                    qp[pq[i]] = i;
                    qp[pq[j]] = j;
                }
            
                /**
                 * 判断k对应的元素是否存在
                 * 判断的是items[k]是否存在, 所以要去pq数组中看看有没有k这个值, 要去pq中找k,
                 * 可以去看qp数组中k位置处的值是不是-1, 是-1就代表不存在
                 *
                 * @param k
                 * @return
                 */
                public boolean contains(int k) {
                    return qp[k] != -1;
                }
            
                //最小元素关联的索引
                public int minIndex() {
                    return pq[1];
                }
            
            
                //往队列中插入一个元素,并关联索引i
                public void insert(int i, T t) {
                    if (contains(i)) {
                        return;
                    }
                    //往items里面添加
                    items[i] = t;
                    //往pq里面添加元素的元素的索引
                    pq[++N] = i;
                    //往qp里面添加元素在堆中的位置
                    qp[i] = N;
                    swim(N);
                }
            
                //删除队列中最小的元素,并返回该元素关联的索引
                public int delMin() {
                    int minIndex = pq[1];
                    //堆的最后一个和第一个交换位置
                    pq[1] = pq[N];
                    //删除堆中的最后一个
                    pq[N--] = -1;
                    //删除items中对应元素
                    items[minIndex] = null;
                    //删除qp中对应元素
                    qp[minIndex] = -1;
                    //让堆中第一个元素下沉
                    sink(1);
                    return minIndex;
                }
            
                /**
                 * 删除索引i关联的元素
                 * 这和删除堆的第一个元素方法是不太一样的
                 * 首先把要删除的元素和堆的最后一个互换位置, 然后要先进行一次上浮的操作, 然后在进行一次下沉的操作
                 *
                 * @param i
                 */
                public void delete(int i) {
                    //找到items[i]在pq中的位置k
                    int k = qp[i];
                    if (k == -1) {
                        return;
                    }
                    //删除items[i]
                    items[i] = null;
                    //删除qp[i]
                    qp[i] = -1;
                    //交换pq[k]和pq[N]的位置
                    pq[k] = pq[N];
                    //删除pq[N]
                    pq[N--] = -1;
                    //让堆中位置k的元素先进行上浮然后再进行下沉
                    swim(k);
                    sink(k);
                }
            
                //把与索引i关联的元素修改为为t
                public void changeItem(int i, T t) {
                    //修改items[i]
                    items[i] = t;
                    //找到items[i]在pq中的位置k
                    int k = qp[i];
                    //上浮 下沉
                    swim(k);
                    sink(k);
                }
            
            
                //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
                private void swim(int k) {
                    while (k > 1) {
                        if (greater(k / 2, k)) {
                            exchange(k / 2, k);
                            k /= 2;
                        } else {
                            break;
                        }
                    }
                }
            
            
                //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
                private void sink(int k) {
                    while (2 * k <= N) {
                        int min;
                        if (2 * k + 1 <= N) {
                            min = less(2 * k, 2 * k + 1) ? (2 * k) : (2 * k + 1);
                        } else {
                            min = 2 * k;
                        }
                        if (less(k, min)) {
                            break;
                        }
                        exchange(k, min);
                    }
                }
            }
            

             

    展开全文
  • //支持优先队列最大值和最小值删除,aType = 0是删除最小值 aType = 1是删除最大值 void STdeleteMinAndMax(int aType) {  STfilterData();   int ret = 0;   int i = 0;   int n = STcount();...
  • 然而在某些情况下,我们需要找到最大值,最小值,或某些特定元素进行删除,这个时候我们就可以用优先队列来实现这种需求。 1.1 最大优先队列 可以获取并删除队中最大的值。 实现方式和上篇讲的堆大同小异,因此不再...
  • 优先队列最大

    2018-07-30 21:32:42
    优先队列与最大堆 什么是优先队列 优先队列:出队顺序与入队顺序无关,和... 出队(拿出最大元素) 普通线性结构 O(1) O(n) 顺序线性结构 O(n) O(1) 堆 O(logn) O(logn) 可以看出普通与顺序的...
  • 最大优先队列

    千次阅读 2015-06-24 10:24:12
    最大优先队列前言 堆排序是一种集插入排序和选择排序的有点于一身的排序算法,但是在... 优先队列是一种用来维护由一组元素构成的集合S的数据结构,其中的每一个元素都有一个相关的,称为关键字。一个最大优先队列
  • 优先队列 普通的队列是一种先进先出的数据结构,元素在队列尾部追加,从而队列头删除。在某些情况下,我们可能需要找出队列中的最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下,计算机的任务都是...
  • (1)最大优先队列:可以获取并删除队列中最大 最大优先队列:无论入队的顺序,当前最大元素先出列。 (2)最小优先队列:可以获取并删除队列中最小的 最小优先队列:无论入队的顺序,当前最小的元素先...
  • 使用priority_queue容器适配器所有操作函数,实现最大值优先队列和最小值优先队列#include #include #include #include #include #include <functional>using namespace std; void main() {
  • 优先队列

    2020-09-05 09:57:24
    普通的队列要完成这样的功能,需要每次遍历队列中的所有元素,比较并找出最大值,效率不是很高,这个时候我们就可以使用一种特殊的队列来完成这种需求,那就是优先队列 优先队列按照其作用不同,可以分为以下两种: ...
  • 它的操作不仅局限于队列的先进先出,可以按逻辑(按最大值或者最小值等出队列)。普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高...
  • 优先队列是一种用来维护由一组元素构成的集合的数据结构,可以用堆来实现。在优先队列中,元素被赋予优先级,当访问元素时,具有最高级优先级的元素先被访问。 最大优先队列可用于共享计算机系统的作业调度等,最小...
  • C++之priority_queue(最大值优先级队列、最小值优先队列) 文章目录C++之priority_queue(最大值优先级队列、最小值优先队列)前言一、优先级队列二、用法三、用法案例 前言 1、最大值优先级队列、最小值优先级队列 2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,067
精华内容 21,626
关键字:

优先队列删除最大元素