Python_数据结构的应用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 函数应用