最大堆实现 代码
#!/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()
? ?
? ?
? ?
? ?