标签：heapq python Tree -- 二叉树 heap 数据结构 节点
数据结构
栈 --> stack
队列 --> queue
树 --> tree
堆 --> heap
散列 --> hash
图 --> graph 图结构一般包括顶点和边 邻接矩阵 DAG,Directed Acyclic Graph即「有向无环图」
树
树（Tree）是一种非线性的数据结构，
由n个节点组成，其中每个节点都有零个或多个子节点。
树结构中包括一个根节点，该节点没有父节点，以及其他节点，每个节点最多只有一个父节点
根节点 父节点 子节点 叶子节点
兄弟节点 祖先节点
每个元素称为结点（node） root subtree
概念
Height
层次 高度 深度
层次： 根节点层次为1，每向下一层，层次就加1
高度： 节点的高度是该节点到叶子节点的最长路径
深度： 从根节点到该节点的距离称为节点的深度
度 Degree
度： 节点下面子节点的数量称为节点的度（分支的数量），所有节点的度中最大的度称为树的度
二叉树
二叉树是一种特殊的树，二叉树中每个节点的度都不能大于2
满二叉树
完全二叉树
二叉树的代码实现
二叉树的遍历
前序遍历 -根-左-右
中序遍历 -左-根-右
后序遍历 -左-右-根
层序遍历:遍历规则：从根节点开始，按照从上到下、从左到右的顺序逐层访问节点
二叉树中能够实现: 快速插入、删除 查找
二叉查找树(Binary Search Tree,BST),又叫做二叉排序树、二叉搜索树
红黑树(Red-Black Tree)也是是一种自平衡的二叉搜索树,与AVL树不同的是它在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black
数据结构中的堆 heap
堆（Heap）是一种基于二叉树结构的数据结构。与内存中的堆不同，此处的堆是指堆数据结构
相互之间的转换
树转换为二叉树
森林转换成二叉树
哈夫曼树(Huffman Tree) 用于信息编码
最小生成树(Minimum Spanning Tree)
线段树(Segment Tree)
应用
数据库中非常核心的一个部分，就是索引结构的设计——这几乎决定了数据库的应用领域
B 树也属于一种自然平衡树。内部通过分裂机制，能够保持数据的有序
B+树的节点中也包含了多个信息
日志结构化合并树（Log Structured Merge Tree）
查看是什么
## pip install binarytree
from binarytree import tree, bst, heap
from binarytree import Node
#非满二叉树相对于满二叉树“缺失”的节点索引号是跳空的。
## treelib
## Python heapq模块是Python标准库的一部分
Python heapq模块可以用于在大型数据集中查找最大或最小的元素，它可以在O(log n)时间内完成查找操作。
heapq 的全写是heap queue，是堆队列的意思。这里的堆和队列都是数据结构
import heapq
nums = [14, 20, 5, 28, 1, 21, 16, 22, 17, 28]
heapq.nsmallest(3, nums)
heapq.nlargest(3, nums)
## 自定义排序 自己定义一个获取关键字的函数，传递给heapq，这样才可以完成排序
# 额外传递了一个参数key，我们传入的是一个匿名函数
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
## heapq.heapify方法，输入一个数组，返回的结果是根据这个数组生成的堆（等价于优先队列）
heapify(x)：将常规列表x转换为堆队列
提供的功能有哪些
numpy只提供了argpartition 和 partition，
实现以及分析复杂度
操作的复杂度--时间复杂度和空间复杂度
python 迁移学习C++
STL：the C++ Standard Template Library，C++ 标准模板库
参考
图解！24张图彻底弄懂九大常见数据结构 https://cloud.tencent.com/developer/article/1634155
https://blog.csdn.net/qq_19707521/article/details/128393983 Pytorch/Paddle topk 与 Numpy argpartition 函数应用
标签：heapq,
python,
Tree,
--,
二叉树,
heap,
数据结构,
节点
From： https://www.cnblogs.com/ytwang/p/17899108.html