HeapSort

2019-09-15
  • 最大堆实现
    • 代码

      #!/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,?0,?-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[start]?=?array[start],?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,?0,?-1):

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

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

      ????return?array

      def?main():

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

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

      ????print(array)

      if?__name__?==?‘__main__‘:

      ????main()

      ? ?

? ?

? ?

? ?