Python Advanced Data Types

from collections import deque
q = deque()          # empty
q = deque([1, 2, 3]) # with values
q.append(4)     # append to right side
q.appendleft(0) # append to left side
print(q)    # => deque([0, 1, 2, 3, 4])
x = q.pop() # remove & return from right
y = q.popleft() # remove & return from left
print(x)    # => 4
print(y)    # => 0
print(q)    # => deque([1, 2, 3])
q.rotate(1) # rotate 1 step to the right
print(q)    # => deque([3, 1, 2])

Deque is a double-ended queue with O(1) time for append/pop operations from both sides. Used as stacks and queues. See: Deque

import heapq
myList = [9, 5, 4, 1, 3, 2]
heapq.heapify(myList) # turn myList into a Min Heap
print(myList)    # => [1, 3, 2, 5, 9, 4]
print(myList[0]) # first value is always the smallest in the heap
heapq.heappush(myList, 10) # insert 10
x = heapq.heappop(myList)  # pop and return smallest item
print(x)                   # => 1

#Negate all values to use Min Heap as Max Heap

myList = [9, 5, 4, 1, 3, 2]
myList = [-val for val in myList] # multiply by -1 to negate
heapq.heapify(myList)
x = heapq.heappop(myList)
print(-x) # => 9 (making sure to multiply by -1 again)

Heaps are binary trees for which every parent node has a value less than or equal to any of its children. Useful for accessing min/max value quickly. Time complexity: O(n) for heapify, O(log n) push and pop. See: Heapq