Class: PQ

Inherits:
Object
  • Object
show all
Defined in:
lib/ordered_ds.rb

Direct Known Subclasses

MaxQ, MinQ

Instance Method Summary collapse

Constructor Details

#initialize(array = [], heapify = true, &is_unordered) ⇒ PQ

Returns a new instance of PQ.



3
4
5
6
7
8
9
10
11
12
 
# File 'lib/ordered_ds.rb', line 3

def initialize array = [], heapify = true, &is_unordered
    raise ArgumentError.new 'PQ init' unless
        array.class == Array &&
        (heapify == true || heapify == false) &&
        block_given?
    @a, @u = array, is_unordered
    return unless heapify
    i = @a.size / 2
    sink i while (i -= 1) >= 0
end

Instance Method Details

#<<(x) ⇒ Object 



25
26
27
28
29
30
31
32
33
34
35
 
# File 'lib/ordered_ds.rb', line 25

def << x
    i = @a.size
    @a << x
    while i > 0
        p = (i - 1) / 2
        break unless @u.call @a[p], @a[i]
        @a[p], @a[i] = @a[i], @a[p]
        i = p
    end
    self
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


15
 
# File 'lib/ordered_ds.rb', line 15

def empty? = @a.empty?

#pop ⇒ Object 



37
38
39
40
41
42
 
# File 'lib/ordered_ds.rb', line 37

def pop
    return @a.pop if @a.size < 2
    t, @a[0] = @a.first, @a.pop
    sink 0
    t
end

#pop_push(x) ⇒ Object 



19
20
21
22
23
 
# File 'lib/ordered_ds.rb', line 19

def pop_push x
    t, @a[0], = @a.first, x
    sink 0
    t
end

#push_pop(x) ⇒ Object 



17
 
# File 'lib/ordered_ds.rb', line 17

def push_pop(x) = !@a.empty? && @u.(x, @a.first) ? pop_push(x) : x

#size ⇒ Object 



14
 
# File 'lib/ordered_ds.rb', line 14

def size = @a.size

#top ⇒ Object 



16
 
# File 'lib/ordered_ds.rb', line 16

def top = @a.first