ac-library-rb で解く AtCoder 優先度付きキュー(Priority Queue)

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

# 今回のお題
*[AtCoder Beginner Contest D - Powerful Discount Tickets](https://atcoder.jp/contests/abc141/tasks/abc141_d)*
<font color="green">Difficulty: 826</font>

*[AtCoder CODE FESTIVAL 2016 qual C B - K個のケーキ](https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b)*
<font color="green">Difficulty: 905</font>

今回のテーマ、優先度付きキュー

*[ac-library-rb](https://github.com/universato/ac-library-rb)* は、AtCoder Library (ACL)のRuby版です。

今回はその中の`優先度付きキュー(Priority Queue)`を使用しています。
`Java`や`Python`ですと標準ライブラリに優先度付きキューがありますが、`Ruby`にはないので待望のライブラリです。
# D - Powerful Discount Tickets
```ruby.rb
# frozen_string_literal: true

# Priority Queue
# Reference: https://github.com/python/cpython/blob/master/Lib/heapq.py
class PriorityQueue
  # By default, the priority queue returns the maximum element first.
  # If a block is given, the priority between the elements is determined with it.
  # For example, the following block is given, the priority queue returns the minimum element first.
  # `PriorityQueue.new { |x, y| x < y }`
  #
  # A heap is an array for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.
  def initialize(array = [], &comp)
    @heap = array
    @comp = comp || proc { |x, y| x > y }
    heapify
  end

  attr_reader :heap

  # Push new element to the heap.
  def push(item)
    shift_down(0, @heap.push(item).size - 1)
  end

  alias << push
  alias append push

  # Pop the element with the highest priority.
  def pop
    latest = @heap.pop
    return latest if empty?

    ret_item = heap[0]
    heap[0] = latest
    shift_up(0)
    ret_item
  end

  # Get the element with the highest priority.
  def get
    @heap[0]
  end

  alias top get

  # Returns true if the heap is empty.
  def empty?
    @heap.empty?
  end

  private

  def heapify
    (@heap.size / 2 - 1).downto(0) { |i| shift_up(i) }
  end

  def shift_up(pos)
    end_pos = @heap.size
    start_pos = pos
    new_item = @heap[pos]
    left_child_pos = 2 * pos + 1

    while left_child_pos < end_pos
      right_child_pos = left_child_pos + 1
      if right_child_pos < end_pos && @comp.call(@heap[right_child_pos], @heap[left_child_pos])
        left_child_pos = right_child_pos
      end
      # Move the higher priority child up.
      @heap[pos] = @heap[left_child_pos]
      pos = left_child_pos
      left_child_pos = 2 * pos + 1
    end
    @heap[pos] = new_item
    shift_down(start_pos, pos)
  end

  def shift_down(star_pos, pos)
    new_item = @heap[pos]
    while pos > star_pos
      parent_pos = (pos - 1) >> 1
      parent = @heap[parent_pos]
      break if @comp.call(parent, new_item)

      @heap[pos] = parent
      pos = parent_pos
    end
    @heap[pos] = new_item
  end
end

HeapQueue = PriorityQueue

n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

h = PriorityQueue.new(a)
m.times do
  x = h.pop
  h.push(x / 2)
end
puts h.heap.sum
```
# B - K個のケーキ
```ruby.rb
# frozen_string_literal: true

# Priority Queue
# Reference: https://github.com/python/cpython/blob/master/Lib/heapq.py
class PriorityQueue
  # By default, the priority queue returns the maximum element first.
  # If a block is given, the priority between the elements is determined with it.
  # For example, the following block is given, the priority queue returns the minimum element first.
  # `PriorityQueue.new { |x, y| x < y }`
  #
  # A heap is an array for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0.
  def initialize(array = [], &comp)
    @heap = array
    @comp = comp || proc { |x, y| x > y }
    heapify
  end

  attr_reader :heap

  # Push new element to the heap.
  def push(item)
    shift_down(0, @heap.push(item).size - 1)
  end

  alias << push
  alias append push

  # Pop the element with the highest priority.
  def pop
    latest = @heap.pop
    return latest if empty?

    ret_item = heap[0]
    heap[0] = latest
    shift_up(0)
    ret_item
  end

  # Get the element with the highest priority.
  def get
    @heap[0]
  end

  alias top get

  # Returns true if the heap is empty.
  def empty?
    @heap.empty?
  end

  private

  def heapify
    (@heap.size / 2 - 1).downto(0) { |i| shift_up(i) }
  end

  def shift_up(pos)
    end_pos = @heap.size
    start_pos = pos
    new_item = @heap[pos]
    left_child_pos = 2 * pos + 1

    while left_child_pos < end_pos
      right_child_pos = left_child_pos + 1
      if right_child_pos < end_pos && @comp.call(@heap[right_child_pos], @heap[left_child_pos])
        left_child_pos = right_child_pos
      end
      # Move the higher priority child up.
      @heap[pos] = @heap[left_child_pos]
      pos = left_child_pos
      left_child_pos = 2 * pos + 1
    end
    @heap[pos] = new_item
    shift_down(start_pos, pos)
  end

  def shift_down(star_pos, pos)
    new_item = @heap[pos]
    while pos > star_pos
      parent_pos = (pos - 1) >> 1
      parent = @heap[parent_pos]
      break if @comp.call(parent, new_item)

      @heap[pos] = parent
      pos = parent_pos
    end
    @heap[pos] = new_item
  end
end

HeapQueue = PriorityQueue

gets
a = gets.split.map(&:to_i)

h = PriorityQueue.new(a)

while h.heap.size > 1
  u = h.pop
  v = h.pop
  h.push(u - 1) if u - 1 > 0
  h.push(v - 1) if v - 1 > 0
end
if h.heap.size.zero?
  puts 0
else
  puts h.pop - 1
end
```
`D - Powerful Discount Tickets`は、実行時間が 880 -> 395 msと速くなっていい感じですね。
# まとめ
+ 優先度付きキュー(Priority Queue) を解いた
+ ACL に詳しくなった
+ Ruby に詳しくなった

参照したサイト
*[ac-library-rb - GitHub](https://github.com/universato/ac-library-rb)*
*[Ruby と Python と Java で解く AtCoder ABC141 D 優先度付きキュー](https://qiita.com/superrino130/items/a4795aa0d03090f06d8d)*
*[Ruby と Python で解く AtCoder CODE FESTIVAL 2016 qual C B 優先度付きキュー](https://qiita.com/superrino130/items/6c8d56203ff4379f5267)*