`
flyingdutchman
  • 浏览: 358060 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

优先队列

阅读更多
        在现实的生活工作中,有许多情况下都要处理有序的元素,但又不要求全部有序,再或者不要求一次就将它们全部排序,这种情况下一种叫“优先队列”的算法就派上了用场。比如说,不要求全排序一个大数据集合的数据,或内存一次装不下整个数据集,但是要求获得最大或最小的M有序的数组。
       本节我们会学习基于二叉堆数据结构的优先队列的实现。优先队列最重要的操作就是删除最大元素和插入元素两种操作。数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中,每个元素都要保证大于等于两外2个特定位置的元素。(当一颗二叉的每个节点都大于等于它的两个孩子节点时,被称为堆有序。)
       用数组(堆)实现的完全二叉树,结构严格有灵活,能实现对数级别的插入元素和删除最大元素的操作。代码如下:
 /**
 * 基于数组(堆)实现的完全二叉树的优先队列
 * @author jacky
 *
 */
 public class MaxPriorityQueue<Key extends Comparable<Key>>{
	//基于堆的完全二叉树
	private Key[] pq; 
	//将数据存储在pq[1 ... N]中,pq[0]不使用
	private int size = 0;
	
	/**
	 * 默认创建一个大小为Integer.MAX_VALUE的队列
	 */
    public MaxPriorityQueue(){
    	pq = (Key[])new Comparable[Integer.MAX_VALUE];
    }
    
    public MaxPriorityQueue(int max){
    	pq = (Key[])new Comparable[max + 1];
    }
    
    /**
     * 向优先队列中添加元素,将元素添加到数组的pq[++size]
     * @param v
     */
    public void push(Key v){
    	pq[++size] = v;
    	//由下至上的对有序化
    	swim(size);
    }
    /**
     * 由下至上的对有序化:循环比较pq[size/2]和pq[k],若pq[size/2] < pq[k]则
     * 交换数据,知道k = 1
     * @param k
     */
    private void swim(int k){
    	int cmp = k/2;
    	while(k > 1 && less(cmp,k)){
    		exch(cmp,k);
    		cmp = k/2;
    	}
    }
    
    /**
     * 将最大的元素从优先队列中取出
     * @return
     */
    public Key delMax(){
    	Key max = pq[1];//从根节点得到最大的元素
    	exch(1,size--);//将其和最后一个节点交换
    	pq[size+1] = null;//防止越界
    	sink(1);//由上到下恢复对的有序性
    	return max;
    }
    /**
     * 由上到下的对有序化
     * @param k
     */
    private void sink(int k){
    	while(2 * k <= size){
    		int j = 2 * k;
    		if(j < size && less(j,j+1)){
    			j++;
    		}else 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 tmp = pq[i];
    	pq[i] = pq[j];
    	pq[j] = tmp;
    }
    public boolean isEmpty(){
    	return size == 0;
    }    
    public int size(){
    	return size;
    }
 }
分享到:
评论

相关推荐

    优先队列-java可以选择属性和升序降序

    优先队列在Java编程中是一种特殊的数据结构,它遵循特定的出队顺序,通常是最小元素(最小优先队列)或最大元素(最大优先队列)先出队。这种数据结构在解决各种问题时非常有用,例如任务调度、事件驱动编程、搜索...

    用堆实现优先队列

    优先队列是一种特殊的数据结构,它允许我们按照优先级顺序处理元素。在计算机科学中,尤其是在算法和数据结构领域,优先队列常用于解决需要快速访问最高优先级元素的问题,如Dijkstra算法或Prim算法。在C语言中,...

    priority_queue_1.0_excitingfbh_matlab优先队列_matlab优先队列_优先队列_

    "priority_queue_1.0_excitingfbh_matlab优先队列_matlab优先队列_优先队列_"这个标题表明这是一个MATLAB环境下的优先队列实现,可能由excitingfbh开发者创建,版本为1.0。 描述中提到的"pq_create"是创建优先队列...

    用数组实现的优先队列(JAVA)

    优先队列是一种特殊的队列,它的主要特性是队首元素具有最高的优先级。在Java中,我们可以使用数组来实现优先队列。这篇文章将探讨如何利用数组实现优先队列,并通过提供的`PriorityQ.java`文件来深入理解其实现原理...

    优先队列算法实现(Java)

    优先队列是一种特殊的数据结构,它允许我们按照优先级顺序处理元素。在计算机科学中,尤其是在算法设计中,优先队列常被用于解决各种问题,如任务调度、事件驱动模拟和图形学等。本实现是用Java编程语言完成的,Java...

    优先队列(Priority Queue)是一种特殊类型的队列

    优先队列(Priority Queue)是数据结构中的一种特殊队列,它的主要特点是元素的出队顺序不是按照“先进先出”(FIFO)的原则,而是根据每个元素的优先级来决定。这种数据结构广泛应用于各种算法和系统设计中,如事件...

    最大和最小优先队列的基本操作

    根据给定文件的信息,我们可以详细地探讨一下最大优先队列和最小优先队列的基本操作。 ### 一、优先队列概述 优先队列是一种抽象数据类型,它支持一系列基本操作,如插入、删除等,并且队列中的元素具有不同的...

    采用优先队列式分枝限界法求解0/1背包问 题.pdf

    在讨论采用优先队列式分枝限界法求解0/1背包问题之前,我们需要先了解0/1背包问题的基本概念。0/1背包问题是一种组合优化问题,它的目标是在不超过背包总承重的前提下,从给定的一组物品中选择物品,使得选取物品的...

    优先队列实验报告

    优先队列是一种特殊的数据结构,它允许我们根据元素的优先级进行操作,通常用于处理具有紧急程度的任务。在这个实验报告中,优先队列是通过最大堆实现的,最大堆是一种完全二叉树,其中每个父节点的优先权重都大于或...

    简单的优先队列

    优先队列是一种特殊的队列,其中元素按照优先级顺序进行排列。在计算机科学中,它是一种数据结构,常用于处理需要快速访问最高优先级元素的问题。在这个话题中,我们将深入探讨与“简单的优先队列”相关的几个核心...

    利用堆实现的优先队列

    ### 利用堆实现的优先队列 #### 引言 在计算机科学领域,优先队列是一种非常重要的数据结构,它被广泛应用于多种算法中,如任务调度、事件驱动模拟等场景。相比于传统队列,优先队列允许插入元素时指定一个优先级...

    C-优先队列

    优先队列是一种特殊的数据结构,它允许我们按照优先级处理元素。在计算机科学中,特别是在算法和数据结构领域,优先队列通常用于实现任务调度、事件驱动模拟、图的最短路径计算等场景。在C语言中,由于没有内置的...

    数据结构课程设计优先队列数据(priority_queue)类型

    优先队列是一种特殊类型的队列,它遵循“优先”原则,即队列中的元素可以根据某种优先级被处理。在数据结构课程设计中,优先队列数据类型(priority_queue)是核心概念之一,常用于实现高效的调度、搜索和优化问题。...

    STL-优先队列-队列-栈

    "STL优先队列、队列、栈" STL(Standard Template Library)中的优先队列、队列、栈是三个非常重要的数据结构,它们在实际应用中有着广泛的应用。本文将详细介绍STL中的优先队列、队列、栈,包括它们的定义、操作、...

    基于K叉树的优先队列

    ### 基于K叉树的优先队列 #### 概述 本文介绍了一种新的优先队列实现方法,即**基于K叉树的优先队列**。此方法旨在优化传统二叉堆基础上的优先队列算法,提高处理大规模数据集时的效率。通过构建一种特殊的K叉树堆...

    优先队列、图等总结及习题.docx

    优先队列、图等总结及习题 优先队列是一种特殊的队列结构,它的出队顺序是根据元素的优先权决定的,而不是元素入队的顺序。优先队列的操作包括查找、插入和删除,删除操作是根据优先权高或低的次序进行的。 一、...

    多级优先队列.zip

    在IT领域,多级优先队列(Multi-Level Priority Queues)是一种重要的数据结构,尤其在操作系统设计中扮演着核心角色。这种数据结构允许我们高效地处理具有不同优先级的任务,通常用于调度算法,如进程调度或任务...

    优先队列代码堆实现

    优先队列是一种特殊的数据结构,它允许我们快速访问或删除具有最高优先级的元素。在计算机科学中,优先队列通常用作调度任务、事件驱动模拟等场景的基础。本程序通过堆来实现优先队列,堆是一种二叉树形结构,满足堆...

    关于STL中优先队列的用法

    ### 关于STL中优先队列的用法 #### 一、引言 在C++标准模板库(STL)中,优先队列是一种非常有用的容器类型,它提供了高效的访问最大或最小元素的方式,通常用于解决需要频繁进行查找、插入和删除最大(或最小)值...

    批处理作业调度问题·优先队列式分支限界法·回溯法

    本项目通过C++语言实现了批处理作业调度问题的解决方案,利用了优先队列式分支限界法和回溯法这两种高级算法。 1. **批处理作业调度问题**:批处理作业调度是指将一组离散的作业分配给计算机系统,以最大限度地提高...

Global site tag (gtag.js) - Google Analytics