Class: Pque

Inherits:
Array
  • Object
show all
Defined in:
lib/pque.rb,
lib/pque/version.rb

Constant Summary collapse

VERSION = 
"0.1.05"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(o = true) ⇒ Pque

Returns a new instance of Pque.



5
6
7
8
 
# File 'lib/pque.rb', line 5

def initialize(o = true)
  @pushcomp = o ? lambda{|a,b| a >= b} : lambda{|a,b| a <= b}
  @popcomp  = o ? lambda{|a,b| a > b } : lambda{|a,b| a < b }
end

Instance Attribute Details

#popcomp ⇒ Object

Returns the value of attribute popcomp.



4
5
6
 
# File 'lib/pque.rb', line 4

def popcomp
  @popcomp
end

#pushcomp ⇒ Object

Returns the value of attribute pushcomp.



4
5
6
 
# File 'lib/pque.rb', line 4

def pushcomp
  @pushcomp
end

Instance Method Details

#pop ⇒ Object 



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/pque.rb', line 28

def pop
  # 最大（小）値
  ret = self[0]
  #根に持ってくる値
  x = self[-1]
  # 根から下ろしていく
  i= 0
  while i * 2 + 1 < size - 1
    # 子同士を比較
    child1 = i * 2 + 1; child2 = i * 2 + 2
    child1 = child2 if child2 < self.size &&
      popcomp.call(self[child2], self[child1])# ヒープの不等号で順序が逆に
    # もう逆転してないなら終わり
    break if self[child1] <= x
    # この数字を持ち上げる
    self[i] = self[child1]
    i = child1
  end
  self[i] = x
  self.delete_at(-1)
  ret
end

#push(x) ⇒ Object 



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/pque.rb', line 10

def push(x)

  # 自分のノードの番号
  i = size
  while i > 0
    # 親のノードの番号
    p = (i - 1) / 2 #i = p*2 + 1
    # もう逆転してないなら抜け
    unless self[p].nil?
      break if pushcomp.call(self[p], x) # ヒープの不等号で順序が逆に
    end
    # 親のノードの数字を下ろして、自分は上に
    self[i] =self[p]
    i = p
  end
  self[i] = x
end