Deque in Python
Deque can be implemented in python using the module “collections“. Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.
Operations on deque :
1. append() :- This function is used to insert the value in its argument to the right end of deque.
2. appendleft() :- This function is used to insert the value in its argument to the left endof deque.
3. pop() :- This function is used to delete an argument from the right end of deque.
4. popleft() :- This function is used to delete an argument from the left end of deque.
# Python code to demonstrate working of # append(), appendleft(), pop(), and popleft() # importing "collections" for deque operations import collections # initializing deque de = collections.deque([1,2,3]) # using append() to insert element at right end # inserts 4 at the end of deque de.append(4) # printing modified deque print ("The deque after appending at right is : ") print (de) # using appendleft() to insert element at right end # inserts 6 at the beginning of deque de.appendleft(6) # printing modified deque print ("The deque after appending at left is : ") print (de) # using pop() to delete element from right end # deletes 4 from the right end of deque de.pop() # printing modified deque print ("The deque after deleting from right is : ") print (de) # using popleft() to delete element from left end # deletes 6 from the left end of deque de.popleft() # printing modified deque print ("The deque after deleting from left is : ") print (de) |
5. index(ele, beg, end) :- This function returns the first index of the value mentioned in arguments, starting searching from beg till end index.
6. insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i)specified in arguments.
7. remove() :- This function removes the first occurrence of value mentioned in arguments.
8. count() :- This function counts the number of occurrences of value mentioned in arguments.
# Python code to demonstrate working of # insert(), index(), remove(), count() # importing "collections" for deque operations import collections # initializing deque de = collections.deque([1, 2, 3, 3, 4, 2, 4]) # using index() to print the first occurrence of 4 print ("The number 4 first occurs at a position : ") print (de.index(4,2,5)) # using insert() to insert the value 3 at 5th position de.insert(4,3) # printing modified deque print ("The deque after inserting 3 at 5th position is : ") print (de) # using count() to count the occurrences of 3 print ("The count of 3 in deque is : ") print (de.count(3)) # using remove() to remove the first occurrence of 3 de.remove(3) # printing modified deque print ("The deque after deleting first occurrence of 3 is : ") print (de) |
Output:
The number 4 first occurs at a position : 4 The deque after inserting 3 at 5th position is : deque([1, 2, 3, 3, 3, 4, 2, 4]) The count of 3 in deque is : 3 The deque after deleting first occurrence of 3 is : deque([1, 2, 3, 3, 4, 2, 4])
9. extend(iterable) :- This function is used to add multiple values at the right end of deque. The argument passed is an iterable.
10. extendleft(iterable) :- This function is used to add multiple values at the left end of deque. The argument passed is an iterable. Order is reversed as a result of left appends.
11. reverse() :- This function is used to reverse order of deque elements.
12. rotate() :- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to left. Else rotation is to right.
# Python code to demonstrate working of # extend(), extendleft(), rotate(), reverse() # importing "collections" for deque operations import collections # initializing deque de = collections.deque([1, 2, 3,]) # using extend() to add numbers to right end # adds 4,5,6 to right end de.extend([4,5,6]) # printing modified deque print ("The deque after extending deque at end is : ") print (de) # using extendleft() to add numbers to left end # adds 7,8,9 to right end de.extendleft([7,8,9]) # printing modified deque print ("The deque after extending deque at beginning is : ") print (de) # using rotate() to rotate the deque # rotates by 3 to left de.rotate(-3) # printing modified deque print ("The deque after rotating deque is : ") print (de) # using reverse() to reverse the deque de.reverse() # printing modified deque print ("The deque after reversing deque is : ") print (de) |
Output :
The deque after extending deque at end is : deque([1, 2, 3, 4, 5, 6]) The deque after extending deque at beginning is : deque([9, 8, 7, 1, 2, 3, 4, 5, 6]) The deque after rotating deque is : deque([1, 2, 3, 4, 5, 6, 9, 8, 7]) The deque after reversing deque is : deque([7, 8, 9, 6, 5, 4, 3, 2, 1])
Namedtuple in Python
Python supports a type of container like dictionaries called “namedtuples()” present in module, “collection“. Like dictionaries they contain keys that are hashed to a particular value. But on contrary, it supports both access from key value and iteration, the functionality that dictionaries lack.
Operations on namedtuple() :
1. Access by index : The attribute values of namedtuple() are ordered and can be accessed using the index number unlike dictionaries which are not accessible by index.
2. Access by keyname : Access by keyname is also allowed as in dictionaries.
3. using getattr() :- This is yet another way to access the value by giving namedtuple and key value as its argument.
# Python code to demonstrate namedtuple() and # Access by name, index and getattr() # importing "collections" for namedtuple() import collections # Declaring namedtuple() Student = collections.namedtuple('Student',['name','age','DOB']) # Adding values S = Student('Nandini','19','2541997') # Access using index print ("The Student age using index is : ",end ="") print (S[1]) # Access using name print ("The Student name using keyname is : ",end ="") print (S.name) # Access using getattr() print ("The Student DOB using getattr() is : ",end ="") print (getattr(S,'DOB')) |
Output :
The Student age using index is : 19 The Student name using keyname is : Nandini The Student DOB using getattr() is : 2541997
1. _make() :- This function is used to return a namedtuple() from the iterable passed as argument.
2. _asdict() :- This function returns the OrdereDict() as constructed from the mapped values of namedtuple().
3. using “**” (double star) operator :- This function is used to convert a dictionary into the namedtuple().
# Python code to demonstrate namedtuple() and # _make(), _asdict() and "**" operator # importing "collections" for namedtuple() import collections # Declaring namedtuple() Student = collections.namedtuple('Student',['name','age','DOB']) # Adding values S = Student('Nandini','19','2541997') # initializing iterable li = ['Manjeet', '19', '411997' ] # initializing dict di = { 'name' : "Nikhil", 'age' : 19 , 'DOB' : '1391997' } # using _make() to return namedtuple() print ("The namedtuple instance using iterable is : ") print (Student._make(li)) # using _asdict() to return an OrderedDict() print ("The OrderedDict instance using namedtuple is : ") print (S._asdict()) # using ** operator to return namedtuple from dictionary print ("The namedtuple instance from dict is : ") print (Student(**di)) |
Output :
The namedtuple instance using iterable is :
Student(name='Manjeet', age='19', DOB='411997')
The OrderedDict instance using namedtuple is :
OrderedDict([('name', 'Nandini'), ('age', '19'), ('DOB', '2541997')])
The namedtuple instance from dict is :
Student(name='Nikhil', age=19, DOB='1391997')
1. _fields :- This function is used to return all the keynames of the namespace declared.
2. _replace() :- This function is used to change the values mapped with the passed keyname.
# Python code to demonstrate namedtuple() and # _fields and _replace() # importing "collections" for namedtuple() import collections # Declaring namedtuple() Student = collections.namedtuple('Student',['name','age','DOB']) # Adding values S = Student('Nandini','19','2541997') # using _fields to display all the keynames of namedtuple() print ("All the fields of students are : ") print (S._fields) # using _replace() to change the attribute values of namedtuple print ("The modified namedtuple is : ") print(S._replace(name = 'Manjeet')) |
Output :
All the fields of students are :
('name', 'age', 'DOB')
The modified namedtuple is :
Student(name='Manjeet', age='19', DOB='2541997')
Heap queue (or heapq) in Python
Heap data structure is mainly used to represent a priority queue. In Python, it is available using “heapq” module. The property of this data structure in python is that each time the smallest of heap element is popped(min heap). Whenever elements are pushed or popped, heap structure in maintained. The heap[0] element also returns the smallest element each time.
Operations on heap :
1. heapify(iterable) :- This function is used to convert the iterable into a heap data structure. i.e. in heap order.
2. heappush(heap, ele) :- This function is used to insert the element mentioned in its arguments into heap. The order is adjusted, so as heap structure is maintained.
3. heappop(heap) :- This function is used to remove and return the smallest elementfrom heap. The order is adjusted, so as heap structure is maintained.
# Python code to demonstrate working of # heapify(), heappush() and heappop() # importing "heapq" to implement heap queue import heapq # initializing list li = [5, 7, 9, 1, 3] # using heapify to convert list into heap heapq.heapify(li) # printing created heap print ("The created heap is : ",end="") print (list(li)) # using heappush() to push elements into heap # pushes 4 heapq.heappush(li,4) # printing modified heap print ("The modified heap after push is : ",end="") print (list(li)) # using heappop() to pop smallest element print ("The popped and smallest element is : ",end="") print (heapq.heappop(li)) |
Output :
The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1
4. heappushpop(heap, ele) :- This function combines the functioning of both push and pop operations in one statement, increasing efficiency. Heap order is maintained after this operation.
5. heapreplace(heap, ele) :- This function also inserts and pops element in one statement, but it is different from above function. In this, element is first popped, then element is pushed.i.e, the value larger than the pushed value can be returned.
# Python code to demonstrate working of # heappushpop() and heapreplce() # importing "heapq" to implement heap queue import heapq # initializing list 1 li1 = [5, 7, 9, 4, 3] # initializing list 2 li2 = [5, 7, 9, 4, 3] # using heapify() to convert list into heap heapq.heapify(li1) heapq.heapify(li2) # using heappushpop() to push and pop items simultaneously # pops 2 print ("The popped item using heappushpop() is : ",end="") print (heapq.heappushpop(li1, 2)) # using heapreplace() to push and pop items simultaneously # pops 3 print ("The popped item using heapreplace() is : ",end="") print (heapq.heapreplace(li2, 2)) |
Output :
The popped item using heappushpop() is : 2 The popped item using heapreplace() is : 3
6. nlargest(k, iterable, key = fun) :- This function is used to return the k largest elements from the iterable specified and satisfying the key if mentioned.
7. nsmallest(k, iterable, key = fun) :- This function is used to return the k smallest elements from the iterable specified and satisfying the key if mentioned.
# Python code to demonstrate working of # nlargest() and nsmallest() # importing "heapq" to implement heap queue import heapq # initializing list li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1] # using heapify() to convert list into heap heapq.heapify(li1) # using nlargest to print 3 largest numbers # prints 10, 9 and 8 print("The 3 largest numbers in list are : ",end="") print(heapq.nlargest(3, li1)) # using nsmallest to print 3 smallest numbers # prints 1, 3 and 4 print("The 3 smallest numbers in list are : ",end="") print(heapq.nsmallest(3, li1)) |
Output :
The 3 largest numbers in list are : [10, 9, 8] The 3 smallest numbers in list are : [1, 3, 4] ###################################DEQUEUE#######################################
# Python code to demonstrate working of # append(), appendleft(), pop(), and popleft() # importing "collections" for deque operations import collections # initializing deque de = collections.deque([1,2,3]) # using append() to insert element at right end # inserts 4 at the end of deque de.append(4) # printing modified deque print ("The deque after appending at right is : ") print (de) # using appendleft() to insert element at right end # inserts 6 at the beginning of deque de.appendleft(6) # printing modified deque print ("The deque after appending at left is : ") print (de) # using pop() to delete element from right end # deletes 4 from the right end of deque de.pop() # printing modified deque print ("The deque after deleting from right is : ") print (de) # using popleft() to delete element from left end # deletes 6 from the left end of deque de.popleft() # printing modified deque print ("The deque after deleting from left is : ") print (de) |
5. index(ele, beg, end) :- This function returns the first index of the value mentioned in arguments, starting searching from beg till end index.
6. insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i)specified in arguments.
7. remove() :- This function removes the first occurrence of value mentioned in arguments.
8. count() :- This function counts the number of occurrences of value mentioned in arguments.
# Python code to demonstrate working of # insert(), index(), remove(), count() # importing "collections" for deque operations import collections # initializing deque de = collections.deque([1, 2, 3, 3, 4, 2, 4]) # using index() to print the first occurrence of 4 print ("The number 4 first occurs at a position : ") print (de.index(4,2,5)) # using insert() to insert the value 3 at 5th position de.insert(4,3) # printing modified deque print ("The deque after inserting 3 at 5th position is : ") print (de) # using count() to count the occurrences of 3 print ("The count of 3 in deque is : ") print (de.count(3)) # using remove() to remove the first occurrence of 3 de.remove(3) # printing modified deque print ("The deque after deleting first occurrence of 3 is : ") print (de) |
########################HEAP###################################
# Python code to demonstrate working of
# heapify(), heappush() and heappop()
# importing "heapq" to implement heap queue
import heapq
# initializing list
li = [5, 7, 9, 1, 3]
# using heapify to convert list into heap
heapq.heapify(li)
# printing created heap
print ("The created heap is : ",end="")
print (list(li))
# using heappush() to push elements into heap
# pushes 4
heapq.heappush(li,4)
# printing modified heap
print ("The modified heap after push is : ",end="")
print (list(li))
# using heappop() to pop smallest element
print ("The popped and smallest element is : ",end="")
print (heapq.heappop(li))
###################################DEQUEUE#######################################
# importing "collections" for deque operations
import collections
# initializing deque
de = collections.deque([1,2,3])
# using append() to insert element at right end
# inserts 4 at the end of deque
de.append(4)
# printing modified deque
print ("The deque after appending at right is : ")
print (de)
# using appendleft() to insert element at right end
# inserts 6 at the beginning of deque
de.appendleft(6)
# printing modified deque
print ("The deque after appending at left is : ")
print (de)
# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()
# printing modified deque
print ("The deque after deleting from right is : ")
print (de)
# using popleft() to delete element from left end
# deletes 6 from the left end of deque
de.popleft()
# printing modified deque
print ("The deque after deleting from left is : ")
print (de)
################################
import heapq
l=[5,7,2,4,9]
heapq.heapify(l)
print(l)
heapq.heappush(l,0)
print(l)
heapq.heappush(l,-5)
print(l)
heapq.heappop(l)
print(l)
heapq.heappop(l)
print(l)
####################
Named tuple
# Python code to demonstrate namedtuple() and
# Access by name, index and getattr()
# importing "collections" for namedtuple()
import collections
# Declaring namedtuple()
Student = collections.namedtuple('Student',['name','age','DOB'])
# Adding values
S = Student('Nandini','19','2541997')
# Access using index
print ("The Student age using index is : ",end ="")
print (S[1])
# Access using name
print ("The Student name using keyname is : ",end ="")
print (S.name)
######################
>> d=cl.deque([1,2,3,4])
>>> print(d)
deque([1, 2, 3, 4])
>>> d.append(5)
>>> print(d)
deque([1, 2, 3, 4, 5])
>>> d.pop(5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: pop() takes no arguments (1 given)
>>> d.pop()
5
>>> print(d)
deque([1, 2, 3, 4])
>>> d.appendleft(5)
>>> print(d)
deque([5, 1, 2, 3, 4])
>>> d.popleft()
5
>>> print(d)
deque([1, 2, 3, 4])
>>>
############
HEAP
#######
>> hq.heapify(l)
>>> hq.heappush(l,5)
>>> hq.heappop(l)
1
>>> hq.heappop(l)
2
>>> hq.heappop(l)
3
>>> hq.heappop(l)
4
>>> hq.heappop(l)
5
>>> hq.heappop(l)
7
>>> hq.heappop(l)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
##############NAMED TUPLE#################
>>> l=cl.namedtuple('l',('name','age'))
>>> l2=l('abc',12)
>>> print(l2)
l(name='abc', age=12)
>>> l['name]
File "<stdin>", line 1
l['name]
^
SyntaxError: EOL while scanning string literal
>>> l2['name]
File "<stdin>", line 1
l2['name]
^
SyntaxError: EOL while scanning string literal
>>> l2['name']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: tuple indices must be integers or slices, not str
>>> l2[0]
'abc'
>>> l2[1]
12
>>>