binary_heap.coffee

gistfile1.coffee

class BinaryHeap
  constructor: ->
    @array = []
    @rootIndex = 1

  insert: (element) ->
    @array.push element
    @percolateUp @lastLeafIndex()

  deleteMaximum: ->
    first = @array.shift()
    @swap @lastLeafIndex(), @rootIndex
    @percolateDown @rootIndex
    first

  lastLeafIndex: -> @array.length

  getMaximum: -> @getRoot()

  getRoot: -> @array[0]

  getNode: (index) -> @array[index - 1] || null

  setNode: (index, element) -> @array[index - 1] = element

  getParentIndex: (index) -> Math.round index / 2

  getLeftChildIndex: (index) ->
    i = index * 2
    if i > @lastLeafIndex() then null else i

  getRightChildIndex: (index) ->
    i = index * 2 + 1
    if i > @lastLeafIndex() then null else i

  getBiggerChildIndex: (index) ->
    leftChildIndex = @getLeftChildIndex index
    rightChildIndex = @getRightChildIndex index

    return if @getNode leftChildIndex > @getNode rightChildIndex then leftChildIndex else rightChildIndex

  percolateUp: (startIndex) ->
    currentIndex = startIndex

    while currentIndex > @rootIndex
      parentIndex = @getParentIndex currentIndex
      parent = @getNode parentIndex
      current = @getNode currentIndex

      @swap currentIndex, parentIndex if parent < current
      currentIndex = parentIndex

  percolateDown: (startIndex) ->
    currentIndex = startIndex

    while currentIndex < @lastLeafIndex()
      childIndex = @getBiggerChildIndex currentIndex

      break if childIndex == null
      @swap currentIndex, childIndex if (@getNode currentIndex) < (@getNode childIndex)

      currentIndex = childIndex

  swap: (firstIndex, secondIndex) ->
    first = @getNode firstIndex
    second = @getNode secondIndex

    _first = first
    @setNode firstIndex, second
    @setNode secondIndex, _first

h = new BinaryHeap
h.insert 1
h.insert 10
h.insert 4
h.insert 2

console.log h.array
console.log h.deleteMaximum()
console.log h.array
h.insert 3
console.log h.array
console.log h.deleteMaximum()
console.log h.array
console.log h.deleteMaximum()
console.log h.array