import random
def randomList(count:int=10) -> list:
'''return a random list with elements from 0 to count-1'''
return random.sample(range(count), count)
# Recursively. Θ(lgn)
def maxHeapify(array, arrayLength, fatherIndex):
'''Maintain the max-heap property from the fatherIndex-th element'''
largestIndex = fatherIndex
leftIndex = 2 * fatherIndex
rightIndex = leftIndex+1
# Keep indices lower than len of the array
if leftIndex<arrayLength and array[leftIndex]>array[largestIndex]:
largestIndex = leftIndex
if rightIndex<arrayLength and array[rightIndex]>array[largestIndex]:
largestIndex = rightIndex
if largestIndex != fatherIndex:
array[largestIndex], array[fatherIndex] = array[fatherIndex], array[largestIndex]
maxHeapify(array, arrayLength, largestIndex)
# Cyclically. Θ(lgn)
def maxHeapify(array, arrayLength, fatherIndex):
'''Maintain the max-heap property from the fatherIndex-th element'''
largestIndex = fatherIndex
while True:
leftIndex = 2 * fatherIndex
rightIndex = leftIndex+1
# Keep indices lower than len of the array
if leftIndex<arrayLength and array[leftIndex]>array[largestIndex]:
largestIndex = leftIndex
if rightIndex<arrayLength and array[rightIndex]>array[largestIndex]:
largestIndex = rightIndex
if largestIndex != fatherIndex:
array[largestIndex], array[fatherIndex] = array[fatherIndex], array[largestIndex]
fatherIndex = largestIndex
else:break
# Θ(n)
def buildMaxHeap(array):
'''Convert an original array into a max heap'''
for i in reversed(range(len(array)//2)):
maxHeapify(array, len(array), i)
# Θ(nlgn)
def heapSort(array):
'''Heap sort a designated array'''
if len(array)<=1:
return
buildMaxHeap(array)
for i in reversed(range(1, len(array))):
array[0], array[i] = array[i], array[0]
maxHeapify(array, i, 0)
# Trial
array = randomList()
print(array)
heapSort(array)
print(array)
Heap Sort. Θ(nlgn)
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 突然发现自己对这三种排序算法一无所知。他们是基于不比较类型的算法。在特殊情况下,时间复杂度可以达到 O(n) 看下...
- 堆排序是一种树形选择排序,是对直接选择排序的有效改进。 基本思想: 堆顶元素(即第一个元素)必为最小项(小顶堆)或...
- 堆排序算法,基于选择排序的思想,利用堆结构的性质来完成对数据的排序。 前提准备: 什么是堆结构:堆数据结构是一种数...