江苏龙网

  1. 主页 > 生活百科 > >

每个程序员都必须知道的8种数据结构( 三 )

数据结构


文章插图
 
Fig 8. Array Representation of a Heap
 
堆可以有2种类型 。
· 最小堆-父项的密钥小于或等于子项的密钥 。这称为min-heap属性 。根将包含堆的最小值 。
· 最大堆数-父项的密钥大于或等于子项的密钥 。这称为max-heap属性 。根将包含堆的最大值 。
堆的应用· 用于实现优先级队列，因为可以根据堆属性对优先级值进行排序 。
· 可以在O（log n）时间内使用堆来实现队列功能 。
· 用于查找给定数组中k个最小（或最大）的值 。
· 用于堆排序算法 。
8.图一个图由一组有限的顶点或节点以及一组连接这些顶点的边组成 。
图的顺序是图中的顶点数 。图的大小是图中的边数 。
如果两个节点通过同一边彼此连接，则称它们为相邻节点 。
有向图如果图形G的所有边缘都具有指示什么是起始顶点和什么是终止顶点的方向，则称该图形为有向图 。
我们说（u，v）从顶点u入射或离开顶点u，然后入射到或进入顶点v 。
自环：从顶点到自身的边 。
无向图如果图G的所有边缘均无方向，则称其为无向图 。它可以在两个顶点之间以两种方式传播 。
如果顶点未连接到图中的任何其他节点，则称该顶点为孤立的 。

每个程序员都必须知道的8种数据结构

文章插图
 
Fig 9. Visualization of Terminology of Graphs
图的应用· 用于表示社交媒体网络 。每个用户都是一个顶点，并且在用户连接时会创建一条边 。
· 用于表示搜索引擎的网页和链接 。互联网上的网页通过超链接相互链接 。每页是一个顶点，两页之间的超链接是一条边 。用于google中的页面排名 。
· 用于表示GPS中的位置和路线 。位置是顶点，连接位置的路线是边 。用于计算两个位置之间的最短路径 。
参考文献[1]算法简介，第三版，作者：托马斯·H·科门（Thomas H. Cormen），查尔斯·E·雷森（Charles E. Leiserson），罗纳德·L·里维斯特（Ronald L. Rivest）和克利福德·斯坦（Clifford Stein） 。
[2]来自Wikipedia的数据结构列表
(本文翻译自Vijini Mallawaarachchi的文章《8 Common Data Structures every Programmer must know》，参考：https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42)




推荐阅读


上一篇：手环心率监测靠谱吗？背后的科学原理3分钟科普

下一篇：李世民是怎样对待李渊 李世民玄武门之变后对李渊做了什么