作者: 周洋，《 Substrate快速入门与开发实战》开发课第三期助教。某区块链项目核心开发者，拥有多年的汽车电子嵌入式开发及区块链开发经验，擅长 C++，Go，Rust 语言。《Substrate 快速入门与开发实战》 是一块链习联合 Laminar CTO 、Substrate、Polkadot 贡献代码者、 Polkadot 社区大使陈锡亮老师共同打造的全球第一门 Substrate 开发实战指南课程。
目前第三期课程已经进行到第四周，我们希望通过这门精心打磨的课程，在这一年内为全球区块链行业培养 200 位最顶尖的 Substrate 开发者。
每周日晚 8 点，都会进行《Substrate 快速入门与开发实战》开发课的内容知识拓展——助教技术分享会。昨晚，由周洋助教给我们带来「助教技术分享会」第 3讲，题为「Substrate Runtime 中的堆排序」。
在第一期课程的挑战赛中，我们小组为加密猫添加了 lifetime 属性。lifetime 可以理解为小猫的寿命，如果一只猫存在的时间达到了生命周期，它对应的 token 会被系统自动删除掉，这只猫也消失了。要求链上自动化完成上述过程，所以每次 import block 都要检查哪些猫的 lifetime 超时需要被删除。由于所有猫被存在一个数组结构中，找出 lifetime 超时的猫是典型的寻找 Top K 问题。如果实现不当，可能会引入 O(n) 的时间复杂度，进而有可能发生对链的恶意攻击。这时使用堆排序可以将时间复杂度降低为O(nlogn)。今天分享主要关注 heap 的实现，不会有加密猫 lifetime feature 实现细节。
2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。堆排序有几个非常重要的应用：优先级队列、求 Top K 和 求中位数。对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。rust 标准库里面提供了 binary heap 的实现，但是现在我们还不能在 Substrate Runtime 环境下直接使用它。那么我们在 Substrate Runtime 环境中实现一个泛型的堆结构，并且利用 Substrate 默认的 storage value 作为堆的存储来解决 Top K 问题。用数组来存储完全二叉树是个不错的选择。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，非常节省存储空间。这里 T 代表堆中元素类型。C 代表 Compare trait，可供自定义排序方式（决定是大顶堆还是小顶堆）。S 代表存储类型，这个数组利用了 Substrate 提供的 StorageValue<Vec<T>, Query=Vec<T>> 类型。从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2+1 的节点，右子节点就是下标为 i∗2+2 的节点。往堆中插入一个元素后，我们需要进行调整，让其重新满足堆的特性，这个过程叫作堆化（heapify）。堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。我这里画了一张堆化的过程分解图。我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。https://github.com/yz89/substrate-heap/blob/master/runtime/src/heap.rs 总结一下。我们实现了一个泛型的堆结构，用户可以自定义元素类型及排序方式（大顶堆，小顶堆）。使用了Substrate 内置的 StorageValue 作为堆的存储，这样为 Substrate Runtime 提供了通用的堆排序实现。
更多阅读：
▎Subdev 讨论 ▏探究语言规则背后的含义
▎Subdev 周记 ▏区块链编程语言必不可少的三大特性
▎Substrate Off-Chian Workers 是什么？如何用？
扫码关注公众号，回复“1”加入开发者社群