欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆排序及python实现

程序员文章站 2022-06-06 20:40:57
...

一、首先,什么是堆?完全二叉树?满二叉树?
堆是一个完全二叉树,什么是完全二叉树呢?完全二叉树的一个特点是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素。完全二叉树和满二叉树的区别又是什么呢?
满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

对于完全二叉树来说,叶子结点只可能在层次最大的两层上出现:对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次或为p,或为p+1。
堆排序及python实现
堆排序及python实现
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。这个是个最大堆
堆排序及python实现

堆的存储
一般都用数组来表示堆,i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

堆排序及python实现
二、二叉堆排序的思想是什么呢?
我们以大顶堆(最大堆)为例子,小顶堆的排序方法类似,思想是一样的。
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.堆排序及python实现

堆排序及python实现

堆排序及python实现

堆排序及python实现

这样我们就把一个普通的堆变成了最大堆(大顶堆)

完整的代码实现为:


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
2
三。怎么让一个随机产生的堆完成堆排序呢?假设数组为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)