NAME

SkewHeap::PP - a fast and flexible heap structure

VERSION

version 0.02

SYNOPSIS

  use SkewHeap::PP;

  my $s = skew{ $_[0] <=> $_[1] };

  # Add items one at a time
  for (@items) {
    skew_put($s, $_);
  }

  # Or as a batch
  skew_put($s, @items);

  # Take individual items
  my @taken;
  until (skew_is_empty($s)) {
    say "Taking: " . skew_peek($s);

    push @taken, skew_take($s);

    say "Left in queue: " . skew_count($s);
  }

  # Or take a batch
  my @take_ten = skew_take($s, 10);

  # Destructively merge two heaps
  skew_merge($s, $another_skew_heap);

  # Non-destructively merge heaps
  my $new_heap = skew_merge($a, $b, $c);

DESCRIPTION

A skew heap is a memory efficient, self-adjusting heap with an amortized performance of O(log n) or better. SkewHeap:PP is implemented in pure perl, yet performs comparably to SkewHeap.

The key feature of a skew heap is the ability to quickly and efficiently merge two heaps together.

skew

Creates a new skew heap. Requires a single argument, a code block that knows how to prioritize the values to be stored in the heap.

  my $heap = skew{ $_[0] <=> $_[1] };

skew_count

Returns the number of elements in the heap.

skew_is_empty

Returns true if the heap is empty.

skew_peek

Returns the top element in the heap without removing it from the heap.

skew_take

Removes and returns the top element from the heap.

  my $item = skew_take($heap);

Optionally, multiple elements may be returned from the heap by passing the desired number of elements, in which case a list is returned, rather than a single, scalar element. If there are fewer elements available than requested, as many as a immediately available are returned.

  # Get 10 elements
  my @items = skew_take($heap, 10);

skew_put

Adds one or more items to the heap.

  skew_put($s, 42);
  skew_put($s, 42, 6, 8);

skew_merge

Merges any number of heaps into the first argument destructively. After merging, the first heap passed in will contain all of the items in the heaps passed in subsequent arguments. After merging, the subsequent heaps will be empty. The comparison function used for ordering is that of the first heap passed in. The return value is the first heap into which the other heaps were merged.

  skew_merge($x, $y, $z); # $x contains all elements of $x, $y, and $z;
                          # $y and $z are now empty.

skew_merge_safe

Non-destructively merges any number of heaps into a new heap whose comparison function will be that of the first heap in the list to merge. Returns a new heap containing all of the items in each of the other heaps. The other heaps' contents will remain intact.

skew_explain

Prints out a representation of the internal tree structure for debugging.

OBJECT INTERFACE

An object interface is provided that maps directly to the similarly named skew_* routines.

new - SEE "skew"

count - SEE "skew_count"

is_empty - SEE "skew_is_empty"

peek - SEE "skew_peek"

take - SEE "skew_take"

put - SEE "skew_put"

merge - SEE "skew_merge"

merge_safe - SEE "skew_merge_safe"

explain = SEE "skew_explain"

SEE ALSO

SkewHeap

Written in XS and roughly 2x faster.

https://en.wikipedia.org/wiki/Skew_heap

AUTHOR

Jeff Ober <sysread@fastmail.fm>

COPYRIGHT AND LICENSE

This software is copyright (c) 2020 by Jeff Ober.

This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.

cpanm SkewHeap::PP

perl -MCPAN -e shell
install SkewHeap::PP