From: Artem Voroztsov <artem.voroztsov@...>
Date: 2008-09-09T19:26:47+09:00
Subject: Extending standard library by priority queue or search tree

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
2) adding new class PriorityQueue to standard library
3) adding new class SearchTree to standard library, which allows to do
all that map does
?



Artem