NAME

SkewHeap - A fast heap structure for Perl

VERSION

version 0.01

SYNOPSIS

  use SkewHeap;

  my $heap = SkewHeap->new(sub{ $a <=> $b });
  $heap->put(42);
  $heap->put(35);
  $heap->put(200);
  $heap->put(62);

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

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

  $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 (using Inline::C).

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

METHODS

new

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 a new element into the heap.

take

Removes and returns the next element from the heap.

merge

Destructively merges another heap into itself. After calling merge, the second heap is empty and the first holds all elements from both heaps.

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.