`
java--hhf
  • 浏览: 308696 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

优先级队列(堆实现)

阅读更多

(一)优先级队列定义



(二)方法实现 

获得最大元素方法


去掉最大元素方法



 修改优先级方法


添加节点


 

(三)实现

/**
 * 用堆实现一个优先级队列
 * 主要是添加、修改、删除节点
 * 节点具有唯一性
 * @author HHF
 * 2014年11月28日
 */
public class PriorityQueue {

	public static int HEAPSIZE;
	public static void main(String[] args) {
		int[] array = Common.random(0,100,10);
		HEAPSIZE = array.length;
		build(array);//建一个极大堆
		System.out.println("原始数据:");
		Common.print(array);
	
		//获得最大值
		System.out.println("优先级最高的节点:"+maximum(array));
		
		//获得并删除最大值
		System.out.println("将要被删除的优先级最高的节点:"+extractMax(array));
		System.out.println("删除后的数据:");
		Common.print(array);
		
		//修改优先级
		increaseKey(array, 5, 100);
		System.out.println("修改后的数据:");
		Common.print(array);
		
		//添加节点
		insert(array, 101);
		System.out.println("插入后的数据:");
		Common.print(array);
		
		//删除节点
		System.out.println("删除的数据:"+delete(array, 1));
		System.out.println("删除后的数据:");
		Common.print(array);
	}
	
	/**
	 * 返回优先队列中优先级最高的节点
	 * @param array
	 * @return
	 */
	public static int maximum(int[] array){
		return array[0];
	}
	
	/**
	 * 去掉并返回优先级队列中优先级最高的节点
	 * @param array
	 * @return
	 */
	public static int extractMax(int[] array){
		if(HEAPSIZE < 1){
			(new Exception("队列内无元素    ")).printStackTrace();
			return 0;
		}
		//获得最优节点
		int max = array[0];
		//删除最优节点
		array[0] = array[--HEAPSIZE];
		//整理堆
		heapify(array, 0);
		//返回最优节点值
		return max;
	}
	
	/**
	 * 往优先队列中插入节点
	 * 记得要去重
	 * @param array
	 * @param x
	 */
	public static void insert(int[] array, int x){
		array[HEAPSIZE++] = x-1;//加一个元素
		increaseKey(array, HEAPSIZE-1, x);
	}
	
	/**
	 * 将优先级为x的节点优先级修改为k
	 * @param array
	 * @param i被修改值下标
	 * @param k
	 */
	public static void increaseKey(int[] array, int i, int k){
		if(HEAPSIZE <= i){
			(new Exception("修改优先级节点下标有误  ")).printStackTrace();
			return;
		}
		if(k <= array[i]){
			(new Exception("新节点的优先级被改低了  ")).printStackTrace();
			return;
		}
		//优先级被修改了
		array[i] = k;
		//整理队列
		int parent = (i-1)/2; //父节点下标
		while(parent>-1 && array[parent]<array[i]){//到了必要交换子父节点的时候了
			Common.swap(array, parent, i);
			i = parent;
			parent = (i-1)/2;
		}
	}
	
	/**
	 * 将下标为i的节点删除 并返回其值
	 * @param array
	 * @param i
	 */
	public static int delete(int[] array, int i){
		if(HEAPSIZE <= i){
			(new Exception("删除节点下标有误  ")).printStackTrace();
			return 0;
		}
		//优先级被修改了
		int result = array[i];
		//整理队列
		array[i] = -1;
		heapify(array, i);
		HEAPSIZE--;
		return result;
	}
	
	/**
	 * 将array变成一个极大堆
	 * @param array 堆
	 */
	public static void build(int[] array){
		int size = array.length;
		for(int i=size/2-1; i>=0; i--){
			heapify(array, i);
		}
	}
	
	/**
	 * 前提是i的左右孩子子树均已经为正常极大堆
	 * 将i调整为正确位置
	 * @param array
	 * @param i 下标
	 */
	public static void heapify(int[] array, int i){
		int left = 2*i+1;//左孩子下标
		int right = left+1;//右孩子下标
		int large = 0;
		//选出left right 和  i 三个下标对应的最大值 记其下标为large 
		if(left<HEAPSIZE  && array[left] > array[i]){
			large = left;
		}else{
			large = i;
		}
		if(right<HEAPSIZE && array[right] > array[large]){
			large = right;
		}
		//准备发生交换 和 递推下一轮
		if(large != i){
			Common.swap(array, large, i);
			heapify(array, large);//此时的i所对应的值 已经 下移一层到了large
		}
	}
}

 (ps:附件内附上工具类Common.zip)

  • 大小: 24 KB
  • 大小: 1.8 KB
  • 大小: 8 KB
  • 大小: 7.5 KB
  • 大小: 9 KB
  • 大小: 9.4 KB
  • 大小: 5.8 KB
  • 大小: 4 KB
  • 大小: 15.8 KB
  • 大小: 39 KB
0
0
分享到:
评论

相关推荐

    一个用堆实现的优先级队列

    在这个案例中,我们讨论的是一个用堆实现的最大优先级队列。 `Max_priority.cpp` 和 `Max_priority.h` 是两个关键文件,分别包含了实现和声明。`Max_priority.h` 文件可能定义了一个名为 `Max_PriorityQueue` 的...

    数据结构课设——小大根交替堆实现的双端优先级队列及应用

    数据结构课设——小大根交替堆实现的双端优先级队列及应用 小大根交替堆是一种特殊的堆结构,它可以同时满足大根堆和小根堆的性质。在本文中,我们将对小大根交替堆实现的双端优先级队列进行详细的分析和设计。 ...

    c语言实现优先级队列

    用c语言实现的,简单易懂,希望对大家有用。

    基于双端堆实现的优先级队列

    dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证)五个泛型算法,在此基础上实现了一个能在对数时间内获取最大和最小元素的优先级队列,相当于原stl优先级队列...

    优先级队列

    为了实现优先级队列,我们需要引入`&lt;priority_queue&gt;`头文件。C++中的`std::priority_queue`是一个容器适配器,它基于堆(heap)数据结构实现,确保了顶部的元素总是具有最高的优先级。 优先级队列的基本操作包括:...

    堆排序、优先级队列(c++模板实现)

    使用c++模板实现的堆排序、优先级队列,在vs2010下编译运行通过。压缩文件里为两个工程文件,如果有vs2010的话解压缩打开sln文件就可以了,没有的话,新建工程将文件复制过去就ok了。如果有问题可以留言。

    数据与算法:2基本数据结构7-优先级队列.pdf

    优先级队列的实现方式有多种,可以基于有序顺序表、无序顺序表、有序链表、无序链表、堆等数据结构。 在优先级队列中,每个元素都有一个优先权值,优先权值越高的元素越先被取出。例如,在任务队列中,每个任务都有...

    第10章-优先级队列2

    优先级队列可以通过各种方式实现,如数组、链表、堆等。其中,堆是一种非常常用的数据结构,它可以高效地支持优先级队列的操作。 在堆中,每个节点都有一个关键码,用于确定节点的优先级关系。堆的根节点是整个堆的...

    毕业设计MATLAB_优先级队列.zip

    在MATLAB中,实现优先级队列的一种常见方法是使用二叉堆。二叉堆是一种特殊的树形数据结构,可以保证父节点的优先级总是不低于(或不高于,取决于是最大堆还是最小堆)其子节点。这样,堆顶元素总是具有最高的优先级...

    第10章-优先级队列1

    "优先级队列" 在数据结构中,优先级队列是一种特殊的队列,队列中的每个元素都有一个优先级,...优先级队列的实现可以使用无序列表、有序列表、无序向量和有序向量四种方法,而完全二叉堆是其中的一种特殊实现方法。

    priority_queue优先级队列模拟实现

    优先级队列为大小堆的结构

    java使用小根堆实现优先级队列的几种方式

    总结来说,Java中的优先级队列通过小根堆实现,提供了高效的插入和删除操作。开发者可以直接使用`PriorityQueue`类,或者根据需求自定义小根堆。理解小根堆的原理和操作对于优化代码性能和解决复杂问题至关重要。...

    os.rar_优先级 队列

    这个文件可以帮助我们进一步理解在实际操作系统的实现中,如何处理优先级队列调度的复杂性。 总的来说,"os.rar_优先级 队列"的主题涉及了操作系统如何通过优先级队列优化进程调度,确保系统性能和响应速度。通过...

    数据结构与算法(Python语言描述)DS053优先级队列和堆排序ppt课件.ppt

    在Python中,可以使用内置的`heapq`模块来实现堆操作,包括插入元素(`heappush`)、弹出最大元素(`heappop`)以及构建堆(`heapify`)等,这些操作提供了高效且便捷的接口来处理优先级队列和堆排序问题。...

    优先级队列 priority queue

    优先级队列的实现,包括堆的实现,最大堆的生成

    数据结构与算法Python语言描述DS优先级队列和堆排序PPT学习教案.pptx

    总结来说,数据结构与算法中的优先级队列和堆排序在Python中可以通过不同的实现方法来达到高效的操作。优先级队列可以使用内置的`heapq`模块或者自定义的排序列表,而堆排序利用了堆数据结构的特性,能够在较短时间...

    二叉堆详解实现优先级队列.md

    二叉堆详解实现优先级队列.md

    6_7.rar_C++_inventedjoc_probablyjzn_基于最小化堆的整型优先级队列

    在这个特定的案例中,我们关注的是一个使用C++实现的、基于最小化堆的整型优先级队列。最小化堆是一种二叉堆,其中每个父节点的值都小于或等于其子节点的值,因此堆顶(根节点)总是具有最小的值。这种数据结构特别...

Global site tag (gtag.js) - Google Analytics