锐客网

  1. 首页 > 生活百科 > it技术 > >

高级数据结构

IT知识数据结构数据

提兵百万西湖上，立马吴山第一峰！这篇文章主要讲述高级数据结构相关的知识，希望能为你提供帮助。
目录

优先队列
图
前缀树
线段树
树状数组
总结

前言
常用的高级数据结构：
优先队列????Priority Queue)
图(Graph)
前缀树(Trie)
????线段树(Segment Tree)
????树状数组(Fenwick Tree/Binary Indexed Tree)


内容
优先队列与普通队列的区别：
保证每次取出的元素是队列中优先级最高的
优先级别可自定义
最常用的场景：
从杂乱无章的数据中按照一定的顺序(或者优先级)筛选数据。
例如：
任意给定一个数组，要求找出前k大的数。
最直接的办法就是先对这个数组进行排序，然后依次输出前k大的数。复杂度为O(nlogn)
如果借用优先队列就能将复杂度优化为O(k+nlogk)。
当数据量很大，而k相对较小时，用优先队列能显著地降低算法复杂度。其本质在于，要找出前k大的数，我们并不需要对所有的数进行排序。
优先队列的本质：
二叉堆的结构，堆在英文里叫Binary Heap
利用一个数据结构来实现完全二叉树。
即，优先队列的本质是一个数组，数组里的所有元素既有可能是其他元素的父节点，也有可能是其他元素的子节点。而且每个父节点只能有两个子节点。
优先队列的特性：
  • 数组里的第一个元素array[0]拥有最高的优先级
  • 给定一个下标i，那么对于元素array[i]而言
  • 父节点对应的元素下标是(i-1)/2
  • 左侧子节点对应的元素下标是2i+1
  • 右侧子节点对应的元素下标是2i+2
  • 数组中每个元素的优先级都必须高于它两侧子节点
优先队列的基本操作为以下两个
  • 向上筛选(sift up/bubble up)，时间复杂度为O(logk)
  • 向下筛选(sift down/bubble down)，时间复杂度为O(logk)
  • 另一个最重要的时间复杂度：优先队列的初始化。将n个数据创建为一个大小为n的优先队列，初始化的时间复杂度，如下图所示，经过进一步的推导，其时间复杂度为O(n)。
  • 即，初始化一个大小为n的堆，其时间复杂度为O(n)。



图图为所有的数据结构中，知识点最丰富的一个。
图的最基本知识点如下:
阶、度
树、森林、环
有向图、无向图、完全有向图、完全无向图
连通图、连通分量
图的存储和表达方式：邻接矩阵、邻接链表
围绕图的算法也是各式各样
  • 图的遍历：深度优先、广度优先
  • 环的检测：有向图、无向图
  • 拓扑排序
  • 最短路径算法：Dijkstra, Bellman-Ford、Floyd Warshall
  • 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树
  • 图的着色、旅行商问题等
必须熟练掌握的知识点
图的存储和表达方式：邻接矩阵、邻接链表
图的遍历：深度优先、广度优先
二部图的检测(Bipartite)、树的检测、环的检测：有向图、无向图
拓扑排序
联合-查找算法(Union-Find)
最短路径：Dijkstra、Bellman-Ford
前缀树也称字典树
这种数据结构被广泛地运用在字典查找当中
什么是字典查找？
例如：给定一系列构成字典的字符串，要求在字典当中找出所有以“ABC”开头的字符串
  • 方法一：暴力搜索法，假设总共有n个单词，要查找的开头字符串长度为m
  • 时间复杂度： O(m*n)
  • 方法二：前缀树，假设m为字典里最长的单词的字符个数
  • 时间复杂度：O(m)
在很多情况下，字典里的n> > m，因此前缀树在此时非常高效。
前缀树的经典应用
搜索框输入搜索文字，会罗列以搜索词开头的相关搜索信息。
汉语拼音输入法，其联想功能就用到了前缀树。
前缀树的重要性质：
每个节点至少包含两个基本属性：
children: 数组或者集合，罗列出每个分支当中包含的所有字符
isEnd: 布尔值，表示该节点是否为某字符串的结尾
根节点是空的
除了根节点，其他所有节点都可能是单词的结尾，叶子结点一定都是单词的结尾
前缀树的最基本操作：
  • 创建
  • 搜索
创建的方法：
  • 遍历一遍输入的字符串，堆每个字符串的字符进行遍历
  • 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中
  • 如果字符集已经包含了这个字符，跳过
  • 如果当前字符是字符串的最后一个，把当前节点的isEnd标记为真
搜索的方法：
  • 从前缀树的根节点出发，逐个匹配输入的前缀字符串
  • 如果遇到了，继续往下一层搜索
  • 如果没遇到，立即返回



线段树先从一个例题出发
假设有一个数组array[0…n-1]，里面有n个元素，现在我们要经常对这个数组做两件事：
  • 更新数组元素的数值
  • 求数组任意一段区间里元素的总和（或者平均值）
  • 方法一：遍历一遍数组时间复杂度：O(n)
  • 方法二：线段树时间复杂度：O(logn)
什么是线段树
一种按照二叉树的形式存储数据的结构，每个节点保存的都是数组里某一段的总和










树状数组也被称为Binary Indexed Tree
先从一个例题出发
假设有一个数组array[0…n-1]，里面有n个元素，现在我们要经常对这个数组做两件事：


更新数组元素的数值
求数组前k个元素的总和(或者平均值)
方法一：线段树
时间复杂度：O(logn)
方法二：树状数组
时间复杂度：O(logn)，
而且树状数组比线段树显得更简单
树状数组的重要基本特征：
利用数组来表示多叉树的结构，和优先队列有些类似
优先队列是用数组来表示完全二叉树，而树状数组是多叉树
树状数组的第一个元素是空节点
如果节点tree[y]是tree[x]的父节点，那么需要满足y=x-(x& (-x))


总结优先队列：常见面试考点，实现过程比较繁琐。在解决面试中的问题时，实行“拿来主义”即可
图：被广泛运用的数据结构，如大数据问题都得运用图论
在社交网络中，每个人可以用图的顶点表示，人与人直接的关系可以用图的边表示
在地图上，要求解从起始点到目的地，如何行使会更快捷，需要运用图论里的最短路径算法
前缀树：出现在面试的难题中，要求能熟练地书写它的实现以及运用
线段树和树状数组：应用场合比较明确
如果要求在一幅图片中修改像素的颜色，求解任意矩形区间的灰度平均值则需要采用二维的线段树
二分搜索二分搜索的优点：
二分搜索也称对数搜索，其时间复杂度为O(logn)，是一种非常高效的搜索
二分搜索的缺点：
要求带查找的数组或区间是排序的
-若要求对数组进行动态地删除和插入操作并完成查找，平均复杂度会变为O(n)
-采取自平衡的二叉查找树
----可在O(nlogn)的时间内用给定的数据结构构建出一棵二叉查找树
----可在O(logn)的时间内对数据进行搜索
----可在O(logn)的时间内完成删除和插入的操作
当输入的数组或区间是有序的，且不会常变动，要求从中找出一个满足条件的元素——采用二分搜索
二分搜索的节本解题模板
递归
非递归
二分搜索的递归
优点是简洁
缺点是执行消耗大



面试题给定一个非空的整数????数组，返回其中出现频率前 k 高的元素。
示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

代码
class Solution
public:
vector topKFrequent(vector& nums, int k)
unordered_map Map; //unordered_map：哈希表 map：红黑树
for(int i=0; iMap[nums[i]]++;

priority_queue,vector> ,greater> > Q;
unordered_map::iterator it;
for(it=Map.begin(); it!=Map.end(); it++)
if(Q.size()==k)
if(it-> second> Q.top().first)
Q.pop();
Q.push(make_pair(it-> second,it-> first));

else
Q.push(make_pair(it-> second,it-> first)); //第一个是频率，第二个是数字


vector res;
while(!Q.empty())
res.push_back(Q.top().second);
Q.pop();

reverse(res.begin(), res.end());
return res;

;

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

3
/ \\
920
/\\
157

代码
/**
* Definition for a binary tree node.
* struct TreeNode
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL)
* ;
*/
class Solution
public:
TreeNode* buildTree(vector& preorder, vector& inorder)
//递归出口
if(preorder.empty() || inorder.empty())
return NULL;
//建立二叉树
TreeNode *head = new TreeNode;
head-> val = preorder[0];
//找到根节点的位置
int root = 0;
for(int i=0; i
if(preorder[0]==inorder[i])
root = i;
break;


// 先序遍历和中序遍历的左右子树vector
vector left_pre,left_in,right_pre,right_in;
for(int i=0; ileft_pre.push_back(preorder[i+1]);
left_in.push_back(inorder[i]);

for(int i=root+1; i
right_pre.push_back(preorder[i]);
right_in.push_back(inorder[i]);


// 根节点的左右节点
head-> left = buildTree(left_pre,left_in);
head-> right = buildTree(right_pre,right_in);
return head;

;

改进
/**
* Definition for a binary tree node.
* struct TreeNode
*int val;
*TreeNode *left;
*TreeNode *right;
*TreeNode(int x) : val(x), left(NULL), right(NULL)
* ;
*/
class Solution
public:
unordered_map map;
TreeNode* buildTree(vector& preorder, vector& inorder)
// 将中序序列用哈希表存储，便于查找根节点
for(int i = 0; i < inorder.size(); i++)
map[inorder[i]] = i;
// 传入参数：前序,中序，前序序列根节点，中序序列左边界，中序序列右边界
return build(preorder,inorder,0,0,inorder.size()-1);

TreeNode* build(vector& preorder, vector& inorder,int pre_root,int in_left,int in_right)
if(in_left > in_right)
return NULL;
TreeNode* root = new TreeNode(preorder[pre_root]);
// 根节点在中序序列中的位置，用于划分左右子树的边界
int in_root = map[preorder[pre_root]];
// 左子树在前序中的根节点位于：pre_root+1,左子树在中序中的边界：[in_left,in_root-1]
root-> left = build(preorder,inorder,pre_root+1,in_left,in_root-1);
// 右子树在前序中的根节点位于：根节点+左子树长度+1 = pre_root+in_root-in_left+1
// 右子树在中序中的边界：[in_root+1,in_right]
root-> right = build(preorder,inorder,pre_root+in_root-in_left+1,in_root+1,in_right);
return root;

;



class Solution
public:
TreeNode* buildTree(vector& preorder, vector& inorder)
if(preorder.empty()) return nullptr;
stack s;
TreeNode *root=new TreeNode(preorder[0]); //根节点
TreeNode *cur=root; //正在确定位置的节点
for(int i=1,j=0; i
//有左子树的情况，一直沿左子树深入，并将沿途节点放入栈中
if (cur-> val != inorder[j])//inorder[j]代表最左节点（去除已经确定左子树的节点）
cur-> left = new TreeNode(preorder[i]);
s.emplace(cur);
cur = cur-> left;
else//没有左子树的情况
j++;
while (!s.empty() & & s.top()-> val == inorder[j])//栈顶是其父节点，判断有无右子树
cur = s.top(); //没有右子树，就追溯到有右节点的祖父节点
s.pop();
j++;

cur = cur-> right = new TreeNode(preorder[i]); //preorder[i]即当前节点的右子树节点，并且下次从右子树开始遍历


return root;

;




















【高级数据结构】


    推荐阅读


    上一篇：HCIA-Datacom 网络层_ICMP协议

    下一篇：Adobe XD 2022软件安装包和安装教程