Substrate Runtime 中的堆排序

原文：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.要实现一个堆，

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

 

用数组来存储完全二叉树是个不错的选择。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，非常节省存储空间。

 

先来看一下这个堆结构代码的样子：

               

这里 T 代表堆中元素类型。C 代表 Compare trait，可供自定义排序方式（决定是大顶堆还是小顶堆）。S 代表存储类型，这个数组利用了 Substrate 提供的 StorageValue<Vec<T>, Query=Vec<T>> 类型。

 

我画了一个用数组存储堆的例子:

   

从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2+1 的节点，右子节点就是下标为 i∗2+2 的节点。

 

 寻找左子节点，右子节点对应的代码：

               

 寻找父节点对应代码：

         

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

 

 向堆中 push 一个元素：

往堆中插入一个元素后，我们需要进行调整，让其重新满足堆的特性，这个过程叫作堆化（heapify）。

 

       

堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。我这里画了一张堆化的过程分解图。

 

我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。

           

 对应的代码：

              

通过简单的递归实现向上交换。

                             

 pop 堆顶元素：

 

               

 对应代码：

                                          

 单元测试如何使用的这个堆结构：

                                                          

以上代码可以参考这里

https://github.com/yz89/substrate-heap/blob/master/runtime/src/heap.rs 

有完整的实现及单元测试。

 

总结一下。我们实现了一个泛型的堆结构，用户可以自定义元素类型及排序方式（大顶堆，小顶堆）。使用了Substrate 内置的 StorageValue 作为堆的存储，这样为 Substrate Runtime 提供了通用的堆排序实现。