堆排序的Python实现

浏览数：19 / 时间：2015年06月08日

堆排序的思想: 堆是一种数据结构，可以将堆看作一棵完全二叉树，这棵二叉树满足，任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值。将一个无序序列调整为一个堆，就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换到序列的最后一个，这样有序序列就元素就增加一个，无序序列元素就减少一个，对新的无序序列重复这样的操作，就实现了排序。

堆排序的执行过程：

1.从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大顶堆。

对节点的调整方法：将当前节点（假设为a）的值与其孩子节点进行比较，如果存在大于a的值的孩子节点，则从中选出最大的一个与a交换。当a来到下一层的时候重复上述过程，直到a的孩子节点的值都小于a为止

2.将当前无序序列中的第一个元素（反映在数中是根节点b），与无序序列中的最后一个元素交换（假设为c），b进入有序序列，到达最终位置。无序序列元素减少1个，有序序列元素增加1个，此时只有节点c可能不满足堆的定义，对其进行调整。

3.重复2 的过程，直到无序序列的元素剩下一个时排序结束。

技术分享

 1 # -*- coding:utf-8 -*-
 2 # 堆排序适用于记录数很多的情况
 3 
 4 from collections import deque
 5 
 6 # 这里需要说明元素的存储必须要从1开始
 7 # 涉及到左右节点的定位，和堆排序开始调整节点的定位
 8 # 在下标0处插入0，它不参与排序
 9 L = deque([49,38,65,97,76,13,27,49])
10 L.appendleft(0)
11 
12 #L = [0,49,38,65,97,76,13,27,49]
13 
14 def element_exchange(numbers,low,high):
15 
16     temp = numbers[low]
17 
18     # j 是low的左孩子节点(cheer!)
19     i = low
20     j = 2*i
21 
22     while j<=high:
23         # 如果右节点较大，则把j指向右节点
24         if j<high and numbers[j]<numbers[j+1]:
25             j = j+1
26         if temp<numbers[j]:
27             # 将numbers[j]调整到双亲节点的位置上
28             numbers[i] = numbers[j]
29             i = j
30             j = 2*i
31         else:
32             break
33     # 被调整节点放入最终位置
34     numbers[i] = temp
35 
36 def top_heap_sort(numbers):
37 
38     length = len(numbers)-1
39 
40     # 指定第一个进行调整的元素的下标
41     # 它即该无序序列完全二叉树的第一个非叶子节点
42     # 它之前的元素均要进行调整
43     # cheer up！
44     first_exchange_element = length/2
45 
46     #建立初始堆
47     print first_exchange_element
48     for x in range(first_exchange_element):
49         element_exchange(numbers,first_exchange_element-x,length)
50 
51     # 将根节点放到最终位置，剩余无序序列继续堆排序
52     # length-1 次循环完成堆排序
53     for y in range(length-1):
54         temp = numbers[1]
55         numbers[1] = numbers[length-y]
56         numbers[length-y] = temp
57         element_exchange(numbers,1,length-y-1)
58 
59 if __name__==‘__main__‘:
60     top_heap_sort(L)
61     for x in range(1,len(L)):
62         print L[x],