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