SkewHeap::PP - a fast and flexible heap structure


version 0.01


  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);


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.


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] };


Returns the number of elements in the heap.


Returns true if the heap is empty.


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


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);


Adds one or more items to the heap.

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


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.


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.


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


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"



Built with XS, SkewHeap is between 50-100% faster than SkewHeap::PP for heaps with 100,000 or fewer elements. For large heaps, that drops down to roughly 50% slower that the pure perl solution.


Jeff Ober <>


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.