Heapの実装

RubyでHeapのデータ構造を実装します。

class Heap

    def push(array,elem)
        n = array.size
        array << elem
        
        while n != 0
            i = (n-1) / 2
            if (array[n] - array[i]) > 0
                tmp      = array[n]
                array[n] = array[i]
                array[i] = tmp
            end
            n = i
        end

    end

    def pop(array)
        n = array.size.to_i - 1
        max_elem = array[0]
        array[0] = array.pop
        i = 0

        while  (j = (2 * i + 1)) < n
            if((j != n-1) && ((array[j] - array[j+1]) < 0))
                j += 1
            end
            if (array[i] - array[j]) < 0
                tmp      = array[j]
                array[j] = array[i]
                array[i] = tmp
            else
                break
            end
            i = j
        end
        
        return max_elem
    end

end

実行します。

heap = Heap.new()

test = []
heap.push(test,20)
heap.push(test,5)
heap.push(test,15)
heap.push(test,4)
heap.push(test,3)
heap.push(test,9)
heap.push(test,10)
heap.push(test,6)
puts heap.pop(test)
puts heap.pop(test)
puts heap.pop(test)
puts heap.pop(test)
puts heap.pop(test)
puts heap.pop(test)

実行結果です。

20
15
10
9
6
5
Complete(0)

下記のWebページを参考にさせていただきました。
優先度付き待ち行列

広告を非表示にする