https://pixabay.com/photos/tulips-tulip-field-netherlands-5104497/
Leetcode 2530, дається масив та ціле число K, потрібно знайти найбільше число в масиві, поділити його на три, і повторювати цю операцію K разів, після чого повернути найбільше число.
Задача хоча й здається простою, але після ділення числа на три, воно не обов’язково залишатиметься найбільшим в масиві. Потрібно знову порівняти його з іншими числами та вибрати нове максимальне число, повторюючи операцію. Коли масив дуже великий, можуть виникнути проблеми з часом виконання, навіть якщо після сортування використовувати бінарний пошук (bsearch), тому для цієї задачі необхідно використовувати Max Heap.
Особливість Max Heap в тому, що можна виконувати сортування за час O(log(n)), а оскільки найбільше число знаходиться на першій позиції в Heap, його можна забрати за O(1). Проте в Ruby немає вбудованої підтримки цієї структури даних, тому її доводиться реалізовувати самому:
# @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 запам’ятається надовго.
Перекладено з: 【Ruby】Max Heap