堆排序及python实现
一、首先,什么是堆?完全二叉树?满二叉树?
堆是一个完全二叉树,什么是完全二叉树呢?完全二叉树的一个特点是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素。完全二叉树和满二叉树的区别又是什么呢?
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。这个是个最大堆
堆的存储
一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。
二、二叉堆排序的思想是什么呢?
我们以大顶堆(最大堆)为例子,小顶堆的排序方法类似,思想是一样的。
1.堆排序就是把堆顶的最大数取出,如数组有n + 1个元素,放到数组的最后一个位置,即attr[n],因为数组是从0开始的。
2.将剩余的堆attr[0, n-1]继续调整为最大堆
3.剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束
那么问题来了,怎么将堆变成最大堆(大顶堆)呢?
对于一个堆来讲,比如:
A = [9, 12, 17, 30, 50, 20, 60, 65, 4, 49]
数组中包含10个数据,那么我们可以通过root = 0, root = 1, root = 2,root = 3, root = 4 就可以将数组中的所有的元素遍历到。即对于一个子堆,它的根是root,那么它的左子树的下标为2*i +1, 右子树的下标是 2*i + 2.
这样我们就把一个普通的堆变成了最大堆(大顶堆)
完整的代码实现为:
2
def filter_down(attr, start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
# if child + 1 <= end and attr[child] < attr[child + 1]:
print 'child is: ******** > ', child
print 'end is: >>>> ',end
if child + 1 < end and attr[child] < attr[child + 1]:
child += 1
if attr[root] < attr[child]:
temp = attr[root]
attr[root] = attr[child]
attr[child] = temp
root = child
else:
break
print 'the one circle is: > ', attr
三。怎么让一个随机产生的堆完成堆排序呢?假设数组为a t t r = [a1, a2, a3, …, an, an+1]
1.首先将该堆变成最大堆
2.然后将第0个值,即根节点与最后一个值交换,这样最大值就放在了数组的最后,即n+1的位置
3,则[a1, a2, a3,… an]已经不是最大堆了,用上面的方法,把数组[a1, a2, a3,… an]变成最大堆
4.不断重复2-3的步骤,从index = n开始循环执行,直到index = 0,这样整个堆排序就结束了。
四、完整的堆排序代码
#!/usr/bin/python env
# -*- coding:utf-8 -*-
import random
def filter_down(attr, start, end):
root = start
while True:
child = 2 * root + 1
if child > end:
break
# if child + 1 <= end and attr[child] < attr[child + 1]:
print 'child is: ******** > ', child
print 'end is: >>>> ',end
if child + 1 < end and attr[child] < attr[child + 1]:
child += 1
if attr[root] < attr[child]:
temp = attr[root]
attr[root] = attr[child]
attr[child] = temp
root = child
else:
break
print 'the one circle is: > ', attr
def heap_sort(attr):
attr_num = len(attr) - 1
sort_num = len(attr) // 2 -1
for index in range(sort_num, -1, -1):
filter_down(attr, index, attr_num)
print 'the large heap list is: ', attr
for end_index in range(attr_num, -1, -1):
print ' choose end is ***** >>>>> ', end_index
temp = attr[0]
attr[0] = attr[end_index]
attr[end_index] = temp
filter_down(attr, 0, end_index - 1)
if __name__ == '__main__':
attr_list = []
for i in range(15):
attr_list.append(random.randrange(1000))
print attr_list
heap_sort(attr_list)
print '########################'
print attr_list
五、堆排序的时间复杂度
堆排序与快速排序一样,时间复杂度为O(N*logN)