精华内容
下载资源
问答
  • 某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要...

    前言

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


    一、最大优先队列

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

    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设计;
    类名MaxPriorityQueue

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

    实现代码如下:

    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 boolean less(int i,int j){
            return items[i].compareTo(items[j]) < 0;
        }
    
        //交换堆中i索引和j索引处的值
        private void exch(int i,int j){
            T temp;
            temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        //往堆中插入一个元素
        public void insert(T t){
            items[++N] = t;
            //使用上浮算法使堆有序
           swim(N);
        }
    
        //删除堆中最大的元素,并返回这个最大元素
        public T delMax(){
            //利用max保存索引1处的最大值
            T max = items[1];
            //交换
            exch(1,N);
            //删去最大元素,元素个数-1
            N--;
            //使用下沉算法使堆有序
            sink(1);
            //返回最大值
            return max;
        }
    
        //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
        private void swim(int k){
            while (k > 1){
                //比较其父结点和本身的大小
                if(less(k/2,k)){
                    exch(k/2,k);
                }
    
                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(max,k)){
                    break;
                }else {
                    //
                    exch(k,max);
                    k = max;
                }
            }
        }
    }
    

    测试代码如下:

    public class MaxPriorityQueueTest {
        public static void main(String[] args) {
            //创建优先队列
            MaxPriorityQueue<String> queue = new MaxPriorityQueue<>(15);
            //往队列中存储元素
            queue.insert("a");
            queue.insert("m");
            queue.insert("b");
            queue.insert("l");
            queue.insert("c");
            queue.insert("k");
            queue.insert("d");
            queue.insert("j");
            queue.insert("e");
            queue.insert("i");
            queue.insert("f");
            queue.insert("h");
            queue.insert("g");
            //通过循环从队列中获取最大的元素
            while (!queue.isEmpty()){
                String max = queue.delMax();
                System.out.print(max+" ");
            }
        }
    }
    
    

    测试结果如下:
    在这里插入图片描述
    最小优先队列API设计;
    类名MinPriorityQueue

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

    实现代码如下:

    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 boolean less(int i,int j){
            return items[i].compareTo(items[j]) < 0;
        }
    
        //交换堆中i索引和j索引处的值
        private void exch(int i,int j){
            T temp;
            temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        //往堆中插入一个元素
        public void insert(T t){
            items[++N] = t;
            swim(N);
        }
    
        //删除堆中最小的元素,并返回这个最小元素
        public T delMin(){
            T min = items[1];
            exch(1,N);
            N--;
            sink(1);
            return min;
        }
    
        //使用上浮算法,使索引k处的元素能在堆中处于一个正确的位置
        private void swim(int k){
            while (k > 1){
                //比较其父结点和本身的大小
                if(less(k,k/2)){
                    exch(k,k/2);
                }
    
                k = k/2;
            }
        }
    
        //使用下沉算法,使索引k处的元素能在堆中处于一个正确的位置
        private void sink(int k){
            while (2*k <= N){
                //记录最小元素
                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;
                }
    
                //判断父结点是否小于子结点
                if(less(k,min)){
                    break;
                }else {
                    //交换元素
                    exch(k,min);
                    k = min;
                }
            }
        }
    }
    

    测试代码如下:

    public class MinPriorityQueueTest {
        public static void main(String[] args) {
            //创建优先队列
            MinPriorityQueue<String> queue = new MinPriorityQueue<>(15);
            //往队列中存储元素
            queue.insert("a");
            queue.insert("m");
            queue.insert("b");
            queue.insert("l");
            queue.insert("c");
            queue.insert("k");
            queue.insert("d");
            queue.insert("j");
            queue.insert("e");
            queue.insert("i");
            queue.insert("f");
            queue.insert("h");
            queue.insert("g");
            //通过循环从队列中获取最大的元素
            while (!queue.isEmpty()){
                String min = queue.delMin();
                System.out.print(min+" ");
            }
        }
    }
    

    测试结果如下:
    在这里插入图片描述

    展开全文
  • 最大优先队列

    2020-05-25 14:45:50
    某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下,计算机的任务都是有优先级的,我们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就...

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

    最大优先队列API设计;
    类名:MaxPriorityQueue

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

    package com.test;
    
    import java.util.Comparator;
    
    /**
     * @Author zongx
     * @Date 2020/5/25 13:43
     * @Version 1.0
     */
    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 this.N;
        }
    
        //判断队列是否为空
        public boolean isEmpty() {
            return this.N == 0;
        }
    
        //判断堆中索引i处的值是否小于索引j处的值
        public boolean less(int i, int j) {
            return items[i].compareTo(items[j])<0;
        }
    
        //交换堆中i索引与j索引处的值
        public void exch(int i, int j) {
            T temp = items[i];
            items[i] = items[j];
            items[j] = temp;
        }
    
        //往堆中插入一个元素
        public void insert(T t) {
            items[++N] = t;
            swim(N);
        }
    
        //删除堆中最大的元素
        public T delMax() {
            T max = items[1];
            exch(1,N);
            N--;
            sink(1);
            return max;
        }
    
        //使用上浮算法,使索引k处的值处于一个正确的位置
        private void swim(int k) {
            while (k > 1) {
                // k/2小于k,则交换位置
                if (less(k/2, k)) {
                    exch(k/2, k);
                }
                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)) {
                    exch(k, max);
                    k = max;
                }else {
                    break;
                }
            }
        }
    }
    
    
    
    package com.test;
    
    public class MaxPriorityQueueTest {
        public static void main(String[] args) {
            //创建优先队列
            MaxPriorityQueue<String> queue = new MaxPriorityQueue<String>(15);
            //往队列中存储元素
            queue.insert("a");
            queue.insert("m");
            queue.insert("b");
            queue.insert("l");
            queue.insert("c");
            queue.insert("k");
            queue.insert("d");
            queue.insert("j");
            queue.insert("e");
            queue.insert("i");
            queue.insert("f");
            queue.insert("h");
            queue.insert("g");
            //通过循环从队列中获取最大的元素
            while (!queue.isEmpty()){
                String max = queue.delMax();
                System.out.print(max+" ");
            }
        }
    }
    
    

    展开全文
  • 优先队列

    2020-09-05 09:57:24
    某些情况下,我们可能需要队列中最大值或者最小值。普通的队列要完成这样的功能,需要每次遍历队列中的所有元素,比较并最大值,效率不是很高,这个时候我们就可以使用一种特殊的队列来完成这种需求,那...

    优先队列

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

    优先队列按照其作用不同,可以分为以下两种:
    最大优先队列:可以获取并删除队列中最大的值
    最小优先队列:可以获取并删除队列中最小的值

    最大优先队列

    //最大优先队列
    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 boolean less(int i,int j){
            return items[i].compareTo(items[j])<0;
        }
    
        //交换索引i处和索引j处的值
        private void exchange(int i,int j){
            T temp=items[i];
            items[i]=items[j];
            items[j]=temp;
        }
    
        //往堆中插入一个元素
        public void insert(T t){
            items[++N]=t;
            swim(N); //上浮
        }
    
        //删除堆中最大的元素,并且返回这个最大的元素
        public T delMax(){
            T max=items[1];
            //交换索引1和索引N处的值
            exchange(1,N);
            //删除最后位置上的元素
            items[N]=null;
            N--;
            sink(1);
            return max;
        }
    
        //上浮算法,使索引k处的元素能在堆中处于一个正确的值
        public void swim(int k){
            while (k>1){
                //比较当前结点和其父节点
                if(less(k/2,k)){
                    //父节点小于子节点,交换
                    exchange(k/2,k);
                }
                k=k/2;
            }
    
        }
    
        //下沉算法,使索引k处的元素能在堆中处于一个正确的位置
        public void sink(int k){
            while (2*k<=N){
                //找到子节点中较大者
                int max=2*k;
                if(2*k+1<=N){  //存在右子节点
                    if(less(2*k,2*k+1)){
                        max=2*k+1;
                    }
                }
    
                if(!less(k,max)){
                    break;
                }
                exchange(k,max);
                k=max;
            }
        }
    }
    

    测试代码

    import com.algorith.heap.MaxPriorityQueue;
    
    public class MaxPriorityQueueTest {
        public static void main(String[] args) throws Exception {
            String[] arr = {"S", "O", "R", "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+",");
            }
        }
    }
    

    最小优先队列

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

    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 boolean less(int i,int j){
            return items[i].compareTo(items[j])<0;
        }
    
        //交换索引i处和索引j处的值
        private void exchange(int i,int j){
            T temp=items[i];
            items[i]=items[j];
            items[j]=temp;
        }
    
        //往堆中插入一个元素
        public void insert(T t){
            items[++N]=t;
            swim(N); //上浮
        }
    
        public T delMin(){
            //索引1处的值是最小值
            T min=items[1];
            //交换索引1处和索引N处的值
            exchange(1,N);
            //删除索引N处的值
            items[N]=null;
            N--;
            sink(1);
            return min;
        }
    
        public void swim(int k){
            while (k>1){
                //如果当前结点小于父节点
                if(less(k,k/2)){
                    exchange(k,k/2);
                }
                k=k/2;
            }
        }
    
        public void sink(int k){
            while (2*k<=N){
                //找出子节点中较小的索引值
                int min=2*k;
                if(2*k+1<=N&&less(2*k+1,2*k)){
                    min=2*k+1;
                }
                //如果当前结点小于子节点中的最小值
                if(less(k,min)){
                    break;
                }
    
                exchange(k,min);
                k=min;
            }
    
        }
    
    }
    

    测试代码

    import com.algorith.heap.MinPriorityQueue;
    
    public class MinPriorityQueueTest {
        public static void main(String[] args) throws Exception {
            String[] arr = {"S", "O", "R", "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+",");
            }
        }
    }
    

    索引优先队列

    最大优先队列和最小优先队列,它们可以分别访问队列中最大元素和最小元素,但是它们有一个缺点,就是没办法通过索引访问已存在于优先队列中的对象,并更新它们。为了实现这个目的,则需要用到索引优先队列

    步骤一:
    存储数据时,给每一个数据元素关联一个整数,例如insert(int k,T t),我们可以看做k是t关联的
    整数,那么我们的实现需要通过k这个值,快速获取到队列中t这个元素,此时有个k这个值需要具有唯一性。
    最直观的想法就是我们可以用一个T[] items数组来保存数据元素,在insert(int k,T t)完成插入时,可以把k看做是items数组的索引,把t元素放到items数组的索引k处,这样我们再根据k获取元素t时就很方便了,直接就可以拿到items[k]即可。

    在这里插入图片描述

    步骤二:
    步骤一完成后的结果,虽然我们给每个元素关联了一个整数,并且可以使用这个整数快速的获取到该元素,但是,items数组中的元素顺序是随机的,并不是堆有序的,所以,为了完成这个需求,我们可以增加一个数组int[]pq,来保存每个元素在items数组中的索引,pq数组需要堆有序,也就是说,
    pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和
    items[pq[3]]。

    在这里插入图片描述

    步骤三:
    通过步骤二的分析,我们可以发现,其实我们通过上浮和下沉做堆调整的时候,其实调整的是pq数组。如果需要
    对items中的元素进行修改,比如让items[0]=“H”,那么很显然,我们需要对pq中的数据做堆调整,而且是调整
    pq[9]中元素的位置。但现在就会遇到一个问题,我们修改的是items数组中0索引处的值,如何才能快速的知道需
    要挑中pq[9]中元素的位置呢?
    最直观的想法就是遍历pq数组,拿出每一个元素和0做比较,如果当前元素是0,那么调整该索引处的元素即可,
    但是效率很低。
    我们可以另外增加一个数组,int[] qp,用来存储pq的逆序。例如:
    在pq数组中:pq[1]=6;
    那么在qp数组中,把6作为索引,1作为值,结果是:qp[6]=1;

    在这里插入图片描述

    public class IndexMinPriorityQueue<T extends Comparable<T>> {
        private T[] items;  //存储堆中的数据元素
        private int[] pq;  //存储items数组元素的索引,pq数组需要堆有序
        private int[] qp;  //qp数组的索引值对应pq数组存储的元素值
                           //qp数组存储的元素值对应pq数组的索引值
    
        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];
            N=0;
            for (int i = 0; i < qp.length; i++) {
                //默认情况下,qp逆序中不保存任何索引
                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;
        }
    
        //交换堆中i索引处和j索引处的值
        private void exchange(int i,int j){
            //交换pq数组中的值
            int temp=pq[i];
            pq[i]=pq[j];
            pq[j]=temp;
    
            //更新qp数组中的值
            qp[pq[i]]=i;
            qp[pq[j]]=j;
        }
    
        //判断k对应的元素是否存在
        public boolean contains(int k){
            //默认情况下,qb所有元素都为-1,如果某个位置插入了数据,则不为-1
            return qp[k]!=-1;
        }
    
        //最小关联索引
        public int minIndex(){
            //pq的索引1处,存放的是最小元素在items的索引
            return pq[1];
        }
    
        //往队列中插入一个元素,并关联索引i
        public void insert(int i,T t){
            if(contains(i)){
                throw new RuntimeException("该索引已存在");
            }
            //个数加1
            N++;
            //把元素放到item数组中
            items[i]=t;
            //使用pq存放这个索引
            pq[N]=i;
            //在qp的i索引处存放N
            qp[i]=N;
            //上浮items[pq[N]],让pq堆有序
            swim(N);
        }
    
        //删除队列中最小元素,并返回该元素的关联索引
        public int delMin(){
            //找到items中最小元素的索引
            int minIndex=pq[1];
            //交换索引1和N的值
            exchange(1,N);
            //删除qp中索引为pq[N]的值
            qp[pq[N]]=-1;
            //删除pq索引N处的值
            pq[N]=-1;
            //删除items中最小元素
            items[minIndex]=null;
            N--;
            sink(1);
            return minIndex;
        }
    
        //删除索引i关联的元素
        public void delete(int i){
            //找出i在pq中的索引
            int k=qp[i];
            //吧pq中索引K处的值和索引N处的值交换
            exchange(k,N);
    
            //删除qp中pq[N]的值
            qp[pq[N]]=-1;
            //删除pq中索引N处的值
            pq[N]=-1;
            //删除item中索引i的值
            items[i]=null;
            N--;
            sink(k);
            swim(k);
        }
    
        //把与索引i关联的元素修改为t
        public void changeItem(int i,T t){
            //修改items数组中索引i处的值
            items[i]=t;
            //找到i在pq中的位置
            int k=qp[i];
            sink(k);
            swim(k);
        }
    
        //上浮算法
        public void swim(int k){
            while (k>1){
                //比较当前结点和父节点,如果当前结点比父节点小,交换位置
                if(less(k,k/2)){
                    exchange(k,k/2);
                }
                k=k/2;
            }
        }
    
        //下沉算法
        public void sink(int k){
            while (2*k<=N){
                //找出子节点中较小的值
                int min=2*k;
                if(2*k+1<=N&&less(2*k+1,2*k)){
                    min=2*k;
                }
    
                //如果当前结点比子节点的较小值小,结束下沉
                if(less(k,min)){
                    break;
                }
                exchange(k,min);
                k=min;
            }
        }
    
    
    
    }
    

    测试代码

    public class Test {
        public static void main(String[] args) {
            String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
            IndexMinPriorityQueue<String> indexMinPQ = new IndexMinPriorityQueue<>(20);
    //插入
            for (int i = 0; i < arr.length; i++) {
                indexMinPQ.insert(i,arr[i]);
            }
            System.out.println(indexMinPQ.size());
    //获取最小值的索引
            System.out.println(indexMinPQ.minIndex());
    //测试修改
            indexMinPQ.changeItem(0,"Z");
            int minIndex=-1;
            while(!indexMinPQ.isEmpty()){
                minIndex = indexMinPQ.delMin();
                System.out.print(minIndex+",");
            }
        }
    }
    
    展开全文
  • 某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要...
  • 某些情况下,我们可能需要找出 队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我 们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就...
  • Java数据结构--优先队列一、优先队列1.1 ...某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要这些计算机的任务中找出优
  • STL优先队列实现

    2020-06-25 16:26:01
    某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我 们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就...
  • 某些情况下,我们可能需要队列中最大值或者最小值。普通的 队列要完成这样的功能,需要每次遍历队列中的所有元素,比较并最大值,效率不是很高,这个时候,我们就可以使用一种特殊的队列来完成这种需求...
  • 内卷(思维+优先队列)

    2021-02-12 16:07:50
    思路:状态很多,尝试dp的话复杂度肯定不够。那么尝试贪心,靠贪心来化简状态。那么这里的贪心启发就是可以尝试找一个最特殊的...找最小值的过程用优先队列即可。 #include<iostream> #include<vecto..
  • k组区间,它们的公共交集=k组区间右端点最小值-k组区间左端点最大值。如果我们要区间大,那我们应该尽量让左端点小,右端点大。 先对区间按照左端点排序,然后用优先队列处理。 将区间按照左端点从小到大...
  • 这里,我们想实现的是快速最小值最大值),因此最小值最大值)应该根上。 所以我们可以得出一个堆序性:,对于每一个节点X,X的父亲的值应该小于等于(大于等于)X的值。 如果
  • 快速出一个集合最小值(或者最大值) 堆属性 堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。 最大堆,父节点的值比每一个子节点的值都要大。 最小堆,父节点的值比每一个子节点的值都...
  • 某些情况下,我们可能需要找出队列中最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有优先级的,我们需要这些计算机的任务中找出优先级最高的任务先执行,执行完毕后就需要...
  • 构造优先队列我们需要引入一个堆的该...堆的基本作用是,快速集合最大值或者最小值 建堆是根据向上调整,和向下调整同时完成的 我们所建的堆未考虑扩容,建堆的代码为大堆代码。 public class MyPriorityQueu...
  • 这里,我们想实现的是快速最小值最大值),因此最小值最大值)应该根上。 所以我们可以得出一个堆序性:,对于每一个节点X,X的父亲的值应该小于等于(大于等于)X的值。 如果你不知道二叉树这些...
  • 堆和优先级队列

    2021-02-15 20:48:44
    一个集合的数据最大值或者最小值 逻辑上完全二叉树 实际上是可以通过数组保存的 满足任意结点的值都大于其子树结点的值,叫做大堆,或者大根堆,或者最大堆 ,反之就是小堆 使用数组保存二叉树结构,...
  • STL的heap

    2019-10-23 21:19:51
    堆的常用方法:构建优先队列、支持堆排序、快速出一个集合最小值(或者最大值)。 (1)heap属性 1)堆属性分为两种:最大堆和最小堆。最大堆,父节点的值比每一个节点的值都要大。最小堆,父节点的值...
  • POJ 2823 (滑动窗口)

    2017-03-13 18:30:00
    这道题最容易想到的是用朴素的做法,即 每滑动一次,就遍历一次窗口最大最小值,这样时间复杂度为O(n*k),由于题目数据比较大,这种做法肯定是...假设优先队列中的元素是大值优先。先用未进行滑动的窗口内元素...
  • 应用场景:经常是一个数一个数的过来,比如找最大值或者找最小值 分类:堆本身是一个抽象的数据结构,根据实现形式,将其分为二叉堆、斐波那契堆等。 P.S: 二叉堆是堆(优先队列 priority_queue) 的一种常见且简单的...
  • 数据结构:堆(Heap)

    2019-07-18 23:23:27
    快速出一个集合最小值(或者最大值) 朋友面前装逼 堆属性 堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。 最大堆,父节点的值比每一个子节点的值都要大。 最小堆,父节点的值...
  • 数据结构__堆

    2019-02-27 15:28:06
    快速出一个集合最小值(或者最大值) 朋友面前装逼 堆属性 堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。 最大堆,父节点的值比每一个子节点的值都要大。最小堆,父节点的值比每...
  • 堆的常用方法:构建优先队列支持堆排序快速出一个集合最小值(或者最大值)朋友面前装逼堆属性堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。最大堆,父节点的值比每一个子节点的值都要大。...
  • 2019-11-07 19:59:30
    快速出一个集合最小值(或者最大值) 堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。 最大堆,父节点的值比每一个子节点的值都要大。最小堆,父节点的值比每一个子节点的值都要小。这...
  • 常用数据结构-堆

    2021-02-02 20:01:39
    快速出一个集合最小值(或者最大值) 朋友面前装逼 堆属性 堆分为两种:最大堆和最小堆,两者的差别在于节点的排序方式。 最大堆,父节点的值比每一个子节点的值都要大。最小堆,父节点的值比每...

空空如也

空空如也

1 2
收藏数 40
精华内容 16
关键字:

在最大优先队列中找最小值