class PriorityQueue
def initialize()
@heap_size = 0
@heap_tail = 0
@heap_data = [0]
end
def empty
@heap_tail == 0
end
def size
@heap_size
end
def push(value)
@heap_tail += 1
@heap_data[@heap_tail] = value
f = @heap_tail
#把新插入的节点往上提
while f != 1 && value > @heap_data[f>>1] #可以向上去
@heap_data[f] = @heap_data[f>>1]
@heap_data[f>>1] = value
f >>= 1
end
end
def top
@heap_data[1] #最大元素在顶端
end
def pop
@heap_data[1] = @heap_data[@heap_tail]
f = 1
tmp = @heap_data[@heap_tail]
@heap_tail -= 1
while (f << 1) <= @heap_tail
d = @heap_data[f<<1] - @heap_data[f<<1|1]
#左右节点都比自己小，终止循环
if d > 0
break if @heap_data[f<<1] <= tmp
else
break if @heap_data[f<<1|1] <= tmp
end
if d > 0 #左孩子大就与左孩子交换，否则和右孩子交换
@heap_data[f] = @heap_data[f<<1]
@heap_data[f<<1] = tmp
f <<= 1
else
@heap_data[f] = @heap_data[f<<1|1]
@heap_data[f<<1|1] = tmp
f = f<<1|1
end
end
end
end
#test
q = PriorityQueue.new
gets.split.map{|e| e.to_i}.each {|e| q.push(e)}
while !q.empty
puts q.top
q.pop
end