From: Robert Klemme <shortcutter@...>
Date: 2008-09-09T21:32:53+09:00
Subject: Re: Extending standard library by priority queue or search tree

2008/9/9 Artem Voroztsov <artem.voroztsov@gmail.com>:
> I'd like to have guide for C++ programmers who wants to learn Ruby.
> This guide should explain how to do things in Ruby they used to do in C++, STL.
>
> STL has container map which allows us to do the following
>  insert(key,value)
>  find_by_key(key)
>  delete_by_key(key)
>  min_by_key()
>  max_by_key()
>  extract_min_by_key()
>  extract_max_by_key()
>
> running O(log N) each (N - number of elements in container)
>
> So map could acts as associative array, and as priority queue as well.
>
> Simple use case: find M most frequent words in big text of size N in
> time O( N * log(M) ) or faster.
>
> I don't know how to solve this problem in Ruby using only standard
> classes and not using gems (PriorityQueue) and not writing data
> structures (RB-trees, or binary heap, or ..) by myself.
>
> Is it possible?
>
> What do you think about
> 1) implementing Hash as RB-tree and adding methods :first and :last
> returning min and max pair by key

Bad idea since this will change the character of Hash completely -
also, it's no longer a Hash then.

> 2) adding new class PriorityQueue to standard library
> 3) adding new class SearchTree to standard library, which allows to do
> all that map does

Rather put an RBTree into the std lib.  Note that such a thing does
exist already:

http://raa.ruby-lang.org/search.rhtml?search=rbtree

See also

http://raa.ruby-lang.org/search.rhtml?search=binary%20search

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end