This blog will introduce **deque**, **bisect**, **defaultdict**, **Counter**, **OrderedDict**, **heapq**. For every data structure, I’ll introduce their basic knowledge, example code and LeetCode problems. The four basic inbuilt data structures (Lists, Dictionary, Tuple, and Sets) can be learned from GeeksforGeeks.

Of course, this blog won’t cover all useful functions or data structures. I’ll update this article when I find more useful data structures.

The best way to understand these data structures is to read official documents. You can access these websites by click titles. However, to avoid people being overwhelmed by massive information, this article will only cover the most significant knowledge.

## deque

“deque” is the abbreviation of “double-ended queue”[wikipedia]. The queue operations (push/pop) can be operated on both the head and tail of “deque” list. The time complexity of operations is O(1).

You should import `collections`

library to use `deque`

. The functions of deque are shown below.

1 | from collections import deque |

These functions are easy to understand from their name. If you learned Lists, all of the above functions can be implemented by List. So, **why we need deque?**

The document explains it in below.

Though

`list`

objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for`pop(0)`

and`insert(0, v)`

operations which change both the size and position of the underlying data representation.

It seems like there are some optimizations in deque for `appendleft`

and `popleft`

operations. Let’s do some tests!

1 | # Test1: list.pop(0) |

1 | # Test2: deque.popleft() |

**128.42 sec** VS **0.05 sec** !!!

Now, you know the difference. You can paractice it by LeetCode shown below.

**Practice:** LeetCode 102. Binary Tree Level Order Traversal

## Counter

`Counter`

is another class in the `collections`

library. A `Counter`

is a `dict`

subclass for counting hashable objects. Therefore, you can call all functions in `dict`

. Besides, specific functions for `Counter`

are listed below.

1 | from collections import Counter |

**Practice**: LeetCode 169. Majority Element ; LeetCode 242. Valid Anagram

## OrderedDict

`OrderedDict`

is a dictionary that remembers insertion order. Because it’s a `dict`

subclass, all of the functions of `dict`

can be used in `OrderedDict`

either. Unlike the unsorted keys in `dict`

, keys of `OrderedDict`

is sorted by insertion order from early to late. Specific functions are shown below.

1 | from collections import OrderedDict |

**Practice**: LeetCode 146. LRU Cache

## defaultdict

`defaultdict`

is a `dict`

subclass that calls a factory function to supply missing values. `dict`

class will raise `KeyError`

exception if an unexistence key is used. To avoid such an error, we can use `defaultdict`

. The example of the class is shown below.

1 | from collections import defaultdict |

**Practice**: LeetCode 212. Word Search II

## heapq

“`heapq`

“ is an implementation of the heap queue. The knowledge of heap can be found in the GeeksforGeeks and Wikipedia). Cited from GeeksforGeeks

Max-Heap(Min-Heap): In a Max-Heap (Min-Heap) the key present at the root node must be greatest (minimum) among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

The basic operations of heap include build empty heap, insert new element, get the top element, delete the top element. The time complexity of operations are O(n), O(log n), O(1), O(log n) respectively.

The implementation of `heapq`

is shown below (cited from the official document).

This implementation uses arrays for which

`heap[k] <= heap[2*k+1]`

and`heap[k] <= heap[2*k+2]`

for allk, counting elements from zero. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that its smallest element is always the root,`heap[0]`

.

There are some examples for `heapq`

functions.

1 | import heapq |

You can also learn the use case of `heapq`

, like the implementation of priority queue and theory in the official document.

**Practice**: LeetCode 703. Kth Largest Element in a Stream

## bisect

Citation from official document

This module provides support for maintaining a list in sorted order without having to sort the list after each insertion.

Bisection method is one of the most commonly used methods. For searching an element in the sorted array, the time complexity of bisection searching is O(log n). Even if the implementation of bisection is simple, implementing it everywhere is cumbersome and inelegant.

The `bisect`

library provides a standard way to do it. Functions of `bisect`

are shown below.

1 | import bisect |

Some interesting use cases of `bisect`

are introduced in the official document.