72 lines
1.1 KiB
Crystal
72 lines
1.1 KiB
Crystal
class Heap (T)
|
|
@heap : Array(T)
|
|
|
|
def initialize (source : Array(T) = [] of T)
|
|
@heap = source.dup
|
|
heapify
|
|
end
|
|
|
|
def << (item)
|
|
@heap << item
|
|
siftup @heap.size - 1
|
|
self
|
|
end
|
|
|
|
def push (item)
|
|
self << item
|
|
end
|
|
|
|
def shift
|
|
new_head = @heap.pop
|
|
return new_head if @heap.empty?
|
|
result = @heap[0]
|
|
@heap[0] = new_head
|
|
siftdown 0
|
|
result
|
|
end
|
|
|
|
def empty?
|
|
@heap.empty?
|
|
end
|
|
|
|
def to_s (io)
|
|
io << "Heap"
|
|
@heap.to_s io
|
|
end
|
|
|
|
private def heapify
|
|
(@heap.size//2 - 1).downto(0) do |i|
|
|
siftdown i
|
|
end
|
|
end
|
|
|
|
private def siftdown (i)
|
|
n = @heap.size
|
|
loop do
|
|
j = i*2 + 1
|
|
return if j >= n
|
|
j += 1 if j+1 < n && @heap[j+1] < @heap[j]
|
|
return if @heap[i] <= @heap[j]
|
|
@heap.swap i, j
|
|
i = j
|
|
end
|
|
end
|
|
|
|
private def siftup (i)
|
|
loop do
|
|
j = (i-1)//2
|
|
break unless j >= 0 && @heap[i] < @heap[j]
|
|
@heap.swap i, j
|
|
i = j
|
|
end
|
|
end
|
|
end
|
|
|
|
tasks = [{3, "Clear drains"}, {4, "Feed cat"}, {5, "Make tea"},
|
|
{1, "Solve RC tasks"}, {2, "Tax return"}]
|
|
|
|
heap = Heap.new tasks
|
|
|
|
while !heap.empty?
|
|
puts heap.shift
|
|
end
|