【Ruby】Max Heap

https://pixabay.com/photos/tulips-tulip-field-netherlands-5104497/

Leetcode 2530，給予一串陣列及一個整數 K，找出陣列中最大的數字除以三，反覆操作 K 次之後回傳最大的數字。

題目雖然看起來很簡單，但因為數字除以三後不見得還是陣列中最大的數字，要和其他數字再比一次大小，重新挑出最大數字操作，如此反覆排序，當陣列的數量很大的時候就會超過時間失敗，即使是排序後再用 bsearch 處理也一樣，所以這題要使用 Max Heap 操作。

Max Heap 的特性就是可以在 lon(n) 的時間複雜度下完成排序，同時，因為最大的數字就在 Heap 的第一個位置，因此也可以在 O(1) 就取出最大值；只是 Ruby 本身沒有附相關功能，所以要自己實作一個 Max Heap 出來：

# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def max_kelements(nums, k)
    max = MaxHeap.new
    nums.each { |num| max.insert(num) }
    result = 0
    for i in(1).upto(k)
        target = max.pop
        result += target
        target = (target + 2) / 3
        max.insert(target)
    end
    result
end

class MaxHeap
  def initialize
    @heap = []
  end

  def insert(target)
    @heap << target
    switch_up(@heap.size - 1)
  end

  def pop
    return if @heap.empty?

    switch(0, @heap.size - 1)
    target = @heap.pop
    switch_down(0)
    target
  end

  private

  def switch_up(index)
    while index > 0
      parent = (index - 1) / 2
      break if @heap[parent] >= @heap[index]

      switch(index, parent)
      index = parent
    end
  end

  def switch_down(index)
    size = @heap.size
    while index * 2 + 1 < size
      left = index * 2 + 1
      right = left + 1

      # Determine the largest child
      largest = left
      if right < size && @heap[right] > @heap[left]
        largest = right
      end

      break if @heap[index] >= @heap[largest]

      switch(index, largest)
      index = largest
    end
  end

  def switch(before, after)
    @heap[before], @heap[after] = @heap[after], @heap[before]
  end
end

雖然上網查了不少資料，又失敗了很多次才弄出來，不過看到通過還蠻有成就感的，順便紀錄一下 Max Heap 的學習過程。