精华内容
下载资源
问答
  • * 利用二叉堆实现优先队列 * @author Prince * * @param <Key> */ public class MaxPQ<Key extends Comparable<Key>> { private Key[] pq; //基于堆的完全二叉树 ...
    package com.prince.algorithm;
    
    
    /**
     * 利用二叉堆实现优先队列
     * @author Prince
     *
     * @param <Key>
     */
    public class MaxPQ<Key extends Comparable<Key>> {
    	private Key[] pq;   //基于堆的完全二叉树
    	private int N = 0;   //存储于pq[1..N]中,pq[0]没有使用
    	
    	public MaxPQ(int maxN) {
    		pq = (Key[]) new Comparable[maxN+1];
    	}
    	
    	public boolean isEmpty() {
    		return N==0;
    	}
    	
    	public int size() {
    		return N;
    	}
    	
    	/**
    	 * 插入元素
    	 * 将新元素加到数组末尾,增加堆的大小并让这个新元素上浮到合适的位置
    	 */
    	public void insert(Key v) {
    		pq[++N] = v;
    		swim(N);
    	}
    	
    	/**
    	 * 删除最大元素
    	 * 从数组顶端删去最大的元素并将数组的最后一个元素放到顶端,
    	 * 减小堆的大小并让这个元素下沉到合适的位置
    	 */
    	public Key delMax() {
    		Key max = pq[1];   //从根结点得到最大的元素
    		exch(1,N--);       //将其和最后一个结点交换
    		pq[N++] = null;
    		sink(1);              //恢复堆的有序
    		return max;      
    	}
    	
    	/**
    	 * 由下至上的堆有序化
    	 * 堆的有序状态因为某个结点变得比它的父结点更大被打破,交换其和其
    	 * 父结点来修复。交换后,该结点比它的两个子节点都大(一个是其曾经父结点,
    	 * 另一个是其父结点的子节点)重复此过程至稳定状态
    	 * @param k
    	 */
    	private void swim(int k) {
    		while(k>1&&less(k/2,k)) {
    			exch(k/2,k);
    			k = k/2;
    		}
    	}
    	
    	/**
    	 * 由上至下的堆有序化
    	 * 某个结点比它的两个子节点或其中之一更小了,通过将它和它的两个子
    	 * 结点中的较大者交换来使堆稳定
    	 * @param k
    	 */
    	private void sink(int k) {
    		while(2*k<=N) {
    			int j =2*k;
    			if(j<N&& less(j,j+1)) j++;   //是否有右子树
    			if(!less(k,j)) break;
    			exch(k,j);
    			k=j;
    		}
    	}
    	private boolean less(int i, int j) {
    		return pq[i].compareTo(pq[j])<0;
    	}
    	
    	private void exch(int i, int j) {
    		Key t = pq[i];
    		pq[i] = pq[j];
    		pq[j] = t;
    	}
    	
    	
    	
    	
    }
    

     

    展开全文
  • 实现如下: package MaxPQ; public class MaxPQ<Key extends Comparable<Key>>{ private Key[] pq; private int N= 0; public MaxPQ(int maxN){ pq =(Key[]) new Comparable[maxN+1]; } public boolean...

    堆有序的·二叉树,就是每个节点值都是大于等于它的子节点值。

    这里用大小为N+1的数组pq来表示一个大小为N的堆,不使用pq[0]。

    关于二叉树,有一个特点很重要,就是位置k的父节点是k/2,子节点是2*k和2*k+1。

     

    堆的有序化,包括两种情况:

    1.当某个节点的值增大时,采用的是由下至上的堆有序化,比较该节点与它的父节点的值,并根据比较结果交换位置。定义方法swim(上浮)。

    2.当某个节点的值减小时,采用的是由上至下的堆有序化,比较该节点与它的较大的那个子节点的值,并根据比较结果交换位置。定义方法sink(下沉)。

    实现如下:

    package MaxPQ;
    
    public class MaxPQ<Key extends Comparable<Key>>{
    	private Key[] pq;
    	private int N= 0;
    	public MaxPQ(int maxN){
    		pq =(Key[]) new Comparable[maxN+1];
    	}
    	public boolean isEmpty() {
    		return N==0;
    	}
    	public int size() {
    		return N;
    	}
    	public void insert(Key key) {
    		pq[++N] =key;
    		swim(N);
    	}
    	
    	public Key delMax() {
    		Key re =pq[1];
    		exch(1,N);
    		pq[N] =null;
    		N--;
    		sink(1);
    		return re;
    	}
    	
    	private void sink(int k) {//由上至下的堆有序化
    		while (2*k<=N) {
    			int j =2*k;
    			if (less(j,j+1)) {
    				j=j+1;
    			}
    			if (!less(k,j)) {
    				break;
    			}
    			else {
    				exch(k,j);
    				k = j;
    			}
    		}
    	}
    	private void swim(int k) {//由下至上的堆有序化
    		while (k>1&&less(k/2,k)) {
    			exch(k/2,k);
    			k =k/2;
    		}	
    	}
    	private void exch(int i, int j) {//交换第i、j个值
    		Key key = pq[i];
    		pq[i] = pq[j];
    		pq[j] = key;	
    	}
    	private boolean less(int i, int j) {//判断第i个值是否比第j个值小
    		return pq[i].compareTo(pq[j])<0;
    	}
    
    }

    测试如下:

    package MaxPQ;
    
    public class Test {
    	public static void main(String[] args) {
    		MaxPQ<Integer> m =new MaxPQ<Integer>(11);
    		System.out.println(m.isEmpty());
    		m.insert(2);
    		m.insert(6);
    		m.insert(4);
    		m.insert(7);
    		m.insert(0);
    		m.insert(8);
    		m.insert(3);
    		m.insert(5);
    		System.out.println(m.size());
    		System.out.println(m.delMax());
    		System.out.println(m.delMax());
    		System.out.println(m.size());
    		System.out.println(m.isEmpty());
    	}
    
    }

     

    结果如下:

     

     

    true
    8
    8
    7
    6
    false

     

    展开全文
  • 数据结构-优先队列(最大优先队列、最小优先队列、索引优先队列) 由于队列先进先出的特性,无法灵活按照优先级进行数据的获取。但是在应用中又有此类需求,例如... * 实现最大优先队列 * <T extend Comparable&g

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


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

    一、最大优先队列

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

    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;
            }
        }
    }
    
    展开全文
  • /**** @author sunnyykn*/class PriorityQ{//array in sorted order,from max at 0 to min at size - 1private int maxSize;private long[] queArray;private int nItems;public PriorityQ(int s){maxSize = s;...

    /**

    *

    * @author sunnyykn

    */

    class PriorityQ{

    //array in sorted order,from max at 0 to min at size - 1

    private int maxSize;

    private long[] queArray;

    private int nItems;

    public PriorityQ(int s){

    maxSize = s;

    queArray = new long[maxSize];

    nItems = 0;

    }

    public void insert(long item){

    int j;

    if(nItems == 0)

    queArray[nItems ++] = item;

    else

    {

    for(j = nItems - 1;j >= 0;j --)

    {

    if(item > queArray[j])

    queArray[j + 1] = queArray[j];

    else

    break;

    }

    queArray[j + 1] = item;

    nItems ++;

    }

    }

    public long remove()

    {

    return queArray[-- nItems];

    }

    public long peekMin()

    {

    return queArray[nItems - 1];

    }

    public boolean isEmpty()

    {

    return (nItems == 0);

    }

    public boolean isFull()

    {

    return (nItems == maxSize);

    }

    }

    class PriorityQApp

    {

    public static void main(String[] args)

    {

    PriorityQ thePQ = new PriorityQ(5);

    thePQ.insert(30);

    thePQ.insert(50);

    thePQ.insert(10);

    thePQ.insert(40);

    thePQ.insert(20);

    while(!thePQ.isEmpty())

    {

    long item = thePQ.remove();

    System.out.print(item + " ");

    }

    System.out.println("");

    }

    }

    展开全文
  • importjava.util.ArrayList;class MyHeap>{private ArrayListdata;private intMaxSize;private intsize;publicMyHeap() {this.MaxSize=0;this.size=0;}public booleanadd(Type Elem) {if(this.size>=this.MaxS...
  • Java优先队列(PriorityQueue)实现重写compare操作发布时间:2020-10-29 15:15:11来源:亿速云阅读:82作者:Leah这篇文章将为大家详细讲解有关Java优先队列(PriorityQueue)实现重写compare操作,文章内容质量较高,...
  • Java优先队列实现

    2018-10-31 17:14:16
    数据结构与算法第六章,优先队列,heap_maximum 返回优先队列的最大值 heap_extract_max 删除并返回最大值 max_heap_insert插入值为key的元素进优先队列中 。
  • 本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考,具体如下:package Demo;import java.util.NoSuchElementException;/** 小顶堆 java使用堆结构实现优先队列*/public class JPriorityQueue {@...
  • 【数据结构 1】顺序表及其Java实现 【数据结构 2】单向链表及其Java实现 ...优先队列一、什么是优先队列二、最大优先队列2.1 最大优先队列API设计2.2 最大优先队列代码实现三、最小优先队列3.1 最小优先队列A
  • /*** 优先队列实现:* 实现插入的时候有序*/public class PQueue {private int maxSize;private long[] queArray;private int nItems;public PQueue(int s) {maxSize = s;queArray = new long[max...
  • JAVA优先队列实现

    2020-02-24 00:11:27
    基于堆的优先队列实现 JAVA 二叉堆是一种特殊的堆,二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性:父节点的键值总是保持固定的序关系于任何一个子节点的键值,且每个节点的左子树和右子树都是一个二叉...
  • 优先队列Java实现

    千次阅读 2019-06-07 23:58:33
    实现了以下核心方法: pulbic void push (E x); public E poll (); public E peek (); public boolean isEmpty (); public void resize (); 详细设计: import java.util.Comparator; public class PriorityQueue&...
  • 最大优先队列类为: //基于堆结构的最大值优先的优先队列 public class MaxPrimaryQueue<Key extends Comparable<Key>>{ //用于保存堆的元素 private Key[] pq; //用于保存堆中目前存在的元素个数 ...
  • 优先队列至二项队列的理解以及JAVA实现
  • 优先队列 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在某些情况下,我们可能需要找出 队列中的最大值或者最小值,例如使用一个队列保存计算机的任务,一般情况下计算机的任务都是有...
  • 优先队列的应用优先队列在程序开发中屡见不鲜,比如操作系统在进行进程调度时一种可行的算法是使用优先队列,当一个新的进程被fork()出来后,首先将它放到队列的最后,而操作系统内部的Scheduler负责不断地从这个...
  • 二,优先队列的几种实现方法 数组,入队O(n),出队O(n); 无序链表,入队O(1),出队O(n); 有序链表,入队O(n),出队O(1); 二叉排序树,入队O(logn),出队O(logn),容易造成不平衡二叉树,因为deleteMin始终是从...
  • 1 //BinaryHeap class2 //3 //CONSTRUCTION: with optional capacity (that defaults to 100)4 //or an array containing initial items5 //6 //******************PUBLIC OPERATIONS*********************7 //void ...
  • java优先队列实现

    千次阅读 2019-03-20 12:56:39
    //以堆作为底层数据结构实现,对的实现看上一篇文章 public class PriorityQueue<E extends Comparable<E>> { private MaxHeap maxHeap ; public PriorityQueue() { maxHeap = new MaxHeap() ; }...
  • 优先队列算法实现(Java)

    热门讨论 2009-06-01 12:49:59
    该算法基于Java语言,对算法设计中的优先队列进行了实现,本人能力有限,如有bug请多指教
  • 这里主要介绍的是优先队列的二叉堆java实现,代码如下:package practice;import edu.princeton.cs.algs4.StdRandom;public class TestMain {public static void main(String[] args) {int[] a = new int[20];for ...
  • 接口见 队列的Java实现 基于***二叉堆*** 的实现 import java.util.Iterator; import java.util.NoSuchElementException; /** * 基于二叉堆的优先队列实现 */ public class BiMaxPq<Key extends Comparable<...
  • 打印二叉堆(Java实现) 打印二叉堆:利用层级关系 我这里是先将堆排序,然后在sort里执行了打印堆的方法printAsTree() public class MaxHeap 纯数据结构Java实现(6/11)(二叉堆&;优先队列) 堆其实也是树结构(或者说基于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,237
精华内容 494
关键字:

优先队列java实现

java 订阅