Leon Ding Blog - 数据结构
type: channel
link: https://blog.leonding.me/category/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95.html
description: 收录数据结构与算法相关文章
items: 基于 LogStructuredFS 的 NoSQL 设计与实现
items: 哈希算法的实践
items: 计算机中的二进制位
items: Go 范型的实践
items: 二分查找算法
items: 堆排序定时器实现
items: 非线型结构之树

基于 LogStructuredFS 的 NoSQL 设计与实现
type: item
date: 2024-12-22T23:45:00+08:00
description: NoSQL 的抽象数据库系统的核心作用在于高效地存储和管理数据，并支持从海量信息中快速检索所需记录。传统的 SQL 关系型数据库在数据规模持续增长的情况下，容易遭遇单机性能瓶颈。目前提升性能的主流做法多依赖垂直扩展增强单机硬件能力，而非水平扩展增加节点以线性扩容。由于其架构限制，关系型数据库在弹性扩展性方面存在障碍，难以充分适应多节点分布式环境。同时为满足 ACID 事务特性，这类系统在支持分布式事务处理时也面临一定的技术挑战。相比之下，NoSQL 数据库更适用于大规模数据存储和高吞吐、低延迟的应用场景。由于 NoSQL 不受固定数据结构和关系的限制，具有更灵活的扩展能力，并且支持节点的动态扩展，从而更好地适应分布式环境。无论是关系型 SQL 数据库还是 NoSQL 数据库，它们都有一个共同的核心组件存储引擎，这是数据库设计与实现的关键核心部分。目前数据库存储引擎可以分为两大类，一类是基于内存的 （In-Memory）实现，例如 Redis 和 Memcached 这类的将数据全部存储在内存中；另外一种则是类似于 MySQL 的 InnoDB 和 LevelDB 这种将数据存储在磁盘中。两者都有各自的优势和劣势，基于内存的存储引擎通常存储的数据量较少，但其访问速度往往比基于磁盘的存储引擎快好几个数量级，而基于磁盘的存储引擎访问速度较慢，但存储数据量要比内存引擎多几个数量级。通常内存的价格要比磁盘的贵很多，这也是在选择存储硬件时要考虑的成本问题。存储引擎的开发者需要权衡读写性能和硬件成本的同时，重点在于如何高效存储数据和检索数据。数据库的存储引擎相当于在操作系统文件系统之上，建立的一套用于数据组织、存储与查询的逻辑管理层，最终实现是依赖于操作系统的文件系统 API 接口的，最终数据是被持久化到磁盘文件中保存，这个就对应着 ACID 中的 Durability 数据持久性。持久性（Durability）是存储引擎最为至关重要的功能实现，目前很多基于内存版本的 NoSQL 数据库例如 Memcached 和 Redis 在这方面做的就比较差，在 NoSQL 服务器运行过程中突然崩溃断电就会导致数据没有被持久化存储的情况，从而导致数据丢失影响到上层的业务程序。[scode type="yellow"]所谓的持久性就是如何将计算机运算的结果持久化存储在一些物理介质中；持久性是指系统能够将状态变更的结果可靠保存，使其在系统重启或故障后仍然能够恢复。 [/scode]存储是现代计算机最核心的功能之一，计算机中的程序和文件以数据块的形式保存在各种存储介质中，主要可分为持久化存储和非持久化存储两类。非持久化存储通常指内存（如 RAM），其特点是在断电或关机后，数据会被清除。尽管容量通常小于持久化存储，但其高速读写性能使其广泛应用于程序运行过程中的数据处理和临时缓存。相比之下，持久化存储如硬盘、固态硬盘、DVD、磁带等，能够在断电后保留数据，适用于长期保存程序和文件信息。鉴于数据可能存储在多种物理介质（如磁盘、SSD、光盘等）上，主流的操作系统需要提供一致的抽象接口，以屏蔽底层硬件差异，使用户能够高效、统一地进行文件的读写、创建与删除等操作。当前主流操作系统均实现了完整的文件系统，开发者可以通过如 POSIX 这样的标准 API 接口来访问和管理存储设备，而无需关心具体设备的物理实现方式。尽管操作系统的文件子系统通过标准如 POSIX 提供了对存储设备的访问能力但仍存在一些限制；例如存储性能受限于设备的物理读写速度，同时文件系统通常采用页缓存 Page Cache 或写缓冲机制，这意味着数据写入操作并不会立即持久化到磁盘，一旦系统发生故障或意外断电，可能会导致数据丢失，影响系统的可靠性。基础架构综上所述，针对这些场景的问题 UrnaDB 采用了基于 Log-Structured Megre Tree 日志结构化文件系统的存储引擎实现，存储引擎会以 Append-Only Log 的方式将所有的数据操作写入到数据文件中。同时 UrnaDB 为了高速查询检索数据记录，存储引擎会将数据记录索引信息全部保存在内存中，从而实现高效快速的查询目标数据记录。这样的设计的好处是能以磁盘最大写入性能进行写入数据，并且还能减少读取磁盘索引所需要的时间，通过一次索引定位来读取数据记录，写入和查询流程图：其核心持久化机制基于预写日志 Write-Ahead Logging 简称 WAL ，在对数据执行任何操作前，都会先将操作记录写入 WAL 日志文件。WAL 文件不仅承担持久化的角色，也作为主要的数据存储载体。在数据库进程崩溃后，只需从 WAL 日志中顺序读取各条 Segment 记录，即可高效恢复内存中的索引结构。这是一种 Log-Structured Megre T…

哈希算法的实践
type: item
date: 2022-05-12T17:36:00+08:00
description: 哈希函数 估计是一个程序员都知道这个概念，可以将一串数据变成一串特定的散列值，如果看过我之前的一致性哈希那篇文章应该会很清楚工作原理。这篇文章将讲解如何去设计一个工业级的哈希表，哈希表本身概念和工作原理没有什么难的，主要还是存储方式选择和负载因子带来的扩容和哈希冲突问题。哈希表属于数据结构的范围了，日常开发过程中经常会使用到哈希表例如Java的HashMap、Go内置的map，这些都是哈希表，还有知名的缓存中间件例如Redis也是采用哈希的方式数据分区，也可以看成是一个超大的哈希表，大部分都在使用，而设计一个工业级哈希表要考虑的因素有很多：存储方式、负载因子、缩容和扩容问题等。存储方式哈希表是一种映射数据结构key-value，这种形式的存储，键可以是任何数据只要经过hash function就能得到一串哈希序列值。而值的存储方式有很2种：开放式存储，链表式存储，两种方式都用来存储值数据的，区别就是存储方式和取值方式不同罢了。开放式寻址： 上来我们可以申请一块大的连续内存空间，数组就可以满足，然后把经过哈希计算的值放到对应的数组下标位置上，但是问题就是哈希函数可能不同的键算出来的值有可能相同发送哈希冲突了，这时怎么解决位置被占用的就是一个问题？开放寻址工作原理如上图，如果发生了位置占用就往下一个下标位置找，看看是不是为空的，如果是空的那么就存储，循环这个过程。删除操作是不直接删除数据的，而是直接标记存储位置的下标，假性删除。但是这种也会有扩容带来的问题，删除的数据越多那么被标记的位置越多而且还是一样占用内存，所以不能再删除和插入一起操作，如果直接删除了位置上的内容，下次插入值时被存储到这个位置可能会发生数据错乱的现象。链式存储： 链式存储是最简单的方式了，数据结构存储头节点是指向一个根数组的，然后如果发生了数据冲突那么的，数据会以链表的方式对接下去，这样的好处就是数据槽位固定的，但是数据元素可以在每个槽位上以链表的方式存储下去，动态分配存储，这个最常用的没有什么好说的原理图我也不画了。负载因子负载因子针对的是链式存储的方式，上面我讲过链式存储解决哈希冲突的问题是把数据分槽位，然后在对应的槽位上以链表的方式存储数据。但是这样的话如果数据越来越多，每个链表上的数据也很越来越多导致本来查询很快的时间复杂度变成了O(n)，怎么解决这样的问题，那就是要对数据较多的时候进行扩容操作，扩容操作就是针对分区槽位的扩容，把数据能确保分摊到所有的槽位上，那触发槽位扩容条件是什么？需要扩容条件，那就要确定存储空间在什么条件下才能发生扩容操作，看了上面图，很容易看出来我们哈希函数是针对的槽位数，在哈希确定到槽位编号了之后，然后就是把数据放到链表上存储，和槽位上其他节点对接上。熟悉链表的朋友应该知道链表查找是要从头开始扫描查找数据的，所以时间复杂度为O(n)，所以链表上的数据不能太多，为了解决这个不能多的办法就是对槽的个数发生更新。数据少的时候可能默认几个槽位就可以够用了，但是如果数据多了动态添加和删除数据多了，那么就要扩容了，扩容条件按照上面的推理完全可以推导出来那就是把目前哈希表所有存储的数据对槽位取平摊值，这个值就是每个槽位上的负载因子，公式我已经在图上画出来了，当负载因子越大的时候可能每个槽位上的链表数据就越多，查询性能也会有影响，越小就越快，所以在设计一个哈希表时负载因子很重要，使用的时候，可以在预估需要处理的数量积，先计算出负载因子然后初始化一个哈希表，这样就能满足需求。扩容问题解决了什么时候发生扩容的问题之后，另外一个问题就是怎么迁移数据到新的存储地址上，当数据太多时候，一般的扩容策略都在分配一个原始大小1.25的存储空间或者原始存储大小的两倍空间来存储老的数据和新的数据。但是问题来了，如果老的哈希表里面有很多数据一次性迁移会带来很大问题，例如迁移的过程中哈希表还在并发操作的，并且有可能还有数据在写入，怎么保证数据一次性迁移呢？并且在扩容之后我们的哈希函数也要跟着更新的，原来的槽位数和新的扩容之后的槽位数是不一致的，所以老的哈希函数是不能正常访问到新的数据，这也是一个问题？很多时候一次性迁移数据会发生性能损耗，哈希槽位上的链表数据越多那么迁移的数据就越多，这个就会带来性能问题。我看过一些比较好的迁移策略就是间接性迁移，也可以理解为被动迁移，那是怎么工作的呢？针对上面的两个扩容的问题，哈希函数我们可以保留两个哈希函数，当有新的数据来的时候我们使用新的哈希函数计算存储到新的空间里面，如果有请求来查询我们可以先把老哈希函数计算一遍看看有没有数据，如果老哈希函数在老的地址里面没有找到新的数据，就用的新的哈希函数查找，每次有新的数据插入时就触发一次老的数据迁移，直到老的数据全部被迁移完成，销毁老的存储空间即可，在数据没有迁移完成之前可能内存消耗比较…

计算机中的二进制位
type: item
date: 2022-05-12T17:21:00+08:00
description: 二进制的 0 和 1人类我们常用的数据表示方法是十进制，而计算机却是二进制，在计算机的设备里面所有的数据都是使用二进制表示的。显示器显示的数据是人类能理解的数据，这是为了更好的和人类交互这样的设计的，当在键盘上输入一个内容的时候，这些在计算机内部处理完全是二进制的，计算机只认识 0 和 1 ，也是二进制位。计算机最基础的计量单位是 bit ，也就是 8 个比特位等于一个 byte 字节，后面的计量单位在当前计量基础做 10^2 计算，相关的存储单位可以去看看相关资料，这篇 blog 我就不会详细的介绍这些计量单位。用比特位存储表示详细的话，如果把8个比特位填满那么可以表示为 255 ，如果 8 比特位都是0的话那么就是 0 。如果某些时候在追求计算性能和存储空间利用率的时候，可以使用位运算，如果需要表示的信息状态只要两种的话可以使用位图来表示，这样空间利用率会更好，本文就介绍一下关于位运算的基础和位图。说一句话就是：与二一是 1 ，或二零是 0 ，异或相同为 0 ，相异为 1 ，取反就是反。计算两个数的和，因为在计算机中都是以二进制来进行运算，所以下面所给的 int 变量会在机器内部先转换为二进制在进行相加，例如下图动图：在我们人类世界里是逢十进一，在计算机的二进制里面逢二进一，计算过程： 183: 1 0 1 1 0 1 1 1 + 19: 0 0 1 0 0 0 1 1 —————————————————————————— 202: 1 1 0 0 1 0 1 0在计算机运算里面，加减乘除都是通过加法实现的，这部分内容比较深奥，涉及一些知识，读者可以下面这个视频：李永乐二进制进制运算位图实现位图就是利用的比特位作为基础的一种数据结构的应用，可以使用少量的内存占用表示更多数据信息，例如我在 Go 语言里面使用了 int16 作为基础存储空间，这样 int16 是由 2 个 byte 组成的，可以表示 512 状态信息。位图就是使用这一特性来解决的问题状态信息表示的问题，例如下面实现代码：package bitmap type Bits struct { bytes []int16 nbits int } //把需要表示数量除以16得到需要分配的int16个数 func New(nbits int) Bits { return Bits{ nbits: nbits, bytes: make([]int16, nbits/16+1), } } // 通过下标对16取商得到具体那块内存 // 然后对其内存的bit位进行设置 func (m *Bits) Set(index int) { if index > m.nbits { return } byteIndex := index / 16 bitIndex := index % 16 m.bytes[byteIndex] |= (1 << bitIndex) } func (m *Bits) Peek(index int) bool { if index > m.nbits { return false } byteIndex := index / 16 bitIndex := index % 16 return (m.bytes[byteIndex] & (1 << bitIndex)) != 0 }

Go 范型的实践
type: item
date: 2022-05-09T17:35:00+08:00
description: Go泛型也出来很久了，最近也用泛型去实现一些功能，例如数据结构一些应用还是没有什么问题的。但是如果做一些类型上限制，还是有点问题，和其他语言有一些不一样的地方，想要基于泛型做一些类型上的限制，必须使用组合的模式，或者嵌套。这篇我将记录一下我在Go泛型上遇到一些问题。阅读这篇文章读者需要了解Go泛型怎么使用和泛型能做什么，还有了解map结构原理，并且本文会以LinkedHashMap作为一个泛型结构讲解一些关于Go泛型不完美的地方。读者要知道LinkedHashMap底层是怎么工作的才能读懂这篇文章。原生Map局限性大家都知道Go的内置map结构在遍历的时候是无序的，如果要让其有序输出那么就要对key进行排序，然后收集排序完的key依次索引输出这样子，但是很麻烦的样子，并且还不能保证map存储的的顺序不是以插入值的顺序而存储，并且还不能按照访问操作顺序重排底层存储结构元素的关系，了解的原生map应该知道底层是通过hash function打乱并且存储在不同桶里，遍历只能从不同的桶里随机输出这些元素，这就是无序的原因。LinkedHashMap使用过Java朋友应该知道一个数据结构叫LinkedHashMap，这个数据结构是可以保证数据存储顺序的，并且还能按照配置动态调整存储的元素的顺序关系，下面这是一段Java代码，介绍一下工作原理：LinkedHashMap<String, Integer> lmap = new LinkedHashMap<String, Integer>(); lmap.put("语文", 1); lmap.put("数学", 2); lmap.put("英语", 3); lmap.put("历史", 4); lmap.put("政治", 5); lmap.put("地理", 6); lmap.put("生物", 7); lmap.put("化学", 8); for(Entry<String, Integer> entry : lmap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); }输出结果可以看到：语文: 1 数学: 2 英语: 3 历史: 4 政治: 5 地理: 6 生物: 7 化学: 8可以看到是以我们插入时候的顺序输出的结果，可以做到有序的。这是怎么做到的呢？如果深入底层源代码分析发现，他内部结构入下图：和HashMap的运行结果不同，LinkedHashMap的迭代输出的结果保持了插入顺序，它底层其实就是一个map加Linked List组成一个结构，map负责索引，而Linked List负责的是数据顺序组织存储方式，可以形成一个完全有序的链表，大部分可能认为就是一个链式存储方式，这是不对的，有兴趣可以源代码，是两种数据结构组合而成，类似于LRU淘汰算法那样，每次操作元素都会发生底层数据交换位置。元素是被内置的map索引着的只是为了方便快速拿取，而为了数据能和插入时一致的顺序又用链表组织成了有序链表，原理可以想象上面这幅图，你洗衣服拿衣服怎么洗的？如果读者看到这里看不懂话，可以去网上看看关于LinkedHashMap底层实现的代码分析文章吧，我这里不讲解了。用Go泛型实现对其工作原理介绍完了，下面我就针对这个这种方式，使用Go去实现类似的，算是重复造轮子吧。但是在泛型key上还是遇到一些问题，顺便写一个文章记录。下面这是我使用Go复刻的LinkedHashMap代码，Node[K Hashed, V any]结构是为了底层数据存储所设计的，而LinkedHashMap为主体结构，注意里面的table map[uint64]*Node[K, V]字段。type Node[K Hashed, V any] struct { Prev, Next *Node[K, V] Key K Value V } // Stored structure type LinkedHashMap[K Hashed, V any] struct { accessOrder bool // the iteration ordering method capacity int // total capacity head, tail *Node[K, V] // linked list table map[uint64]*Node[K, V] // data storeage size int // current size }为了这个map能达到和Java的LinkedHashMap一样的效果，我在key泛型上做了限制，因为要支持双泛型参数声明，有两个泛型参数，如果简单一个话，这个键完全可以设置为string类型，那…

二分查找算法
type: item
date: 2022-05-04T17:39:00+08:00
description: 逻辑推导二分查找算法： 也称为二分搜索算法，是一个很巧妙的算法，在实际开发中我们会经常使用到这个算法，能在很大的数量有序不重复集合下快速查找到一个元素，每次查找一次如果不符合命中条件的，那么参入搜索的集合就会被折半一次，也就是下次搜索的时候数量会少一半，原理如下图：代码实现首先要在被排序的数组里面定义两个指针，分别是low和high，还有一个middle指针，这个指针是随机的取low和high指针区间的随机数。然后每次搜索就是看需要查找的n是否等于middle指针上的元素，如果等于那么就是命中查找到元素直接返回即可。否则就看middle是否小于n，如果小于那么就把low指向middle + 1处，如果大于就把high指向middle - 1处。package main import "fmt" func main() { var arr []int = []int{10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} index := binarySearch(arr, len(arr), 16) fmt.Println(index) } func binarySearch(arr []int, len, n int) int { // 初始化两个指针 low, high := 0, len - 1 // 两个指针的关系必须是low小于等于high for low < high { // 取中轴 middle := low + ((high-low)>>1) if arr[middle] == n { return middle } // 如果middle小于n就说明不在middle前面的范围内 // 如果middle大于n就说明不在middle后面的范围内 if arr[middle] < n { low = middle + 1 } else { high = middle - 1 } } return -1 } 需要注意的是low + ((high-low)>>1) = low + (high-low) / 2这行代码，这行代码是为了防止有时候我们需要搜索的数据量太大，经过计算得出来的值会超过int类型的表示范围，所以这来采用优化，位运算也是比传统除法性能要高很多的。下面是递归版本的实现：package me.ibyte.sorting; public class BinarySearch { public static void main(String[] args) { int[] arr = { 10, 11, 12, 13, 14, 15 ,15}; int index = bsearch(arr, 14, 0, arr.length - 1); System.out.println(index); } public static int bsearch(int[] arr, int n, int low, int hight) { if (low > high) { return -1; } int middle = low + (high - low) / 2; if (arr[middle] == n) { return middle; } if (arr[middle] < n) { return bsearch(arr, n, middle + 1, high); } else { return bsearch(arr, n, low, middle - 1); } } } 以上是我的实现代码，掌握了二分查找算法的思想其实用代码写起来就很容易，把思路转换成代码实现就可以了，如果不能理解自己可以先画一下图，例如上面就是我自己画的图，图画完就清晰多了，或者可以看看这个视频讲解二分搜索算法。优点：在一定数据量下查找数据是O(logN)，会很快的就能查找到目标数据。缺点：数据必须全部是静态的并且数据量占用内存不能太多，二分查找依赖于数组，数组存储是连续的，如果数据规模较小可以使用暴力顺序遍历查找，如果数据量较多并且在操作的时候会动态发生修改建议使用二叉搜索树或者哈希表。其实二分查找算法最核心思想是每次进行一轮搜索，数据范围会缩小n/2，这个和插入排序的进阶版本希尔排序的思想差不多。每进行一轮会在原始数组上进行数据缩减，而不是传统方式的O(n)一个一个去查找目标值，而是带着有条件有跨度去搜索，这里条件就是原数组有序并且每一轮都能确定目标数据所在的范围。变体问题二分查找本质也是分而治之的应用，本身如果搜索查找一个元素的话没有什么难度。还有一部分二分查找算法应用就是使用二分查找在有重复的数据段里面做模糊查找。例如[12,13,14,14,14,15,16,17]，这个数组里面有3个1…

堆排序定时器实现
type: item
date: 2022-04-29T17:57:00+08:00
description: 一些思考很多人可能认为算法和数据结构没有多大用处，恰恰相反，我们使用的一些编程语言核心类库和一些api底层就是对数据结构加算法而组成的。很多人可能最多就是看看源代码，写点分析源代码文章，那都是已经现有的东西照着思路读就行了，而算法完全是不一样的，一个算法题解题思路可以是多种，多种数据结构解决，那这么多解决问题方法，差异在哪啦呢？这就得看自己本身对各种数据结构的特性的了解程度了，算法是应用于数据结构之上的东西，如果没有掌握好数据结构，怎么谈应用去解决实际问题呢？我看过很多人，或者大多数开发者最多就是一个API操作员，搞点框架拼积木一样，能跑就行了，当然框架能解决问题也是，也能减少开发复杂性，重复工作，那都是一些固定死的业务逻辑罢了，真正的问题是针对你业务问题而且填写你业务逻辑问题解决问题，框架做的最多就是把你外围的工作或者基础配置搭建好而已。真正的业务逻辑还是根据个人的需求去完成，框架也是别人包装出来的，但是它包装不了不同问题的解决方法，只能起到一些刚开始的约束作用，最后你会发现随着需求的改变和业务问题，你的代码还是要解决问题，还是自己去写核心逻辑代码，所以不要小看数据结构和算法的重要性。当然很多人选择if else一把梭然后call api完成任务罢了，我觉得一个好工程师最少要掌握设计模式编程范式，数据结构的应用去解决问题，那样代码水平才能提高。我看到很多人在一些语言上写溜的不行，换到Rust上就寸步难行。。实际上根本什么都不懂，面试靠着是八股文，八股文这个东西我觉得只要你不笨有脑子是个人都能背，所以我现在看到那种八股文广告就烦的狠，不是背还是要理解，这样才能技术有提升。而真正一名工程师应该是从上到下知识系统和认知面要很广，操作系统，计算机组成，计算机网络，编译原理，数据结构加算法，这些才是组成今天的计算机的东西，不说废话了本文将介绍堆的实现和堆在实际问题上的应用。堆结构什么是堆？堆是从完全二叉树演进过来的，至于什么是完成二叉树我这里就不介绍了。堆有两种组织形态：根节点的值小于左右孩子节点的值称为小顶堆，根节点的值大于左右孩子节点的值称为大顶堆。堆的用处用很多，例如解决动态数据添加删除问题，从小到大排序，可以在O(1)的时间复杂度里面获取最大值或者最小值，0(logn)的时间内添加一个节点或者删除一个节点。获取一组序列的最大的K个元素，时间复杂度为NlogK，求一些排名前几的这些问题也可以使用。优先队列就是一个例子，如果一个节点频繁添加或者删除可以把他放入大顶堆堆顶上，还有数据是动态的每次要根据新进来的数据做出调整这种也适合使用堆。最典型的应用就是高效的定时器任务扫描了，这个在Go语言里面的定时器底层有用到，具体过程如下：假设我们要设计一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间比如 1 秒，就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。像这样每次扫描的时候，把所有任务都扫描一遍，肯定很低效，如果任务比较少还好，任务比较多的话，就比较耗时。那有更高效的办法呢？答案是有的：我们可以把每个任务都存储在优先级队列中(以触发时间为优先级的小顶堆)，这样最先执行的任务就在堆顶，每次扫描的时候只需取出堆顶任务，拿对其他任务的定时时间和当前时间比较。堆构造上面说了这么多，那如何构造一个堆呢？例如下图右边就是一个大顶堆：构建很简单就是组成堆的3个元素分别比较交换位置，把最大的放到堆顶上，如果有子节点的话还要继续调整子节点，下面是我Java实现的代码： public static void heapify(int[] tree,int len,int i) { if (i >= len) { return; } int max = i,left = i * 2 + 1,right = i * 2 + 2; if (tree[left] > tree[max]) { max = left; } if (tree[right] > tree[max]) { max = right; } if (max != i) { int temp = arr[i]; arr[i] = arr[max]; arr[max] = arr[i]; heapify(tree,len,max); } } 如果输入的数组顺序是无序的，次数我们还需要对数组进行调整，以满足大顶堆的要求，原理就是对最后一组的3个元素依次往上调整直到到堆顶即可完成堆的构建，下面是我的Java代码：public static void build(int []tree,int len) { for (int i = (len - 1) / 2; i >= O; --i) { heapify(tree,len…

非线型结构之树
type: item
date: 2022-03-12T17:12:00+08:00
description: 树是一个非线性结构，日常很多东西都和树这个结构类似，例如：企业人员组织架构，操作系统的文件目录，如果这些信息被高度抽象到某种程度那么就是一种数据结构的应用了，这篇文章讲整理一下 树 的知识。树最简单的结构组织方式就是二叉树，二叉树是树里面应用最简单的一种树型结构，其特征就是每个节点有2个子节点或者说一个节点，也可以有一个上级节点，如果当前节点没有子节点但是有父节点那么可以认为是叶子节点。节点之间的关系就是：层次关系，左右关系，层次关系是子节点和父节点之间的关系，左右关系是父节点下的左右节点之间的关系，如下图：关于树的一些名词有： 高度 、 深度 、 层数 ，这些可以用来形容一个树的元信息。节点的高度：节点到叶子节点的最长路径的长度也就是边数。节点的深度：根节点到这个节点的路径长度的边数。节点的层数：节点的深度加上1。树的高度：也就是根节点的高度。上图就是一颗树的结构图，此结构不限于二叉树所有树形结构都适用。树的存储树的存储方式有两种，一种是链式存储，一种是数组存储；链式存储如下图，一共 3 个字段，一个字段存储数据，另外两个字段存储左右子节点：另外一种就是使用数组进行存储，连续空间存储，如下图：上面是使用数组连续空间存储的话不需要额外的空间占用去存储左右孩子节点的 child 的指针，而是通过数组的下标去访问数组上的元素，而下标访问是很特殊的公式如上图我所画的，计算公式很简单: 父节点 = 当前节点下标 / 2，左孩子节点 = 当前下标 2，右孩子节点 = 当前下标 2 + 1；当然有一个前提是数组存储的时候根节点下标为1，而不是0，如果是零的话公式还需要额外计算，大多数1为根节点下标，0有的话空出来，浪费一个位置空间没有什么特殊的。两种存储方式利弊： 第一种使用链式存储的话，在数据节点需要加入树中的时候可以动态分配内存，而数组的方式则要在使用前提取分配一堆连续的内存，然后去存储元素，因为数组的特殊性，如果数中某些子节点只要单一的孩子节点，那么数组对应上的位置为空，要预留这些位置，不能充分使用内存，如果是完全二叉树情况下推荐使用数组，对于非完全二叉树的情况下还是使用传统链式存储方式，这个可能要根据使用的时候场景进行分配。树的应用树最典型的应用就是二叉搜索树了，二叉搜索树特点就是一个节点最多只有两个节点，也可以只有一个节点，而左子节点比父节点本身小，右子节点比父节点大。如上图我所画的就是一个典型的完全二叉搜索树，并且满足左节点小于父节点，右孩子大于父节点的要求，用代码实现的话，用链式存储实现是最为简单的，下面是链式存储实现代码：package tree import "github.com/auula/coffee" type Node[T coffee.Number] struct { Data T LeftChild, RightChild *Node[T] } type BinaryTree[T coffee.Number] struct { Root *Node[T] Size int } func (bt *BinaryTree[T]) Insert(v T) { if bt.Root == nil { bt.Root = &Node[T]{Data: v} return } node := bt.Root for node != nil { if v > node.Data { if node.RightChild == nil { node.RightChild = &Node[T]{Data: v} return } node = node.RightChild } else { if node.LeftChild == nil { node.LeftChild = &Node[T]{Data: v} return } node = node.LeftChild } } } func (bt *BinaryTree[T]) Search(v T) *Node[T] { node := bt.Root for node != nil { if v < node.Data { node = node.LeftChild } else if v > node.Data { node = node.RightChild } else { return node } } return nil } 构造一颗二叉搜索树很简单，先是构造根节点，然后根据需要被插入的节点的值构造左右子节点，搜索方式也是根据节点大小进行的，时间复杂度为O(logN)。func Previous[T coffee.Number](node *Node[T], channel chan *Node[T]) { if node == nil { retur…