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
 
# 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, @z, @u = array, array.size, is_unordered
    return if @a.empty? || !heapify
    i = 1 << Math.log(@z, 2).floor
    sink i while (i -= 1) >= 0
end

Instance Method Details

#<<(x) ⇒ Object 



18
19
20
21
22
23
24
25
26
27
 
# File 'lib/ordered_ds.rb', line 18

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty? = @z == 0

#pop ⇒ Object 



29
30
31
32
33
34
 
# File 'lib/ordered_ds.rb', line 29

def pop
    return nil unless r = top
    @a[0] = @a[@z -= 1]
    sink 0
    r
end

#size ⇒ Object 



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

def size = @z

#top ⇒ Object 



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

def top = @z > 0 ? @a.first : nil