The heapq module provides heap algorithms. heapq is a tree data structure in which child nodes and parent nodes are sorted. This module provides heap[k]
Print heapq type
import math import random from cStringIO import StringIO def show_tree(tree, total_width=36, fill=' '): output = StringIO() last_row = -1 for i, n in enumerate(tree): if i: row = int(math.floor(math.log(i+1, 2))) else: row = 0 if row != last_row: output.write('\n') columns = 2**row col_width = int(math.floor((total_width * 1.0) / columns)) output.write(str(n).center(col_width, fill)) last_row = row print output.getvalue() print '-' * total_width print return data = random.sample(range(1,8), 7) print 'data: ', data show_tree(data)
Print result
data: [3, 2, 6, 5, 4, 7, 1] 3 2 6 5 4 7 1 ------------------------- heapq.heappush(heap, item)
Push an element into the heap and modify the above code
heap = [] data = random.sample(range(1,8), 7) print 'data: ', data for i in data: print 'add %3d:' % i heapq.heappush(heap, i) show_tree(heap)
Print the result
data: [6, 1, 5, 4, 3, 7, 2] add 6: 6 ------------------------------------ add 1: 1 6 ------------------------------------ add 5: 1 6 5 ------------------------------------ add 4: 1 4 5 6 ------------------------------------ add 3: 1 3 5 6 4 ------------------------------------ add 7: 1 3 5 6 4 7 ------------------------------------ add 2: 1 3 2 6 4 7 5 ------------------------------------
It can be understood from the results that the elements of the child node are larger than the elements of the parent node. Sibling nodes will not be sorted.
heapq.heapify(list)
Convert the list type to heap and rearrange the list in linear time.
print 'data: ', data heapq.heapify(data) print 'data: ', data show_tree(data)
Print results
data: [2, 7, 4, 3, 6, 5, 1] data: [1, 3, 2, 7, 6, 5, 4] 1 3 2 7 6 5 4 ------------------------------------ heapq.heappop(heap)
Delete and return the smallest element in the heap, by heapify() and heappop() to sort.
data = random.sample(range(1, 8), 7) print 'data: ', data heapq.heapify(data) show_tree(data) heap = [] while data: i = heapq.heappop(data) print 'pop %3d:' % i show_tree(data) heap.append(i) print 'heap: ', heap
Print results
data: [4, 1, 3, 7, 5, 6, 2] 1 4 2 7 5 6 3 ------------------------------------ pop 1: 2 4 3 7 5 6 ------------------------------------ pop 2: 3 4 6 7 5 ------------------------------------ pop 3: 4 5 6 7 ------------------------------------ pop 4: 5 7 6 ------------------------------------ pop 5: 6 7 ------------------------------------ pop 6: 7 ------------------------------------ pop 7: ------------------------------------ heap: [1, 2, 3, 4, 5, 6, 7]
You can see the sorted heap.
heapq.heapreplace(iterable, n)
Removes the existing element and replaces it with a new value.
data = random.sample(range(1, 8), 7) print 'data: ', data heapq.heapify(data) show_tree(data) for n in [8, 9, 10]: smallest = heapq.heapreplace(data, n) print 'replace %2d with %2d:' % (smallest, n) show_tree(data)
Print results
data: [7, 5, 4, 2, 6, 3, 1] 1 2 3 5 6 7 4 ------------------------------------ replace 1 with 8: 2 5 3 8 6 7 4 ------------------------------------ replace 2 with 9: 3 5 4 8 6 7 9 ------------------------------------ replace 3 with 10: 4 5 7 8 6 10 9 ------------------------------------
heapq.nlargest(n, iterable ) and heapq.nsmallest(n, iterable)
Return the n maximum and minimum values in the list
data = range(1,6) l = heapq.nlargest(3, data) print l # [5, 4, 3] s = heapq.nsmallest(3, data) print s # [1, 2, 3]
PS: A calculation question
Construct a minimum heap code example with the number of elements K=5:
#!/usr/bin/env python # -*- encoding: utf-8 -*- # Author: kentzhan # import heapq import random heap = [] heapq.heapify(heap) for i in range(15): item = random.randint(10, 100) print "comeing ", item, if len(heap) >= 5: top_item = heap[0] # smallest in heap if top_item < item: # min heap top_item = heapq.heappop(heap) print "pop", top_item, heapq.heappush(heap, item) print "push", item, else: heapq.heappush(heap, item) print "push", item, pass print heap pass print heap print "sort" heap.sort() print heap
Result:
For more articles related to the usage of the heapq module in Python, please pay attention to the PHP Chinese website!