Treap

Treap — tree + heap == treap

A randomized binary tree using random priorities in heap order to maintain a probabilistically balanced tree.

Synopsis

  require 'treap'
  tree = Treap.new
  i = 0
  %w- f w a q b c l r d -.each {|k| tree.insert(k, i += 1)}
  tree.each_pair {|k,v| print "<#{k}:#{v}>"}
  print "\n"
  __END__

  <a:3><b:5><c:6><d:9><f:1><l:7><q:4><r:8><w:2>

Requirements:

Ruby 1.8+

Install

  ruby setup.rb config
  ruby setup.rb install

  ruby setup.rb --help  # for installation help

Licence

Licensed under the same terms as Ruby. Copyright © 2005, Andrew L Johnson