编程实践｜如何用 MoonBit 实现二叉堆与配对堆？

178 天前
 Moonbit

1964 年，J.W.J Williams 的论文"Algorithm 232 - Heapsort"将二叉堆引入了程序世界，之后的几十年中，人们发现这种数据结构在一般性的排序之外也有着不少用处(例如带优先级的任务调度，图算法等)，在它的基础上扩展产生的各种变体层出不穷。本文将探讨使用数组实现的二叉堆和使用列表实现的配对堆的工作原理，以及如何使用 MoonBit 语言实现。

顺带一提，MoonBit 即将推出的标准库中最早一批可供使用的数据结构就有堆。

堆的基本结构和使用方法

堆这个名字很容易让人联想到与栈相对的不连续的程序数据存储区域，但就和栈一样，在数据结构领域堆这个名字有着截然不同的定义。翻开那本 1964 年最早的关于堆的文献，开篇即提到堆排序是树排序的一种改进版本，所以堆的逻辑结构是一种树.

图源于： https://www.happycoders.eu/algorithms/heapsort/

在一个堆中，任意节点所存放的值都比它的子树中的节点值要大或小，这样的性质保证了堆中的任意子树同样是一个合乎条件的堆。

而对于用户而言，堆使用起来很像一种"队列"

let h = MinHeap::new()

用户可以通过insert方法向堆中添加元素

h.insert(6)
h.insert(4)
h.insert(13)

还可以用pop方法弹出一个元素，只是每次弹出堆的都是当前堆中最小的元素，而非按照insert时的顺序弹出. 

h.pop() // 此处结果应该为 4

在我们给的例子中，堆存放的元素类型是整数，但是实际上堆只要求元素类型可以比较大小，在 MoonBit 中，> < 等比较运算符都是Compare接口下的方法，实现该接口的类型都可以使用堆存储。

数组实现二叉堆

此处实现的是大根堆，即堆顶元素最大

二叉堆的逻辑结构是一种近乎全充满的二叉树(通用的名词是"完全二叉树") - 假设有一个 n 层的二叉堆，其前 n-1 层都是满的，第 n 层的节点则倾向于先布满左侧。下图是一个具有 6 个元素的二叉堆arr，它可以用一个长度为 6 的数组存放，图上已经标出了各节点在对应数组中的位置：

图片太单调不好理解？试试看二叉堆的在线可视化展示页面！

https://visualgo.net/zh/heap

因为上文中这种性质的存在，可以为每个节点赋予一个特定的编号(这个编号被用作数组索引)并通过这个编号查找其左右子节点，进而可以直接用数组来存储整个二叉堆。

在以 1 为索引起始的数组上，节点 i 的左侧子节点是 2i, 右侧子节点是 2i+1, 父节点则需要除以 2 后向下取整。

fn parent(self : Int) -> Int {
  self / 2
}

fn left(self : Int) -> Int {
  self * 2
}

fn right(self : Int) -> Int {
  self * 2 + 1
}

// 假设要获取节点 i 的父节点对应的数组索引，使用 i.parent()即可

MoonBit 中的数组以 0 为索引起始，为了保持形式上的一致，我们将最开始索引为 0 的位置保留不使用，在堆的相关操作中都将 1 做为索引起始。

在创建堆的BHeap::new函数中，为了让真实的堆容量与参数中保持一致，创建数组时要让它的长度长一位。相应的是获取堆容量的capacity()函数要在数组长度上减去 1.

MoonBit 内置的 Array[T]是定长的，所以我们会建立一个带有实际元素计数和数组的 struct 。

struct BHeap[T] {
  mut data : Array[T]
  mut count : Int
  min_value : T
}

fn BHeap::new[T : Compare](capacity : Int, minValue : T) -> BHeap[T] {
  { data: Array::make(capacity + 1, minValue), count: 0, min_value: minValue }
}

fn capacity[T](self : BHeap[T]) -> Int {
  self.data.length() - 1
}

创建数组需要默认值，建议使用 T 类型的最小值填充。

接下来要实现二叉堆的两项相关操作：插入与弹出。

向空二叉堆中插入元素很好处理，只要把元素放到data[1]就好了，但当我们需要插入更多元素时，应该怎样通过比较它们之间的大小关系找到合适的位置呢？

一种广为流传的做法是，首先将需要插入的新元素放到数组末尾 - 相当于在二叉树的最后一层找个最左边的空闲位置将它设为叶节点，如果最下一层已经充满，则另起一层。下图中是将新元素 20 插入到右侧子节点：

fn insert[T : Compare](self : BHeap[T], x : T) {
    ......
    self.data[self.count + 1] = x
    self.count = self.count + 1
    self.heap_fix(self.count)
    ......
}

这一举动有非常大的可能破坏堆的性质，我们根本不知道这个新元素和我们随便为它安排的父节点的大小关系如何。不过，虽然堆的性质被破坏了，但排除掉这个新来的不速之客，之前的堆元素仍然服从父节点元素最大的规则，在这个基础上进行修补并没有那么困难。

假设新元素对应的数组索引存储在变量 i 中，那么

fn heap_fix[T : Compare](self : BHeap[T], i : Int) {
  var i = i
  while i > 1 && self.data[i] > self.data[i.parent()] {
    self.data.exchange(i, i.parent()) // 交换元素位置
    i = i.parent() // 标记被插入元素现在所对应的索引
  }
}

fn exchange[T](self : Array[T], x : Int, y : Int) {
  let tmp = self[x]
  self[x] = self[y]
  self[y] = tmp
}

另一项重要操作是弹出堆顶元素，同样，我们采取先更改再重新平衡的策略，先把数组的第一个和最后一个元素交换一下，然后对count减一。下图中，原本的堆顶元素是 45 ，堆末端元素则是 9 ，现在交换位置并通过递减count把 45 先删除掉

删除的过程可看作让被换到堆顶的这个元素逐步"下沉"到一个合适的位置，这一步会通过heapify函数完成。

假设被交换到堆顶的元素其索引存放在变量i中，同时每一次比较都用变量s存放元素最大的节点索引，初值和 i 一样

上述过程对应的 MoonBit 代码实现如下

fn pop[T : Compare](self : BHeap[T]) -> Option[T] {
  if self.count == 0 {
    return None
  }
  let x = self.data[1] // 保存堆顶元素
  let n = self.count
  self.data.exchange(1, n)
  self.count = self.count - 1 // 删除掉被换到数组尾部的原堆顶元素
  if self.count > 0 {
    self.heapify(1)
  }
  return Some(x)
}

fn heapify[T : Compare](self : BHeap[T], index : Int) {
  let n = self.count
  var i = index
  var s = i
  while true {
    let l = i.left()
    let r = i.right()
    if l <= n && self.data[l] > self.data[s] {
      s = l
    }
    if r <= n && self.data[r] > self.data[s] {
      s = r
    }
    if s != i {
      self.data.exchange(s, i)
      i = s
    } else {
      break
    }
  }
}

有了这两种基本操作，实现通用的数组排序和选出最大的 k 个元素便很轻松了 - 不过，insert和delete有些边界条件的处理方式没有写出，如在容量用尽时进行扩容。完整的代码分享于此：BHeap.mbt

在小数据量且元素出入频繁的情况下，二叉堆的性能相当不错，资料[^1]则提到数据量较大且内存受限时，使用多叉堆会更好。

上文所实现的二叉堆具有明显的命令式风格，而 MoonBit 作为一种多范式语言对函数式编程同样有较好的支持，接下来我们会使用不可变的数据结构List以及 MoonBit 中的枚举类型为基础，实现一个配对堆。

配对堆

此处实现的是小顶堆

配对堆是一种基于多叉树的堆，实现简单，性能优越，GNU libstdc++库中的优先级队列即用它实现。它的困难之处体现在操作的复杂度分析上，本文不会涉及。

由于配对堆的结构是较为一般的多叉树，这里我们用enum定义PHeap, 一个PHeap要么是一棵空树，要么是一个存放着一个元素与 N 棵子树的节点，这样的概念可以通过枚举类型很自然地表达。

enum PHeap[T] {
  Empty
  Node(T, List[PHeap[T]])
}

在配对堆这边，先定义两个堆的合并操作会方便一些。通过模式匹配能很清晰地描述合并的逻辑：

fn merge[T : Compare](h1 : PHeap[T], h2 : PHeap[T]) -> PHeap[T] {
  match (h1, h2) {
    (Empty, h2) => h2
    (h1, Empty) => h1
    (Node(x, ts1), Node(y, ts2)) => if x < y {
      Node(x, Cons(Node(y, ts2), ts1))
    } else {
      Node(y, Cons(Node(x, ts1), ts2))
    }
  }
}

插入可以看做一个单元素的堆被合并进原来的堆

fn insert[T : Compare](self : PHeap[T], x : T) -> PHeap[T] {
  merge(self, Node(x, Nil))
}

弹出栈顶元素只需对一整个列表的堆使用 merge 进行折叠即可, 使用consolidate(此处它的含义是"整合")函数。需要注意的是，consolidate函数实际上通过递归实现了一个两阶段的整合，先是对列表中的子堆两两合并，然后再将这些新生成的堆合并到一起，这表现为代码中嵌套的merge函数调用。

fn consolidate[T : Compare](ts : List[PHeap[T]]) -> PHeap[T] {
  match ts {
    Nil => Empty
    Cons(t, Nil) => t
    Cons(t1, Cons(t2, ts)) => merge(merge(t1, t2), consolidate(ts))
  }
}

fn pop[T : Compare](self : PHeap[T]) -> Option[PHeap[T]] {
  match self {
    Empty => None
    Node(_, ts) => Some(consolidate(ts))
  }
}

match与枚举类型的使用让配对堆的相关操作实现非常简洁, 完整代码于此：try.moonbitlang.com/#a2f1dd62

从配对堆的定义和各操作可以发现，它没有在结构上大做文章保留各种额外的树大小，深度、排名等信息，这使得它避免了斐波那契堆那样的糟糕常数，在实践中为自己赢得了效率优秀实现简单灵活的良好声誉。

[^1]:You're Doing It Wrong - Think you've mastered the art of server performance? Think again.

鸣谢：刘新宇老师和他的开源书籍"基本算法" https://github.com/liuxinyu95/AlgoXY

MoonBit 编程实践

欢迎来到「 MoonBit 编程实践」！本栏目将为你提供如何使用 MooBit 强大功能，轻松实现各种工业应用与创意项目。我们将与你分享实用的示例代码、项目构建步骤以及技术见解，无论你是编程新手还是经验丰富的开发者，都可以轻松玩转 MoonBit 。

我们也期待你积极地分享你的编程实践！让我们一起开启 MoonBit 编程之旅🎉

338 次点击
所在节点    编程
0 条回复

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/991354

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX