# Extending standard library by priority queue or search tree

**URL:** <https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109>\
**Category:** Ruby\
**Created:** [September 9, 2008, 12:33pm UTC](https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109 "2008-09-09T12:33:54Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Artem\_V](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/3be4f8/32.png) [@Artem\_V](https://www.ruby-forum.com/u/Artem_V)\
**Post date:** [September 9, 2008, 12:33pm UTC](https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109/1 "2008-09-09T12:33:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Artem\_V](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/3be4f8/32.png) [@Artem\_V](https://www.ruby-forum.com/u/Artem_V)\
**Post date:** [September 9, 2008, 2:39pm UTC](https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109/2 "2008-09-09T14:39:39Z")

</div>

2008/9/9 Artem V. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> extract\_max\_by\_key()  
> 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.

> 1. adding new class PriorityQueue to standard library
> 2. 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](http://raa.ruby-lang.org/search.rhtml?search=rbtree)

See also

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

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![Artem\_V](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/3be4f8/32.png) [@Artem\_V](https://www.ruby-forum.com/u/Artem_V)\
**Post date:** [September 9, 2008, 8:52pm UTC](https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109/3 "2008-09-09T20:52:55Z")

</div>

Robert K. wrote:

> 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](http://raa.ruby-lang.org/search.rhtml?search=rbtree)

Also: gem install rbtree

Using rbtree, a priority queue is simple:

require ‘rbtree’

class PriorityQueue  
def initialize  
@tree = MultiRBTree.new  
@mutex = Mutex.new  
@cond = ConditionVariable.new  
end

# Push +obj+ with priority equal to +pri+ if given or, otherwise,

# the result of sending #queue\_priority to +obj+. Objects are

# dequeued in priority order, and first-in-first-out among objects

# with equal priorities.

def push(obj, pri = obj.queue\_priority)  
@mutex.synchronize do  
@tree.store(pri, obj)  
@cond.signal  
end  
end

def pop(non\_block=false)  
@mutex.synchronize do  
if (last=@tree.last)  
return @tree.delete(last[0]) # highest key, oldest first  
end

```
   if non_block
     raise ThreadError, "priority queue empty"
   end

   loop do
     @cond.wait(@mutex)
     if (last=@tree.last)
       return @tree.delete(last[0])
     end
   end
 end

```

end  
end

pq = PriorityQueue.new  
pq.push “a”, 1  
pq.push “c”, 3  
pq.push “b”, 2  
p pq.pop

---

<div class="post-metadata">

**Author:** ![Artem\_V](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/3be4f8/32.png) [@Artem\_V](https://www.ruby-forum.com/u/Artem_V)\
**Post date:** [September 9, 2008, 10:42pm UTC](https://www.ruby-forum.com/t/extending-standard-library-by-priority-queue-or-search-tree/148109/4 "2008-09-09T22:42:02Z")

</div>

Thank you all!

2008/9/9 Joel VanderWerf [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):