常见的数据结构有

序列（列表、链表，元祖，队列，二叉树、堆、栈）、图、集合、字典

序列

查询序列中元素出现次数的方法:collections.Counter(LIST).most_common(TOP3);可用于计数的场景；
序列分组：通过特定的元素，对序列或者字典分组；使用itertools.groupby()使用前要先对序列排序；
对序列的下标/索引重命名：collections.namedtuple()；这种感觉是让序列有了字典的特性；
实现：线性数据结构/链表数据结构；如下：
- 顺序存储：[]这种线性关系的特定是；查询快O(1)，插入/删除慢O(N)
- 链表
  - 实现：self.next=null
  - 特点：链式存储：当前节点含下个节点的指针，这个特定是写(add/update)快O(1),读/删很慢O(N)其他特性；单向链表/双向链表（每个节点既保留了下一个的指针，还保留了上一个节点的指针）/快指针/慢指针；
列表推导/生成器表达式：两者都能用来过滤可迭代对象；列表推导生成的对象是列表，而生成式，生成的是可迭代对象；因此列表推动会占用更更多的内存（因为要覆盖整个列表），而生成器表达式只有在调用时，才提供元素，因此他性能更优，但他只能使用一次，列表推导可反复使用；除了用于序列，还能用于hashmap；
sum/min/max函数中都可以放置生成器表达式如sum(x for i in l)
其他的序列过滤工具：filter(fun(),iterable)/itertools.compress(iterable,Boolean)Boolean是元素为TRUE/FALSE的序列，根据是否为true过滤对应位置的iterable的值；两个工具处理后的结果都是可迭代对象需要通过list(iterable)来转化为序列;

字符串

实现：str()/‘str’
特点：字符串类似列表，不过其中的元素不可变，且只能为字符，他有序列的所有特点；底层是线性的数据结构，可以通过数组或者链表实现；

列表

实现：list()/[]
特点：列表是最常见的线性表，数据元素都是首尾相接的（内存结构是连续的，且事先分配固定长度的内存，可在之后动态调整）；
二叉树
实现：二叉树用list表示，[根节点，左节点，右节点]
特点：I为当前层；当前层节点数（2^(n-1)）;总节点数2^n-1;二叉树的父节点，维护子节点的指针；二叉树的特性类似于链表，每个跟节点都有指针，指向左右节点；二叉树在列表中的分布逻辑如下：

在索引从0（根节点）开始的数组中：
  父节点 i 的左子节点在位置(2*i+1)
  父节点 i 的右子节点在位置(2*i+2)
  子节点 i 的父节点在位置floor((i-1)/2)

二叉树遍历的方式有两种：

1
2
3

深度优先：前序，中序，后序
广度优先：从跟节点开始遍历，然后到下一级子节点，一直递归直到最下层子节点；(类似于数组构造，但数据也支持深度遍历)
二叉树是以列表展示，以栈逻辑的方式组织数据，这是由于，最先出去的一定是最底层的左节点子树；可以通过以上的遍历方式来以不同的效率查找到数据

不同的二叉树：
- 二叉查找树：父节点的键（索引）大于左子节点，小于右子节点；
- 满二叉树：每个内部节点（非叶子节点）都有两个子节点的树；
- 完全二叉树：所有叶子节点在同一层的，满二叉树；有标号（索引）的二叉树，根节点为索引0（列表中），左子节点加1，右子节点加2；

队列

实现：[]

特点：先进先出（双端队列不是）；底层是线性的数据结构，可以通过数组或者链表实现

类型：优先队列/双端队列

优先队列：使用二叉堆实现
  实现：heapq.heapify(queue)/heapq.push(queue, e)/heapq.pop(queue)/queue[0]
  特点：查询快，时间复杂度O(1)
双端队列：可以在两端操作
  实现：dq = collections.deque();dq.appendleft(e)，dq.popleft()，dq[0]
  特点：可通过两边操作，左右两端操作快，添加/弹出/查询的时间复杂度都是O(1)

堆

实现：[];物理结构为数组，逻辑结构为完全二叉树;

特点：数据结构类似完全二叉树；堆有两种数据组织方式；根节点最大（且父节点均大于子节点）的为大根堆，跟节点最小（且父节点均小于子节点）的为小根堆；二叉树，一定满足左子节点，小于右子节点；且最底层的左叶子节点值、优先级一定最小，且最早弹出

大根堆/小根堆常用来处理数据优先级问题；原理是由于堆[]最先出的是[-1]的值，因此大根堆，最大优先级的最先出，小根堆正好相反；具体实现

heapq.heappush([], (-priority, self._index, item))

//priority优先级，由于堆默认弹出最小优先级，index是在优先级相同时，通过索引判断优先级
              >>> q.push(Item('foo'), 1)
              >>> q.push(Item('bar'), 5)
              >>> q.push(Item('spam'), 4)
              >>> q.push(Item('grok'), 1)
              >>> q.pop()
              Item('bar')
              >>> q.pop()
              Item('spam')
              >>> q.pop()
              Item('foo')
              >>> q.pop()
              Item('grok')
          可用来对列表进行排序，将其转换成大根堆/小根堆；

栈

实现：[]、或使用队列实现collections.deque()
特点：先进后出；底层的数据结构可以是数组或者双端队列；

元组

实现：（*，）
特点：线性序列；序列不可变；

图

图是多对对的非线性数据关系，可以用列表，字典，集合实现；

字典/hash_map

实现：dict()、｛key:value,｝
特点：无序的键值对（底层是动态数据和一个哈希函数构成），且key不能重复；查询块O(1),添加/删除/改很快O(1)
- 有顺序关系的字典：Orderdict();他维护了一个双向链表，用来指示键的顺序，新加入的键放在双向链表的最后
- 以上是对字典内部的排序，字典间的排序可以使用（sorted(dicts,key=itemgetter(‘lname’,’fname’))）,利用itemgetter指定排序模式；同时min/max函数也支持（min(rows, key=itemgetter(‘uid’))）
- 以上的sort排序还可以用来对不支持排序的对象进行排序如对类或者函数排序（sorted(users, key=lambda u: u.user_id)）；同样他也适用于min/max函数；
- 单个键，有多个值的字典：defaultdict(list/set)这是建多值字典的方法即｛k:[1,2]｝
- 字典的运算：注意运算是针对键的，如果要针对值则需要转换，如sort(zip(dict.vaule,dict.key))
- 字典&集合：字典可以理解成键集合和值集合的映射关系；因此字典的dict.key和dict.item均可以执行集合的逻辑操作
- 合并多个字典：c = collections.ChainMap(dict1,dict2),c其实是创建多个列表来维护这些字典的键和值，不是真的合并；这个对象查询相同键时，查到的是最先出现的键值，更新/删除数据操作，只能在第一个字典中生效；还能用dict1.update(dict2)合并字典；
- 以上两种方法的区别，ChainMap是维护了一个数组，来建立key:value关系，不新建字典，变动会两端同步；update方法执行完后建立一个完全独立的新字典，和旧字典互不影响；

set

实现：set()、｛*，｝
特点：确定，无序，元素不重复（底层也是hash实现的），类似于只有key的hash,查询慢O(N),添加/删除/改很快O(1)

查看对象占用的内存大小：sys.getsizeof()

教程
浙大-数据结构课程-完整
 github-算法快速教程-快
 GitHub-算法示例大全-Python版
可视化工具
新加坡国立大学算法可视化工具
 数据结构可视化工具

Bu Jia Ban

算法--数据结构1️⃣

常见的数据结构有

序列

字符串

列表

二叉树

队列

堆

栈

元组

图

字典/hash_map

set