Re: finding local minima/maxima for a discrete array

[Anno]

...need to find the top k local maxima

ysth has shown a nice method to find local maxima in an array. I'd like to add that it isn't necessary to store (and sort) all maxima if only the top $k are needed. A heap data structure minimizes both time- and space requirements of the task.

Assuming a mythical Heap class with methods new, insert, extract_min, and size, create a heap

my $heap = Heap->new;

and then for each new local maximum $max:

$heap->insert( $max);
$heap->extract_min if $heap->size > $k;

(This step can be optimized a little more.)

After all are done,

map $heap->extract_min, 1 .. $heap->size;

returns the top $k maxima (or as many as there are) in ascending order.

CPAN has a couple of heap-implementations.

In practice, quite often the expense of storing and sorting the full array is irrelevant, so the heap solution isn't often implemented. I still like to point out the alternative whenever a "top $k" problem comes up.

Anno