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!

InPython,youappendelementstoalistusingtheappend()method.1)Useappend()forsingleelements:my_list.append(4).2)Useextend()or =formultipleelements:my_list.extend(another_list)ormy_list =[4,5,6].3)Useinsert()forspecificpositions:my_list.insert(1,5).Beaware

The methods to debug the shebang problem include: 1. Check the shebang line to make sure it is the first line of the script and there are no prefixed spaces; 2. Verify whether the interpreter path is correct; 3. Call the interpreter directly to run the script to isolate the shebang problem; 4. Use strace or trusts to track the system calls; 5. Check the impact of environment variables on shebang.

Pythonlistscanbemanipulatedusingseveralmethodstoremoveelements:1)Theremove()methodremovesthefirstoccurrenceofaspecifiedvalue.2)Thepop()methodremovesandreturnsanelementatagivenindex.3)Thedelstatementcanremoveanitemorslicebyindex.4)Listcomprehensionscr

Pythonlistscanstoreanydatatype,includingintegers,strings,floats,booleans,otherlists,anddictionaries.Thisversatilityallowsformixed-typelists,whichcanbemanagedeffectivelyusingtypechecks,typehints,andspecializedlibrarieslikenumpyforperformance.Documenti

Pythonlistssupportnumerousoperations:1)Addingelementswithappend(),extend(),andinsert().2)Removingitemsusingremove(),pop(),andclear().3)Accessingandmodifyingwithindexingandslicing.4)Searchingandsortingwithindex(),sort(),andreverse().5)Advancedoperatio

Create multi-dimensional arrays with NumPy can be achieved through the following steps: 1) Use the numpy.array() function to create an array, such as np.array([[1,2,3],[4,5,6]]) to create a 2D array; 2) Use np.zeros(), np.ones(), np.random.random() and other functions to create an array filled with specific values; 3) Understand the shape and size properties of the array to ensure that the length of the sub-array is consistent and avoid errors; 4) Use the np.reshape() function to change the shape of the array; 5) Pay attention to memory usage to ensure that the code is clear and efficient.

BroadcastinginNumPyisamethodtoperformoperationsonarraysofdifferentshapesbyautomaticallyaligningthem.Itsimplifiescode,enhancesreadability,andboostsperformance.Here'showitworks:1)Smallerarraysarepaddedwithonestomatchdimensions.2)Compatibledimensionsare

ForPythondatastorage,chooselistsforflexibilitywithmixeddatatypes,array.arrayformemory-efficienthomogeneousnumericaldata,andNumPyarraysforadvancednumericalcomputing.Listsareversatilebutlessefficientforlargenumericaldatasets;array.arrayoffersamiddlegro


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

SublimeText3 Chinese version
Chinese version, very easy to use

Dreamweaver CS6
Visual web development tools

Notepad++7.3.1
Easy-to-use and free code editor

WebStorm Mac version
Useful JavaScript development tools
