HeapSort

• 最大堆实现
  • 代码

    #!/usr/bin/env?python

    #?-*-?coding:?utf-8?-*-

    ? ?

    #?单个叶子节点进行上浮调整位置

    def?float_up(array,?start):

    ????parent?=?(start?-?1)?//?2

    ????if?start?==?0:

    ????????return

    ????if?array[parent]?>=?array[start]:

    ????????return

    ????array[parent],?array[start]?=?array[start],?array[parent]

    ????float_up(array,?parent)

    #?不断的更新最后的叶子节点的下标从而确定最新的最后的叶子节点进行上浮

    def?heap(array,?length):

    ????for?start?in?range(length?-?1,?0,?-1):

    ????????float_up(array,?start)

    ????return?array

    ? ?

    #?得到最大堆之后交换顶点与末尾,?得到最后的排序

    def?heap_sort(array):

    ????array?=?heap(array,?len(array))

    ????for?start?in?range(len(array)?-?1,?-1):

    ????????array[start],?array[0]?=?array[0],?array[start]

    ????????array?=?heap(array,?start)

    ????return?array

    def?main():

    ????array?=?[6,?5,?2,?7,?3,?9,?8]

    ????print(heap_sort(array))

    ? ?

    if?__name__?==?‘__main__‘:

    ????main()

    ? ?

• 最小堆实现
  • 代码

    #!/usr/bin/env?python

    #?-*-?coding:?utf-8?-*-

    ? ?

    #?maxheapsort?是?float?up,?默认顶点就是?0,?但是?minheapsort?的最低部是长度,?且不是固定的,?因为在?sort?时会删除元素

    def?sink_down(array,?start,?length):

    ????left?=?start?*?2?+?1

    ????right?=?start?*?2?+?2

    ????if?left?>?length?-?1?or?right?>?length?-?1:

    ????????return

    ????tmp?=?start

    ????if?array[tmp]?>?array[left]:

    ????????tmp?=?left

    ????if?array[tmp]?>?array[right]:

    ????????tmp?=?right

    ????if?tmp?==?start:

    ????????return

    ????array[tmp],?array[tmp]

    ????sink_down(array,?tmp,?length)

    def?heap(array,?length):

    ????for?start?in?range(length):

    ????????sink_down(array,?start,?length)

    ????return?array

    def?heap_sort(array):

    ????array?=?heap(array,?len(array))

    ????for?i?in?range(len(array)?-?1,?-1):

    ????????array[0],?array[i]?=?array[i],?array[0]

    ????????array?=?heap(array,?i)

    ????return?array

    def?main():

    ????array?=?[6,?8]

    ????array?=?heap_sort(array)

    ????print(array)

    if?__name__?==?‘__main__‘:

    ????main()

    ? ?

? ?

? ?

? ?