posts - 195, comments - 34, trackbacks - 0, articles - 1

使用用最小堆来找最大的K个数

Posted on 2009-12-06 11:29 小强摩羯座 阅读(796) 评论(0)  编辑  收藏 所属分类: 算法编程
/**
     * 最小堆化,使用递归
     
*/

    
static void minHeapity(int[] a, int i, int size)
    
{
        
int left = (i << 1+ 1// i * 2 + 1,当下标从0正式开始时
        int right = (i << 1+ 2;
        
int t;
        
if (left < size && a[left] < a[i])
            t 
= left;
        
else
            t 
= i;
        
if (right < size && a[right] < a[t])
            t 
= right;
        
if (t != i)
        
{
            a[t] 
= a[i] + a[t] - (a[i] = a[t]);
            minHeapity(a, t, size);
        }

    }

    
/**
     * 最小堆化,不使用递归,并且合并表示
     * 
@param size
     
*/

    
static void minHeapityNOCur(int[] a, int i, int size)
    
{
        
int p = i;
    
        
while(p < size)
        
{
            
int q = p * 2 + 1;// q指向最小的孩子结点
            if( q >= size) return;
            
if( q < (size-1&& a[q+1< a[q])
                q 
= q + 1;// q 指向右
            if( a[q] < a[p])
            
{
                a[q] 
= a[p] + a[q] - ( a[p] = a[q]);
                p 
= q;
            }

            
else break;//已经不用调整了
        }

    }

    
static void maxK( int k)
    
{
        
int[] maxKs = new int[k];
        
try
        
{
            Scanner scan 
= new Scanner(new File("IntNums10K.txt"));
            
for (int i = 0; i < k; i++)
            
{
                
if (scan.hasNextInt())
                
{
                    maxKs[i] 
= scan.nextInt();
                }

            }

            System.out.println(
"最初K个值"+ Arrays.toString(maxKs));
            
// builder the heap
            int size = maxKs.length;
            
for (int i = (size - 1/ 2; i >= 0; i--)
                minHeapity(maxKs, i, size);
            
            System.out.println( 
"建堆后"+Arrays.toString(maxKs));
            
while(scan.hasNextInt())
            
{
                
int tmpN = scan.nextInt();
                
if( tmpN <= maxKs[0])
                    
continue;
                maxKs[
0= tmpN;
                minHeapity(maxKs, 
0, size);
            }

            System.out.println(
"得到最大的K个"+ Arrays.toString(maxKs));
        }
 catch (FileNotFoundException e)
        
{
            e.printStackTrace();
        }

    }



只有注册用户登录后才能发表评论。


网站导航: