原文:https://mp.weixin.qq.com/s/jqkjXIAN8rZcBWqlPL0gSw
周洋,某区块链项目核心开发者,拥有多年的汽车电子嵌入式开发及区块链开发经验,擅长 C++,Go,Rust 语言。1月5日,周洋分享了「Substrate Runtime 中的堆排序」。以下为分享的关键内容。
1.给加密猫

添加一个 lifetime 属性

 
在第一期课程的挑战赛中,我们小组为加密猫添加了 lifetime 属性。lifetime 可以理解为小猫的寿命,如果一只猫存在的时间达到了生命周期,它对应的 token 会被系统自动删除掉,这只猫也消失了。
 
要求链上自动化完成上述过程,所以每次 import block 都要检查哪些猫的 lifetime 超时需要被删除。由于所有猫被存在一个数组结构中,找出 lifetime 超时的猫是典型的寻找 Top K 问题。
 
如果实现不当,可能会引入 O(n) 的时间复杂度,进而有可能发生对链的恶意攻击。这时使用堆排序可以将时间复杂度降低为O(mlogn)。
 
今天分享主要关注 heap 的实现,不会有加密猫 lifetime feature 实现细节。

 

2. 堆排序介绍

 
 堆需要以下2个条件:
1. 堆是一个完全二叉树
2. 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
 
堆排序有几个非常重要的应用:优先级队列、求 Top K 和 求中位数。
 
对于每个节点的值都大于等于子树中每个节点值的堆,我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆,我们叫作“小顶堆”。
 
rust 标准库里面提供了 binary heap 的实现,但是现在我们还不能在 Substrate Runtime 环境下直接使用它。
 
那么我们在 Substrate Runtime 环境中实现一个泛型的堆结构,并且利用 Substrate 默认的 storage value 作为堆的存储来解决 Top K 问题
 

3.要实现一个堆,

我们先要知道如何存储一个堆

 
用数组来存储完全二叉树是个不错的选择。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点,非常节省存储空间。
 
先来看一下这个堆结构代码的样子:
        Substrate Runtime 中的堆排序-Rebase       
这里 T 代表堆中元素类型C 代表 Compare trait,可供自定义排序方式(决定是大顶堆还是小顶堆)。S 代表存储类型,这个数组利用了 Substrate 提供的 StorageValue<Vec<T>, Query=Vec<T>> 类型。
 
我画了一个用数组存储堆的例子:
   Substrate Runtime 中的堆排序-Rebase
从图中我们可以看到,数组中下标为 i 的节点的左子节点,就是下标为 i∗2+1 的节点,右子节点就是下标为 i∗2+2 的节点。
 
 寻找左子节点,右子节点对应的代码:
        Substrate Runtime 中的堆排序-Rebase       
 寻找父节点对应代码:
        Substrate Runtime 中的堆排序-Rebase 

4. 下面看一看堆的基本操作

 
 向堆中 push 一个元素:
往堆中插入一个元素后,我们需要进行调整,让其重新满足堆的特性,这个过程叫作堆化(heapify)。
 
       Substrate Runtime 中的堆排序-Rebase
堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。我这里画了一张堆化的过程分解图。
 
我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,我们就互换两个节点。一直重复这个过程,直到父子节点之间满足刚说的那种大小关系。
    Substrate Runtime 中的堆排序-Rebase       
 对应的代码:
       Substrate Runtime 中的堆排序-Rebase       
通过简单的递归实现向上交换。
        Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase       
 pop 堆顶元素:
 
       Substrate Runtime 中的堆排序-Rebase        
 对应代码:
       Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase       
 单元测试如何使用的这个堆结构:
        Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase              Substrate Runtime 中的堆排序-Rebase        
以上代码可以参考这里
https://github.com/yz89/substrate-heap/blob/master/runtime/src/heap.rs 
有完整的实现及单元测试。
 
总结一下。我们实现了一个泛型的堆结构,用户可以自定义元素类型及排序方式(大顶堆,小顶堆)。使用了Substrate 内置的 StorageValue 作为堆的存储,这样为 Substrate Runtime 提供了通用的堆排序实现。