`
cjf068
  • 浏览: 34416 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

固定容量二叉堆

 
阅读更多
固定容量的二叉堆实现,可用于快速求top k 问题。如要求一个数组中top k的元素,则建立一个容量为k的大根堆,一次遍历数组add进该堆,遍历完毕,堆中的元素即为top k的所有元素。

固定容量大根堆代码
package org.jf.alg;

public class BigHeadFixedBinHeap <T extends Comparable>
{
	private Object array[];
	private int current_size = 0;

	public BigHeadFixedBinHeap(int size)
	{
		array =   new Object[size+1];
	}
	
	/**
	 * 往堆中添加一个元素
	 * 
	 *分两种情况:
	 *1.当前堆未满,直接添加到末尾,回溯保持堆性质
	 *2.当前堆已满,则找出最后一层中最大元素并与当前元素比较,若当前元素小,则替换,否则什么也不做
	 * 
	 * @param data
	 */
	public void add(T data)
	{
		int comp_begin = current_size/2+1;//求最小值的起始位置
		int indx = 1;//记录当前新插入的元素索引
		if(current_size<array.length-1)//堆未满 直接将新元素插入末尾
		{
			array[++current_size]=data;
			indx = current_size;
		}
		else//堆已满 查找最后一层中的最大值
		{
			
			int min_indx = comp_begin;
			T min = (T) array[min_indx];
			int i=comp_begin;
			while(i<array.length)
			{
				if(min.compareTo((T)array[i])>0)
				{
					min_indx = i;
					min = (T) array[min_indx];
				}
				
				i++;
			}
			
			if(min.compareTo(data)<0)
			{
				indx = min_indx;
				array[indx] = data;//当前的最小值被删除了
				
			}
			else
			{
				indx = 1;//不替换
			}
			
		}
		
		//向上检测
		while(indx>1)
		{
			//当前元素与其父节点比较  若小,则交换 indx = indx/2
			//否则 break
			int pdx = indx/2;
			if(((T)array[indx]).compareTo(((T)array[pdx]))>0)
			{
				Object tmp = array[indx];
				array[indx] = array[pdx];
				array[pdx]=tmp;
				indx = pdx;
			}else
			{
				break;
			}
		}
	}
	
	
	/**
	 * 删除堆顶元素
	 * 删除堆顶,用最后一个元素代替堆顶,向下检测保持堆性质
	 * 
	 * @return
	 */
	public T remove()
	{
		T data = null;
		if(current_size==0)
			return null;
		
		
		data = (T) array[1];
		array[1] = array[current_size];
		array[current_size]	= null;
		current_size -- ;

		//根节点与左右子节点中最小元素交换
		
		int indx = 1;

		int min_indx =indx;
		Object tmp = null;
		while((min_indx=getMaxIndx(indx))!=indx)
		{
			//indx 与 min_indx元素交换
			tmp = array[indx];
			array[indx]=array[min_indx];
			array[min_indx]=tmp;
			indx = min_indx;
		}
		
		return data;
	}
	
	
	private int getMaxIndx(int indx)
	{
		
		T left = null;
		T right = null;
		if(indx*2>this.current_size)//没有子节点
			return indx;
		if(indx*2==this.current_size)
			left = (T)array[indx*2];
		else
		{
			left = (T)array[indx*2];
			right =(T)array[indx*2+1];
		}
		
		
		if(right==null)
		{
		
			if(left.compareTo((T)array[indx])>0)
				indx =  indx*2;
			
			
		}else
		{
			
			if(left.compareTo((T)array[indx])>0)
			{
				indx = indx*2;
				if(right.compareTo((T)array[indx])>0)
					indx = indx+1;
			}
			else if(right.compareTo((T)array[indx])>0)
			{
				indx = indx*2+1;
			}
			
		}
		
		return indx;
	}
	
	public T peek()
	{
		if(this.current_size>0)
		return (T) array[1];
		
		return null;
	}
	

	public int capacity()
	{
		return array.length-1;
	}
	
	 void printArray()
	{
		for(int i=1;i<=this.current_size;i++)
		{
			System.out.print(array[i].toString()+" ");
		}
		System.out.println("\n");
	}
	 
	 public Object [] getAll()
	 {
		 Object[] newArray = new Object[this.current_size];
		 System.arraycopy(array, 1, newArray, 0, current_size);
		 return newArray;
	 }
	
}




固定长度小根堆代码
package org.jf.alg;

/**
 * 定长小根堆
 * 数组存储,数组第一个元素留空
 * 
 * 第k个元素的左儿子为 a[2k],右儿子为a[2k+1]
 * 
 * 第k个元素的父节点为a[k/2]
 * 
 * k从1记起
 * 
 * @author chenjf
 * 
 *
 */
public class LittleHeadFixedBinHeap<T extends Comparable> 
{

	private Object array[];
	private int current_size = 0;

	/**
	 * 
	 * @param size  堆大小
 	 */
	public LittleHeadFixedBinHeap(int size)
	{
		array =   new Object[size+1];

	}
	
	/**
	 * 往堆中添加一个元素
	 * 
	 *分两种情况:
	 *1.当前堆未满,直接添加到末尾,回溯保持堆性质
	 *2.当前堆已满,则找出最后一层中最大元素并与当前元素比较,若当前元素小,则替换,否则什么也不做
	 * 
	 * @param data
	 */
	public void add(T data)
	{
		int comp_begin = current_size/2+1;//求最大值的起始位置
		int indx = 1;//记录当前新插入的元素索引
		if(current_size<array.length-1)//堆未满 直接将新元素插入末尾
		{
			array[++current_size]=data;
			indx = current_size;
		}
		else//堆已满 查找最后一层中的最大值
		{
			
			int max_indx = comp_begin;
			T max = (T) array[max_indx];
			int i=comp_begin;
			while(i<array.length)
			{
				if(max.compareTo((T)array[i])<0)
				{
					max_indx = i;
					max = (T) array[max_indx];
				}
				
				i++;
			}
			
			if(max.compareTo(data)>0)
			{
				indx = max_indx;
				array[indx] = data;//当前的最大值被删除了
				
			}
			else
			{
				indx = 1;//不替换
			}
			
		}
		
		//向上检测
		while(indx>1)
		{
			//当前元素与其父节点比较  若小,则交换 indx = indx/2
			//否则 break
			int pdx = indx/2;
			if(((T)array[indx]).compareTo(((T)array[pdx]))<0)
			{
				Object tmp = array[indx];
				array[indx] = array[pdx];
				array[pdx]=tmp;
				indx = pdx;
			}else
			{
				break;
			}
		}
	}
	
	
	/**
	 * 删除堆顶元素
	 * 删除堆顶,用最后一个元素代替堆顶,向下检测保持堆性质
	 * 
	 * @return
	 */
	public T remove()
	{
		T data = null;
		if(current_size==0)
			return null;
		
		
		data = (T) array[1];
		array[1] = array[current_size];
		array[current_size]	= null;
		current_size -- ;

		//根节点与左右子节点中最小元素交换
		
		int indx = 1;

		int min_indx =indx;
		Object tmp = null;
		while((min_indx=getMinIndx(indx))!=indx)
		{
			//indx 与 min_indx元素交换
			tmp = array[indx];
			array[indx]=array[min_indx];
			array[min_indx]=tmp;
			indx = min_indx;
		}
		
		return data;
	}
	
	
	private int getMinIndx(int indx)
	{
		
		T left = null;
		T right = null;
		if(indx*2>this.current_size)//没有子节点
			return indx;
		if(indx*2==this.current_size)
			left = (T)array[indx*2];
		else
		{
			left = (T)array[indx*2];
			right =(T)array[indx*2+1];
		}
		
		
		if(right==null)
		{
		
			if(left.compareTo((T)array[indx])<0)
				indx =  indx*2;
			
			
		}else
		{
			
			if(left.compareTo((T)array[indx])<0)
			{
				indx = indx*2;
				if(right.compareTo((T)array[indx])<0)
					indx = indx+1;
			}
			else if(right.compareTo((T)array[indx])<0)
			{
				indx = indx*2+1;
			}
			
			
		}
		
		return indx;
	}
	
	public T peek()
	{
		if(this.current_size>0)
		return (T) array[1];
		
		return null;
	}
	

	public int capacity()
	{
		return array.length-1;
	}
	
	 void printArray()
	{
		for(int i=1;i<=this.current_size;i++)
		{
			System.out.print(array[i].toString()+" ");
		}
		System.out.println("\n");
	}
	
	 
	 public Object [] getAll()
	 {
		 Object[] newArray = new Object[this.current_size];
		 System.arraycopy(array, 1, newArray, 0, current_size);
		 return newArray;
	 }
}



分享到:
评论

相关推荐

    Visualization.rar

    二叉堆常用于实现优先级队列,Java中的PriorityQueue类就是基于二叉堆实现的。 哈夫曼树,又称最优二叉树,用于数据的无损压缩,通过构建最小带权路径长度的二叉树来实现。 这些数据结构和算法在实际编程中有着...

    排序及基本算法

    堆排序是选择排序的一种高效实现,利用二叉堆结构进行优化,减少查找最小元素的时间。 4. **归并排序**:归并排序采用分治法,将数组分成两个子数组,递归地对这两个子数组进行排序,然后将两个已排序的子数组合并...

    PriorityQueue:使用 O(LogN) 复杂度为测试类实现 PriorityQueue

    但是,它不会进行容量动态调整,一旦创建,容量固定。 8. **应用示例**:PriorityQueue常用于解决各种算法问题,如Dijkstra最短路径算法、Prim最小生成树算法等,它能快速找到当前的最优解。 在`PriorityQueue-...

    郑州大学软件学院数据结构试题(附有答案)

    顺序栈是具有固定容量的栈,当栈满时无法再进行压栈操作。在给定的题目中,元素的出栈顺序揭示了栈的某些操作,但未提及具体容量,所以实际容量取决于题目背景。 四、关于平衡二叉树: 平衡二叉树,如AVL树或红黑树...

    各种栈沐浴队列的源码

    可以使用二叉堆、斐波那契堆等数据结构实现。 数组和链表同样可以用来实现队列。数组实现的队列称为环形队列,它利用数组的循环特性,避免了数组长度固定的限制,但需要预先确定最大容量;链表实现的队列则更为灵活...

    数据结构课件.rar

    - 二叉堆(如最小堆和最大堆):用于优先队列实现,常用在堆排序和堆优化的优先级队列中。 7. **第七章 图** - 图的定义:节点和边构成的数据结构,用于表示网络、关系等复杂结构。 - 图的遍历:深度优先搜索...

    2009年全国硕士研究生入学考试统考计算机真题

    7) 小根堆的插入和调整:小根堆是每个节点的值都小于其子节点的二叉堆,插入新元素后需要调整堆以保持性质。 8) 第二次排序方法:根据排序后的结果,可判断是哪种排序方法,如直接选择排序、二路归并排序、堆排序或...

    《数据结构》期末复习题-答案.doc

    5. **小根堆**:小根堆是一种特殊的二叉堆,其中父节点的键值总是小于或等于其子节点的键值。在给定的关键字序列中,{12,21,49,33,81,56,69,41}构成小根堆。 6. **二叉树**:B树是一种自平衡的多路搜索树,...

    研究生计算机算法上机作业

    12.最小堆和优先队列:在数据结构中,最小堆是一种自平衡的二叉堆,常用于实现优先队列,例如在A*搜索算法中。 13.滑动窗口最大值/最小值问题:在数据流中找出固定窗口大小内的最大或最小值,如在线监控系统中的...

    《数据结构》期末复习题 答案.pdf

    5. 小根堆是一种特殊的二叉堆,其中父节点的键值小于或等于其子节点。选项A符合小根堆的要求。 6. B树是一种自平衡的多路搜索树,不是二叉树,因为它允许每个节点有多个子节点。 7. 顺序存储的二叉树中,节点A[i]...

    算法设计与分析之动态规划

    Dijkstra算法使用优先队列(如二叉堆)实现,保证每次选择当前未访问节点中距离源点最近的一个。Floyd-Warshall算法则通过填充一个二维数组,逐步考虑所有可能的中间节点,找出所有节点对之间的最短路径。 2. **...

    典型数据结构的实现

    动态顺序表可以随时增加或减少容量,而静态顺序表的大小在创建时固定。顺序表的优点是访问速度快,但插入和删除操作可能需要移动大量元素,效率较低。 2. **链表**:链表是一种非连续存储的数据结构,每个节点包含...

    408真题含答案09-18.pdf

    精简指令集计算机(RISC)的特点包括简单的指令集、固定长度的指令格式、使用寄存器-寄存器操作等。此题中需要根据RISC的定义来判断叙述的正确性。 以上问题中均涉及到了计算机专业领域的基础知识点,考生需要对...

    数据结构java

    1. **数组和ArrayList**:数组在Java中是固定大小的,一旦创建就不能改变容量。而ArrayList是ArrayList类的一个实例,它是基于动态数组的数据结构,可以自动调整容量,提供便利的添加、删除和修改元素的方法。 2. *...

    数据结构经典试题

    2. **树形结构**:树是具有层级关系的数据结构,包括二叉树、二叉搜索树、平衡二叉树(AVL树、红黑树)、堆(最大堆、最小堆)和 Trie 字典树等。二叉树每个节点最多有两个子节点,二叉搜索树确保左子树所有节点小于...

    《数据结构教程》第三版 课后上机答案(李春葆 的)

    2. **链表**:链表允许动态添加和删除元素,不同于数组的固定容量。答案中可能包含单链表、双链表的实现,以及插入、删除、遍历等操作。 3. **栈和队列**:栈是后进先出(LIFO)的数据结构,常用于表达式求值和递归...

    LeetCode:数据结构

    Java 中的 PriorityQueue 类基于二叉堆实现,常用于优先级任务的处理。 图(Graph)是由顶点和边构成的数据结构,Java 中一般通过邻接矩阵或邻接表来表示。图的应用广泛,如路由算法、社交网络分析等。 集合...

    各大高校《数据结构》考研历年真题

    二叉搜索树(BST)是其中一种,它保证左子树的值小于根节点,右子树的值大于根节点,适合进行查找操作。堆(如最大堆和最小堆)常用于优先队列的实现,具有堆性质,即父节点的值总是大于或等于其子节点。 4. 图结构...

    广工数据结构

    二叉树、二叉搜索树、平衡树(如AVL树、红黑树)等都是树的重要类型,广泛应用于文件系统、数据库索引等领域。 6. **图**:图是由节点(顶点)和边组成的,用于表示对象之间的关系。图可以是无向的或有向的,还可以...

    数据结构的一些面试题.pdf

    通常实现方式是预先分配一定容量,当达到容量上限时,重新分配更大的空间并将原有数据复制过去。 13. **解释图的表示方法:邻接矩阵和邻接表** - **邻接矩阵**:对于无向图而言,是一个N×N的矩阵,其中元素aij...

Global site tag (gtag.js) - Google Analytics