""" Understang heapq """ nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] # How to find max and min in the list?? In [2]: max(nums) Out[2]: 42 In [3]: min(nums) Out[3]: -4 #How to find n maximum numbers? #this is not a well written .I'm lazy so is there a pythonic way? def n_max(n,nums): max_list=[] if len(nums) == 0: return (0) elif len(nums) == 1: return nums elif len(nums) >1: for i in range(n): max_list.append(max(nums)) nums.remove(max(nums)) return max_list,len(max_list) print n_max(11,nums) #Using heapq #The heapq module has two functions— nlargest() and nsmallest() —that do exactly and more efficeint way In [1]: nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] In [2]: import heapq In [3]: print (heapq.nlargest(3,nums)) [42, 37, 23] In [4]: print (heapq.nsmallest(3,nums)) [-4, 1, 2] In [5]: portfolio =[{'name':"Ajay",'age':24,'sex':'Male'}, ...: {'name':"Cam",'age':23,'sex':'Male'}, ...: {'name':"Cyber",'age':16,'sex':'Female'}] In [6]: In [6]: youngest=heapq.nsmallest(1,portfolio,key=lambda s: s['age']) In [7]: youngest Out[7]: [{'age': 16, 'name': 'Cyber', 'sex': 'Female'}] In [8]: youngest=heapq.nsmallest(2,portfolio,key=lambda s: s['age']) In [9]: youngest Out[9]: [{'age': 16, 'name': 'Cyber', 'sex': 'Female'}, {'age': 23, 'name': 'Cam', 'sex': 'Male'}] In [10]: eldest=heapq.nlargest(1,portfolio,key=lambda s: s['age']) In [11]: eldest Out[11]: [{'age': 24, 'name': 'Ajay', 'sex': 'Male'}] """ A heap is a tree-like data structure where the child nodes have a sort-order relationship with the parents. Binary heaps can be represented using a list or an array organized so that the children of element N are at positions 2*N+1 and 2*N+2 (for zero-based indexes). This layout makes it possible to rearrange heaps in place, so it is not necessary to reallocate as much memory when adding or removing items. A max-heap ensures that the parent is larger than or equal to both of its children. A min-heap requires that the parent be less than or equal to its children. Python’s heapq module implements a min-heap. Check http://visualgo.net/heap.html(max heap implementation) minheap --> https://www.cs.usfca.edu/~galles/visualization/Heap.html http://kanaka.github.io/rbt_cfs/trees.html check heapify,heappush,heapop from the standard library Practical use of heapq http://stackoverflow.com/questions/8627109/what-would-you-use-the-heapq-python-module-for-in-real-life https://docs.python.org/3/library/heapq.html """ #To understand heap start with an empty list >>> import heapq >>> l=[1,9,2,4,8,5,6] # (L is llooking like 1) >>> l=[] >>> heapq.heappush(l,1) >>> heapq.heappush(l,10) >>> heapq.heappush(l,4) >>> heapq.heappush(l,6) >>> heapq.heappush(l,8) >>> l [1, 6, 4, 10, 8] >>> heapq.heappop(l) 1 >>> l [4, 6, 8, 10] >>> heapq.heappushpop(l,83) 4 >>> l [6, 10, 8, 83]Learn python for fun.The popular blog with questions and answers to the python.Solutions to facebookhackercup,codejam,codechef.The fun way to learn python with me.Building some cool apps.

## Sunday, May 3, 2015

### Basic usage of heapq in python

Labels:
ds-and-algo,
python

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment