广告推广平台网站,asp网站搭建工具,上海电子商城网站制作,网站设计的分辨率heapqpython内置heapq模块#xff0c;通过import heapq导入。heapq模块是用于堆实现优先队列。我们知道队列是先进先出(FIFO)#xff0c;heapq中的优先队列指的是不论谁先进#xff0c;最小的先出或者最大的先出。# 需要注意的是heapq的堆是小根堆。01 23 4 5 67 8 9 10 11 …heapqpython内置heapq模块通过import heapq导入。heapq模块是用于堆实现优先队列。我们知道队列是先进先出(FIFO)heapq中的优先队列指的是不论谁先进最小的先出或者最大的先出。# 需要注意的是heapq的堆是小根堆。01 23 4 5 67 8 9 10 11 12 13 1415 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30# 堆顶位置的元素最小heapq和python一致下标索引从0开始。# heapq提供的主要API, Usage:heap [] # creates an empty heapheappush(heap, item) # pushes a new item on the heapitem heappop(heap) # pops the smallest item from the heapitem heap[0] # smallest item on the heap without popping itheapify(x) # transforms list into a heap, in-place, in linear timeitem heapreplace(heap, item) # pops and returns smallest item, and adds# new item; the heap size is unchangedheapq实现列表排序基本排序流程# -*- coding: utf-8 -*-# created by X. Liu on 2020/3/14import heapqimport randomli [i for i in range(10)]random.shuffle(li)print(排序前, li)# step1: 建堆(小根堆)heapq.heapify(li)print(小根堆, li)# step2: 排序# heapq.heappop()方法弹出堆顶元素即最小的元素new_li []for i in range(10):new_li.append(heapq.heappop(li))print(排序后, new_li)# output:排序前 [3, 4, 9, 0, 5, 1, 6, 2, 8, 7]小根堆 [0, 2, 1, 3, 5, 9, 6, 4, 8, 7]排序后 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]堆排序实现版本2 (不考虑时间复杂度)# 借助 heapq.heappush() heapq.heappop()# heappush(h, item) # Push the value item onto the heap, maintaining the heap invariant.import heapqdef heap_sort(li):h []# 建小根堆for i in li:heapq.heappush(h, i)# 依次弹出最小元素构成有序列表切片回lili[:] [heapq.heappop() for i in range(len(li))]对比分析heapq的heapify建堆函数和我们自己实现的建堆函数大同小异。我们自己的sift函数一步到位(实现堆顶元素选位的过程)heapify中使用两步判断比较其实不如我们自己写的sift好。heappop函数实现每次弹出堆顶元素弹出后再将整个堆调整为一个新的小根堆。它的目的是为了实现优先队列所以才会这样设计。我们如果希望借助它实现列表排序只能手动排序。补充heap的值可以是元组 h [] heappush(h, (5, write code)) heappush(h, (7, release product)) heappush(h, (1, write spec)) heappush(h, (3, create tests)) heappop(h)(1, write spec)heapq.heapify(x)底层代码实现def heapify(x):n len(x)for i in reversed(range(n//2)):_siftup(x, i)def _siftup(heap, pos):endpos len(heap)startpos posnewitem heap[pos]# Bubble up the smaller child until hitting a leaf.childpos 2*pos 1 # leftmost child positionwhile childpos endpos:# Set childpos to index of smaller child.rightpos childpos 1if rightpos endpos and not heap[childpos] heap[rightpos]:childpos rightpos# Move the smaller child up.heap[pos] heap[childpos]pos childposchildpos 2*pos 1# The leaf at pos is empty now. Put newitem there, and bubble it up# to its final resting place (by sifting its parents down).heap[pos] newitem_siftdown(heap, startpos, pos)def _siftdown(heap, startpos, pos):newitem heap[pos]# Follow the path to the root, moving parents down until finding a place# newitem fits.while pos startpos:parentpos (pos - 1) 1parent heap[parentpos]if newitem parent:heap[pos] parentpos parentposcontinuebreakheap[pos] newitemheapq.heappop底层代码实现def heappop(heap):Pop the smallest item off the heap, maintaining the heap invariant.lastelt heap.pop() # raises appropriate IndexError if heap is emptyif heap:returnitem heap[0]heap[0] lastelt_siftup(heap, 0)return returnitemreturn lastelt
