heap queque(堆队列),是一个完全二叉树,并且满足一个条件:每个节点(叶节点除外)的值都大于等于(或小于等于)它的子节点。提供了构建小顶堆的方法和一些小顶堆的基本操作方法(如入堆、出堆等),可以用于实现堆排序算法。
创建堆的两种方法:
import heapq lists = [3, 10, 20, 52, 2, 83, 52, 81, 51]
#一、 创建空列表,然后使用heappush将数据添加到空列表中,每添加一个新数据后,该列表都满足小顶堆特性。 heap = [] for i in lists: heapq.heappush(heap, i)
print("lists: ",lists) print("heap: ",heap)
# 二、使用heapify直接将数据列表调整为小顶堆格式 heapq.heapify(lists) print("The lists after heap is : ",lists)
注:小顶堆含义,每个节点(叶节点除外)的值都小于等于其子节点的值,根节点的值是所有节点中最小的。大顶堆反之。
使用heapq进行堆排序:
import heapq
lists = [3, 10, 20, 52, 2, 83, 52, 81, 51]
# 这里需要先构建堆,否则直接heappop得不到排序后的结果 heap = [] for i in lists: heapq.heappush(heap, i) print(heap[0])
# heappop(heap),依次取出堆顶的值,并将剩余的数据构造成新的小顶堆 heap_sort = [heapq.heappop(heap) for _ in range(len(heap))] print("heap sort result: ", heap_sort)
获取堆中的最大值和最小值
import heapq lists = [3, 10, 20, 52, 2, 83, 52, 81, 51] # 这里的heapq.heapify(lists)写与不写效果一样 heapq.heapify(lists)
# heapq.nlargest和heapq.nsmallest两个函数可以用于堆,也可以用于列表,功能相同。所以前面无需构造堆 print(heapq.nlargest(2, lists)) print(heapq.nsmallest(3, lists))
堆中元素的替换方法
import heapq # 这里演示heappushpop和heapreplace的用法 # heappushpop,先入堆再出堆,所以堆元素不变化 array_c = [10, 7, 15, 8] heapq.heapify(array_c) print("before: ",array_c) # 先push再pop item = heapq.heappushpop(array_c, 5) print("after: ",array_c) print(item) # heapreplace,先出堆,再将新元素入堆,堆元素发生变化 array_d = [10, 7, 15, 8] heapq.heapify(array_d) print("before: ",array_d) item = heapq.heapreplace(array_d, 5) print("after: ",array_d) print(item)
堆的方法:
heapq.heapify(x):创建堆,将list转化为堆
heapq.heappush(heap, item): 添加新元素到堆
heapq.heappop(heap):弹出堆顶元素,并将剩余元素组成新的小顶堆
heap.heappushpop(heap, item):先将item入堆,再将item出堆
heapq.merge(*iterables, key = None, reverse = False):暂未了解
heapq.heapreplace(heap, item):先弹出堆顶元素,再将item入堆
heapq.nlargest(n, iterable, key = None)
heapq.nsmallest(n, iterable, key = None)
标签:heapq,之堆,python,lists,item,heap,print,array From: https://www.cnblogs.com/mastershun/p/18000318