使用python创建堆以及实现堆排序

堆是计算机科学中一类特殊的数据结构的总称，堆通常可以被看做是一颗完全二叉树的数组对象。

<>堆的特性

* 它是完全二叉树，除了树的最后一层结点不需要是满的，其他的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求坐满右不满。
*
他通常用数组来实现。具体方法就是讲二叉树的结点按照层级顺序放入数组中，根结点的在位置1，他的子结点在位置2和3，而子结点的子结点分别在位置4,5，6和7，以此类推。如果一个结点的位置为k，则它的父结点的位置为k/2，而他的两个子结点的位置分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动，从a[k]向上一层，就令k=k/2，而向下一层就令k等于2k或2k+1，
* 每个结点都大于等于它的两个子结点，这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟二叉查找树是有区别的。
<>python创建堆及堆排序的实现
## 堆的创建及堆排序 import copy import time import random # 堆的创建，该堆为大根堆 class Heap(
object): def __init__(self): self.item = [0] ## 创建一个列表用来存储堆元素,第一个索引处的元素废弃掉，0做占位用
self.N = 0 ## 记录元素的个数 ## 往堆中插入元素 def insert(self, data): if len(self.item) > 1:
self.N += 1 self.item.append(data) self.swim(self.N) ## 使用上浮算法使元素处于正确的位置 else:
self.N += 1 self.item.append(data) ## 删除堆中最大的元素 def deleteMax(self): self.item[
self.N], self.item[1] = self.item[1], self.item[self.N] ## 交换最后一个元素和第一个元素 self.
item.pop() ## 删除最后一个元素 self.N -= 1 self.sink(1) ## 使用下沉算法将第一个元素调整至合适的位置 ##
上浮算法调整元素位置 def swim(self, K): while K > 1: f_data_index = K // 2 ##
获取当前结点的父结点的元素的索引 if self.item[f_data_index] < self.item[K]: self.item[
f_data_index], self.item[K] = self.item[K], self.item[f_data_index] K //= 2 else
: break ## 下沉算法调整元素位置 def sink(self, K): while 2 * K + 1 <= self.N:
s1_data_index= 2 * K ## 左子节点索引 s2_data_index = 2 * K + 1 ## 右子节点索引 s_data_index
= s1_data_index if self.item[s1_data_index] > self.item[ s2_data_index] else
s2_data_index## 取值较大的子节点的索引 if self.item[s_data_index] > self.item[K]: self.item
[s_data_index], self.item[K] = self.item[K], self.item[s_data_index] K =
s_data_indexelse: break def getdata(self): return self.item ## 堆排序 class
HeapSort(object): ## 使用下沉算法将第i个元素在一定的范围内处于正确的位置 def sink(self, i, heap,end):
""" :param i: 使用下沉算法的元素的索引 :param heap: 堆 :param end: 下沉算法作用的范围的最后一个元素的索引
:return: """ while 2 * i < len(heap[:end]): s1_data_index = 2 * i ## 左子节点索引 if 2
* i + 1 < len(heap[:end]): s2_data_index = 2 * i + 1 ## 右子节点索引 s_data_index =
s1_data_indexif heap[s1_data_index] > heap[ s2_data_index] else s2_data_index
## 取值较大的子节点的索引 else: s_data_index = s1_data_index if heap[s_data_index] > heap[i
]: heap[s_data_index], heap[i] = heap[i], heap[s_data_index] i = s_data_index
else: break # print(heap) ## 将数组转化成堆结构 def convert(self, source): heap = copy.
deepcopy(source) heap.insert(0, 0) start = len(source) // 2 for i in range(start
, 0, -1): self.sink(i, heap,len(heap)) return heap ## 对堆进行排序 def sort(self,
source): heap = self.convert(source) end_index = len(heap) - 1 while end_index >
1: heap[end_index], heap[1] = heap[1], heap[end_index] ## 交换第一个元素和未排序的堆中的最后一个元素
self.sink(1, heap,end_index) end_index -= 1 return heap if __name__ ==
'__main__': heap = Heap() heap.insert(100) heap.insert(98) heap.insert(122) heap
.insert(150) heap.insert(102) heap.insert(89) heap.insert(101) print("堆数据为：{}".
format(heap.getdata())) heap.deleteMax() print("删除堆中最大值后的堆数据为：{}".format(heap.
getdata())) ## 使用堆进行10000调数据的排序用时测试 list = [random.randint(1, 10000000) for i in
range(10000)] heapSort = HeapSort() start_time = time.time() heap = heapSort.
sort(list) end_time = time.time() print("堆排序用时：{}".format(end_time-start_time))
结果：

• « 上一篇：第四章-存储器（下）
• » 下一篇：主成分分析python代码实现