`
songzi0206
  • 浏览: 158642 次
  • 性别: Icon_minigender_1
  • 来自: 上海
博客专栏
Group-logo
All are from ...
浏览量:33785
Group-logo
Programming w...
浏览量:19645
社区版块
存档分类
最新评论

优先队列

 
阅读更多

      在堆排序基础上顺便实现下优先队列,纯粹为实现下优先队列的思想,也顾不上代码丑陋了,嘿嘿,自己学习。

 

public class PriorityQueue<T extends Comparable<T>> {

	/**
	 * 和对排序中一样,第零个元素不做用
	 */
	private T[] queue;
	
	private int heapSize;
	
    /**
     * 初始化队列
     * @param a
     */
	@SuppressWarnings("unchecked")
	public void initPriorityQueue(T[] a){
		HeapSortor.buildMaxHeap(a);
		heapSize = a.length - 1;
		queue = (T[]) Array.newInstance(Comparable.class, 100);
		for(int i = 1; i < a.length; ++i)
			queue[i] = a[i];
		a = null;
	}
	
	/**
	 * 获取优先多列中第一个元素
	 * @return
	 */
	public T maxItem(){
		return queue[1];
	}
	
	/**
	 * 从队列中删除并返回最大元素,同时通过HeapSortor.maxHeapify保持优先队列特性
	 * @return
	 */
	public T extractMax(){
		T max = queue[1];
		HeapSortor.swap(queue,1, heapSize);
		heapSize--;
		HeapSortor.maxHeapify(queue, 1, heapSize);
		return max;
	}
	
	/**
	 * 将队列的第i个元素增加到key,然后调整使得队列保持优先队列特性
	 * @param key
	 * @param i
	 */
	public void increaseKey(T key, int i){
		if( key.compareTo(queue[i]) < 0 )
			throw new RuntimeException("The key is not greater than queue[i]");
		queue[i] = key;
		int parent = i/2;
		while( parent > 0 && queue[parent].compareTo(queue[i]) < 0){
			HeapSortor.swap(queue, i, parent);
			i = parent;
		}
	}
	/**
	 * 插入关键字key到优先多列中
	 * @param key
	 */
	public void insert(T key){
		queue[++heapSize] = key;
		increaseKey(key, heapSize);
	}
}
 
分享到:
评论

相关推荐

    优先队列-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