Sunday, May 3, 2015

Basic usage of heapq in python

"""
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.

No comments:

Post a Comment