Skip to content

Instantly share code, notes, and snippets.

@jithinabraham

jithinabraham/heap_sort.rb

Created July 4, 2016 19:36
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jithinabraham/f23652a8bc6ae6e7a6c31f5680da6bc8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jithinabraham/f23652a8bc6ae6e7a6c31f5680da6bc8 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jithinabraham created this gist Jul 4, 2016.
    52 changes: 52 additions & 0 deletions heap_sort.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,52 @@
    class HeapSort
    attr_accessor :input

    def initialize(arg)
    @input=arg
    end

    def heap_sort
    heapify
    the_end=input.length-1
    while the_end > 0
    input[the_end],input[0]=input[0],input[the_end]
    the_end-=1
    shift_down(0,the_end)
    end
    input
    end

    def heapify
    the_start=(input.length-2)/2

    while the_start >=0
    shift_down(the_start,input.length-1)
    the_start-=1
    end
    end

    def shift_down(the_start,the_end)
    root=the_start
    while root*2+1 <= the_end
    child=root*2+1
    swap=root

    if input[swap] < input[child]
    swap=child
    end

    if child+1 <= the_end && input[swap] < input[child+1]
    swap=child+1
    end

    if swap!=root
    input[root],input[swap]=input[swap],input[root]
    root=swap
    else
    return
    end

    end
    end

    end