首页 > 代码库 > java最小堆实现优先权队列和求最大的n个数问题

java最小堆实现优先权队列和求最大的n个数问题

堆在实现优先权队列和求最大最小的n个数问题上,有着莫大的优势!

对于最大堆和最小堆的定义此处不再赘述,课参考网上文章:http://blog.csdn.net/genios/article/details/8157031

本文主要是对最小堆进行实现和应用,仅供新手参考。


优先权队列

优先权队列是一种非常有用的数据结构,操作系统的进程调度就有优先权队列的应用,如果用最小值表示最高的优先权,则使用最小堆,否则使用最大堆。


top-N值为问题:

对于求最大的n个数,可以用最小堆来实现,思路是:将n个数构建成一个最小堆,如果剩下的数有大于堆顶元素的值,则替换掉堆顶元素,再调整为最小堆,直到所有数字遍历完。


贴上源码:

关键类:

package com.algorithms;

/**
 * 最小堆,用数组实现,解决top-N问题
 * @author "zhshl"
 * @date	2014-10-22
 * @param <T>
 */

public class Min_Heap {
	
	private int heap[];
	private int maxSize; ////最多可容纳数目
	private int n;///元素数目
	
	
	/** 
	 * @param num 堆的大小
	 */
	public Min_Heap(int num){
		n=0;
		maxSize=num;
		heap=new int[maxSize];
	}
	
	
	
	/*
	*//**
	 * 初始堆是一颗任意次序的完全二叉树,从(n-2)/2处开始向下调整
	 * @param heap
	 * @param n
	 *//*
	public void createHeap(int[] heap2,int n){
		
		heap=heap2;
		
		for(int i=(n-2)/2;i>=0;i--){
			///从(n-2)/2处开始向下调整
			adjustDown(i,n-1);
		}
	}*/

	
	/**
	 * 元素入堆
	 * @param v
	 */
	public void append(int v){
		if(isFull()){
			System.out.println("heap is full ,can't append elements !");
			return ;
		}
		////元素插在末尾
		heap[n]=v;
		n++;
		///向上调整
		adjustUp(n-1);
		
		
	}
	
	
	/**
	 * 取出堆顶元素
	 * @return
	 */
	public int serve(){
		if(isEmpty()){
			System.out.println("heap is empty!");
			return Integer.MIN_VALUE;
		}
		
		int temp=heap[0];
		////用最后一个元素取代第一个元素
		heap[0]=heap[n-1];
		n--;
		//向下调整
		adjustDown(0, n-1);
		
		return temp;
	}	
	
	
	/**
	 * 求最大的n个数据
	 * @param data
	 * @param n
	 * @return null if n is bigger than the heap size, otherwise 
	 */
	public int[] getTopN(int []data,int n){
		heap=new int[n];
		maxSize=n;
		this.n=0;
	
		///构建初始堆
		for(int i=0;i<n;i++){
			append(data[i]);
		}
		
		for(int i=n;i<data.length;i++){
			////如果比堆顶元素大,则替换堆顶元素,并调整
			if(data[i]>heap[0]){
				heap[0]=data[i];
				adjustDown(0, n-1);
			}
		}
		
		return heap;
	}
	
	
	/**
	 * 对元素i进行向下调整,用于删除元素时调整
	 * @param i
	 * @param j
	 */
	private void adjustDown(int i, int j) {
		// TODO Auto-generated method stub
		int child=2*i+1;
		int temp=heap[i];///记录待调整的节点的值	
		while(child<j){
			////在范围内进行遍历调整
			
			if(heap[child]> heap[child+1]){
				///如果左孩子比右孩子大, 则指向较小的右孩子
				child++;
			}
			
			if(heap[child]>temp){
				///如果较小的孩子都比自己大,则退出
				break;
			}
			
			heap[(child-1)/2]=heap[child];
			child=child*2+1;
		}
		////循环结束,child指向最终位置的节点的左孩子
		heap[(child-1)/2]=temp;
		
	}
	
	
	
	
	/**
	 * 将i处的元素向上调整为堆,用于插入时候
	 * @param i
	 */
	private void adjustUp(int i){
		int temp=heap[i];
		while(i>0&&heap[(i-1)/2]> temp){
			///当父节点的值比temp大的时候,交换值
			heap[i]=heap[(i-1)/2];
			i=(i-1)/2;
		}
		heap[i]=temp;
	}
	
	
	/**
	 * 堆是否满了
	 * @return
	 */
	public boolean isFull(){
		return n>=maxSize;
	}
	
	/**
	 * 是否为空堆
	 * @return
	 */
	public boolean isEmpty(){
		return 0==n;
	}
}


测试类:

package com.algorithm.test;

import com.algorithms.Min_Heap;

/**
 * 最小堆测试类
 * @author "zhshl"
 * @date	2014-10-22
 *
 */
public class Min_Heap_Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Min_Heap heap=new Min_Heap(10);
		heap.append(2);
		heap.append(2);
		heap.append(13);
		heap.append(21);
		heap.append(2);
		heap.append(2);
		heap.append(53);
		heap.append(6);
		
		int temp;
		while(!heap.isEmpty()){
			temp=heap.serve();
			System.out.println(temp);
		}
		
		
		
		
		
		
		System.out.println("\n\n 求top-N问题:");
		int data[]={4,51,52,12,123,52,7643,234,123,33,44,2};
		
		data=http://www.mamicode.com/heap.getTopN(data, 5);>







java最小堆实现优先权队列和求最大的n个数问题