#! perl -slw
use strict;
use List::Util qw[ shuffle ];

use Inline C => 'DATA';

$^W = 0;
 
my $max = 120;
my @values = 1 .. $max;
my @values_mixed = shuffle(@values);
my @top = topNbs(20, sub { $a <=> $b }, \@values_mixed);
print "@top";
 
__END__
__C__

int callComp( SV* cmp, SV* a, SV* b ) {
	dSP;
	int rv;
	ENTER; 
	SAVETMPS; 

	GvSV(gv_fetchpv("a", TRUE, SVt_PV)) = a;
	GvSV(gv_fetchpv("b", TRUE, SVt_PV)) = b;
	
	PUSHMARK(SP);

	if( call_sv( cmp, G_SCALAR|G_NOARGS ) != 1 )
		croak( "Bad comparator" );
	SPAGAIN;

	rv = POPi;

	PUTBACK; // << Was missing and is required!
	FREETMPS;LEAVE;
	return rv;
}
 
void topNbs( int n, SV *cmp, AV*data) {
    SV* *topN;
    int len = av_len( data );
    int i, j, k;
    int left, right;
    Inline_Stack_Vars;
    Newz( 1, topN, n + 1, SV* );
 
    for (i = 0; i < n+1; i++) {
       topN[i] = newSViv( 0 );
    }
 
    for( i = 0; i <= len; i++ ) {
        SV *val = *av_fetch( data, i, 0 );
        if (callComp(cmp, val, topN[ n - 1]) < 0) continue;
 
        left = 0;
        right = n - 1;
        while (left < right) {
           int middle = (left + right) >> 1;
           if (callComp(cmp, val, topN[ middle ]) <= 0) {
              left = middle + 1;
           } else {
              right = middle;
           }
        }
	for( k = n; k > left; k-- ) topN[ k ] = topN[ k-1 ];
	topN[ left ] = val;
    }
 
    Inline_Stack_Reset;
    for( i = 0; i < n; i++ )
        Inline_Stack_Push( sv_2mortal( newSVsv( topN[ i ] ) ) );
    Safefree( topN );
    Inline_Stack_Done;
}

##</code><code>##

#! perl -slw
use strict;
use List::Util qw[ shuffle ];

use Inline C => 'DATA';

$^W = 0;
 
my $max = 120;
my @values = 1 .. $max;
my @values_mixed = shuffle(@values);
my @top = topNheap(20, sub { $a <=> $b }, \@values_mixed);
print join(" ", sort { $a <=> $b } @top),"\n";
 
__END__
__C__

int callComp( SV* cmp, SV* a, SV* b ) {
	dSP;
	int rv;
	ENTER; 
	SAVETMPS; 

	GvSV(gv_fetchpv("a", TRUE, SVt_PV)) = a;
	GvSV(gv_fetchpv("b", TRUE, SVt_PV)) = b;
	
	PUSHMARK(SP);

	if( call_sv( cmp, G_SCALAR|G_NOARGS ) != 1 )
		croak( "Bad comparator" );
	SPAGAIN;

	rv = POPi;

	PUTBACK; // << Was missing and is required!
	FREETMPS;LEAVE;
	return rv;
}
 
// Note: code adapted from web page:
// http://www.dgp.utoronto.ca/~mjmcguff/courses/csc191/02s/topic06.trees/notes29_heaps

#define left_child(i) (2*(i)+1)
#define right_child(i) (2*(i)+2)
#define parent(i) floor(((i)-1)/2)

// A is an array storing a complete binary tree of n nodes.  
// This routine will heapify the subtree rooted at i.
void heapify(SV *cmp, SV** A, int n, int i) {
  int smallest = i;
  int left = left_child(i);
  if ( left < n && callComp(cmp, A[left], A[smallest]) < 0 )
    smallest = left;
  int right = right_child(i);
  if ( right < n && callComp(cmp, A[right], A[smallest]) < 0 )
    smallest = right;
  if ( smallest != i ) {
    // The node i needs to be floated down
    SV * temp = A[ i ];
    A[ i ] = A[ smallest ];
    A[ smallest ]  = temp;
    // Now smallest is the root of the subtree
    // that needs to be fixed up.
    heapify(cmp, A, n, smallest );
  }
}

void buildHeap(SV *cmp, SV** A, int n ) {
   int i;
   for ( i = parent(n-1); i >= 0; --i )
      heapify(cmp, A, n, i );
}

void topNheap( int n, SV *cmp, AV*data) {
    SV* *topN;
    int len = av_len( data );
    int i, k, pk;
    int in_parent = parent(n);
    Inline_Stack_Vars;
    Newz( 1, topN, n + 1, SV* );

    // Preload the first n items.
    for (i = 0; i < n; i++) {
       topN[i] = *av_fetch( data, i, 0 );
    }
    buildHeap(cmp, topN, n);

    // For each of the rest, add to the heap and remove
    // from the heap to maintain the same size.
    // The heap is arranged so the minimum is at the top.
    for( i = n; i <= len; i++ ) {
       SV *val = *av_fetch( data, i, 0 );
       if (callComp(cmp, val, topN[0]) < 0) continue;
 
       // Add the new value to the heap.
       k = n;
       pk = in_parent;
       while ( k > 0 && callComp(cmp, topN[pk], val) > 0) {
	  topN[ k ] = topN[ pk ];
	  k = pk;
	  if (k > 0) pk = parent(k);
       }
       topN[k] = val;

       // Take the lowest value off the top.
       topN[0] = topN[n];
       heapify(cmp, topN, n, 0 );
    }
 
    Inline_Stack_Reset;
    for( i = 0; i < n; i++ )
        Inline_Stack_Push( sv_2mortal( newSVsv( topN[ i ] ) ) );
    Safefree( topN );
    Inline_Stack_Done;
}