Python中的堆（python堆排序）

Python中的堆（python堆排序）

一、堆的理解

1、堆是在程序运行时，而不是在程序编译时，请求操作系统分配给自己某个大小的内存空间。即动态分配内存，对其访问和对一般内存的访问没有区别。

2、堆是指程序运行时申请的动态内存，而栈只是指一种使用堆的方法(即先进后出)。栈是先进后出的，但是于堆而言却没有这个特性，两者都是存放临时数据的地方。 对于堆，我们可以随心所欲的进行增加变量和删除变量，不要遵循任何次序，只要你喜欢。

3、对于一个堆heap来说，它最小的元素总是它的根节点，即heap[0]

二、堆的概念

堆是一个二叉树，其中每个父节点的值都小于或等于其所有子节点的值。整个堆的最小元素总是位于二叉树的根节点。python的heapq模块提供了对堆的支持。堆数据结构最重要的特征是heap[0]永远是最小的元素

三、堆的相关操作

1.heapq.heappush(heap,item)  #heap为定义堆，item 增加的元素;

heapq有两种方式创建堆， 一种是使用一个空列表，然后使用heapq.heappush()函数把值加入堆中；import heapqheap = [] heapq.heappush(heap,1)heapq.heappush(heap,2)heapq.heappush(heap,3)heap#[1,2,3]

2.heapq.heapify(list)        #将列表转换为堆

另外一种就是使用heap.heapify(list)转换列表成为堆结构；>>> list = [1,2,3,5,1,5,8,9,6]>>> heapq.heapify(list)>>> list[1, 1, 3, 5, 2, 5, 8, 9, 6]

3、heapq.heappop(heap)            #删除最小值，因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素。

>>> list[1, 1, 3, 5, 2, 5, 8, 9, 6]>>> heapq.heappop(list)1>>> list[1, 2, 3, 5, 6, 5, 8, 9]

4、heapq.heapreplace(heap.item)         #删除最小元素值，添加新的元素值

>>> list[1, 2, 3, 5, 6, 5, 8, 9]>>> heapq.heapreplace(list,99)1>>> list[2, 5, 3, 9, 6, 5, 8, 99]

5、heapq.heapreplace(heap,item)             #首先判断添加元素值与堆的第一个元素值对比，如果大，则删除第一个元素，然后添加新的元素值，购置不更改堆

>>> list[2, 5, 3, 9, 6, 5, 8, 99]>>> heapq.heappushpop(list,6)2>>> list[3, 5, 5, 9, 6, 6, 8, 99]>>> heapq.heappushpop(list,1)1>>> list[3, 5, 5, 9, 6, 6, 8, 99]

6、heapq.merge（…）         #将多个堆合并

>>> list[3, 5, 5, 9, 6, 6, 8, 99]>>> h[1000]>>> for i in heapq.merge(h,list):... print(i,end=" ")...3 5 5 9 6 6 8 99 1000

7、heapq.nlargest(n,heap)           #查询堆中的最大元素，n表示查询元素个数

>>> list[3, 5, 5, 9, 6, 6, 8, 99]>>> heapq.nlargest(3,list)[99, 9, 8]>>>

8、heapq.nsmallest(n,heap)         #查询堆中的最小元素，n表示查询元素的个数

>>> list[3, 5, 5, 9, 6, 6, 8, 99]>>> heapq.nsmallest(3,list)[3, 5, 5]

去期待陌生，去拥抱惊喜。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。