Posted on 2009-12-06 11:29
小强摩羯座 阅读(806)
评论(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();
}
}