当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-5.查找最小的K个元素-使用最大堆

发表于: 2012-01-12   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Random; public class MinKElement { /** * 5.最小的K个元素 * I would like to use MaxHeap. * using QuickSort is also OK */ public static void
import java.util.Arrays;
import java.util.Random;


public class MinKElement {

	/**
	 * 5.最小的K个元素
	 * I would like to use MaxHeap.
	 * using QuickSort is also OK
	 */
	public static void main(String[] args) {
		MinKElement mke=new MinKElement();
		int[] a={1,2,3,4,5,6,7,8};
		int k=4;
		mke.disArrange(a);
		System.out.println("after disarranging,the array a[]="+Arrays.toString(a));
		mke.findKMin(a,k);
		
	}

	//rearrange the array.just for test.
	public void disArrange(int[] a){
		for(int i=0,len=a.length;i<len;i++){
			Random random=new Random();
			int j=random.nextInt(len);
			swap(a,i,j);
		}
	}
	public void findKMin(int[] a,int k){
		int[] heap=a;//you can do this:int[] heap=new int[k].but that maybe space-cost
		
		//create MaxHeap of K elements.from the lastRootIndex to 0.
		int rootIndex=k/2-1;
		while(rootIndex>=0){
			reheap(heap,rootIndex,k-1);
			rootIndex--;
		}
		for(int i=k,len=heap.length;i<len;i++){
			if(heap[i]<heap[0]){
				heap[0]=heap[i];
				reheap(heap,0,k-1);  
			}
		}
		System.out.print("the K min elements=");
		for(int i=0;i<k;i++){
			System.out.print(heap[i]+",");
		}
	}
	
	//reheap:from root to lastIndex.
	public void reheap(int[] heap,int rootIndex,int lastIndex){
		int orphan=heap[rootIndex];
		boolean done=false;
		int leftIndex=rootIndex*2+1;
		while(!done&&leftIndex<=lastIndex){
			int largerIndex=leftIndex;
			if(leftIndex+1<=lastIndex){
				int rightIndex=leftIndex+1;
				if(heap[rightIndex]>heap[leftIndex]){
					largerIndex=rightIndex;
				}
			}
			//Attention! should not use -->heap[root]<heap[largerIndex]<--.
			//I spend time to find the problem....
			if(orphan<heap[largerIndex]){
				heap[rootIndex]=heap[largerIndex];
				rootIndex=largerIndex;
				leftIndex=rootIndex*2+1;
			}else{
				done=true;
			}
		}
		heap[rootIndex]=orphan;
		
	}
	public void swap(int[] a,int i,int j){
		int temp=a[i];
		a[i]=a[j];
		a[j]=temp;
	}
}

java-5.查找最小的K个元素-使用最大堆

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
/* This is a free Program, You can modify or redistribute it under the terms of GNU *Descript
#include <iostream> #include <cstdlib> #include <vector> using namespace st
一、定义 最小-最大堆:是一棵完全二叉树,二叉树的各层交替为最小层和最大层,且根节点位于最小层
优先队列是一种非常常见的数据结构, 而最大最小树又是其中最具代表性的一种优先队列。 在此详细的
 堆的定义是:n个元素的序列{k1,k2,…,kn},当且仅当满足如下关系时被成为堆     (1)Ki <= k
在建立正确性的回归测试之后,继续前进。 首先用性能工具分析下, 发现有点悲剧: 效率又倒退了。去
上篇谈到, 之前的程序使用堆查找前K个最大值的效率并不理想,本篇尝试对程序进行优化,以提高程序
首先来观察一颗最大堆二叉树 和一个普通序列的映射情况:在序列中从length(LIST)/2+1 -> length(
原理:两个指针先都指向头指针的下一节点,一个指针先走K-1步,然后俩指针再一起走,后走的指针所指
原理:设置快慢指针,快指针和慢指针初始时都指向链表首节点,然后快指针向后走k个单位,再让慢指针
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号