NAME

SkewHeap - A fast and flexible heap structure

SYNOPSIS

  use SkewHeap;

  my $heap = skewheap{ $a <=> $b };
  $heap->put(42);
  $heap->put(35);
  $heap->put(200, 62);

  $heap->top;  # 35
  $heap->size; # 4

  $heap->take; # 35
  $heap->take; # 42
  $heap->take; # 62
  $heap->take; # 200

  my $merged_heap = $heap->merge($other_skewheap);

DESCRIPTION

A skew heap is a memory efficient, self-adjusting heap (or priority queue) with an amortized performance of O(log n) (or better). SkewHeap is implemented in C/XS.

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

METHODS

skewheap

Creates a new SkewHeap which will be sorted in ascending order using the comparison subroutine passed in. This sub has the same semantics as Perl's sort, returning -1 if $a < $b, 1 if $a > $b, or 0 if $a == $b.

size

Returns the number of elements in the heap.

top

Returns the next element which would be returned by "take" without removing it from the heap.

put

Inserts one or more new elements into the heap.

take

Removes and returns the next element from the heap.

merge

Non-destructively merges two heaps into a new heap. Returns the new heap.

AUTHOR

Jeff Ober <sysread@fastmail.fm>

COPYRIGHT AND LICENSE

This software is copyright (c) 2018 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.