数据结构优先队列讲解.ppt

heap sort java program public static void heapsort( Comparable [ ] a ) { for( int i = a.length / 2; i = 1; i-- ) percDown( a, i, a.length ); for( int i = a.length ; i 1; i-- ) { swapReferences( a, 1, i ); percDown( a, 1, i-1); } } heap sort private static void percDown( Comparable [ ] a, int i, int n ) { int child; Comparable tmp; for( tmp = a[ i ]; leftChild( i ) n; i = child ) { child = leftChild( i ); if( child != n – 1 a[child ].compareTo( a[ child + 1 ]) 0 ) child++; if( pareTo( a[ child ] ) 0 ) a[ i ] = a[ child ]; else break; } a[ i ] = tmp; } private static int leftChild( int i ) { return 2 * i + 1; } 6.4.Applications of Priority Queues 2. The Selection Problem 6.4.Applications of Priority Queues 2. The Selection Problem 在N个元素中找出第K个最大元素。 1A算法：读入N个元素放入数组， 并将其选择排序，返回适当的元素。 运行时间：O( N2 ) 1B算法: 1) 将K个元素读入数组， 并对其排序（按递减次序）。 最小者在第K个位置上。 2) 一个一个地处理其余元素： 每读入一个元素与数组中第K个元素(在K个元素中为最小)比较， 如果 , 则删除第K个元素，再将该元素放在合适的位置上。 如果 , 则舍弃。 最后在数组K位置上的就是第K个最大元素。 例如：3, 5, 8, 9, 1, 10 找第3个最大元素。 6.4.Applications of Priority Queues 运行时间(1B 算法)： O( K2 + ( N - K)*K ) = O( N*K ) 当 K = ? N / 2 ? , O( N2 ) 试验： 在 N = 100 万个元素中， 找第 500,000 个最大元素。 以上两个算法在合理时间内均不能结束, 都要处理若干天才算完. 用堆来实现： 6A算法：假设求第K个最小元素 1）将N个元素建堆（最小） O( N ) 2) 执行K次delete O( K*logN ) O( N + K * log N ) 如果 K = ?N / 2? ， ?( N * log N ) 如果 K = N ， O( N * log N ) 堆排序 6.4.Applications of Priority Queues 6B算法：假设求第K个最大元素 1）读入前K个元素， 建立最小堆 O( K ) 2) 其余元素一