heap 是一种常见的数据结构,本周将带大家来了解一下 Go 语言标准库中的 Heap 包,首先在此之前我们需要对堆(heap) 有所概念,简单理解就是用数组实现的完全二叉树,在 Go 官方概述中有这样说道“堆是一棵树,其属性是每个节点都是其子树中的最小值节点”,那么堆的属性又是什么呢?
所谓的“堆属性”指的就是最大堆与最小堆,这两者之间最大的区别在于数据的排列方式不同,如图 1 所示在最大堆中,父节点的值比每一个子节点的值都要大。在最小堆中,父节点的值比每一个子节点的值都要小,在 Go 语言中所采用的是最小堆,树中最小的元素是根,索引为 0。
通过刚刚的讲述想必我们已经对堆有了一个基础的概念,那问题来了,虽然堆在物理结构上是一个一维的数组,但在存储逻辑上是一棵完全二叉树,所以堆的数据结构是非线性的,那它即没有指针指向当前节点的父节点或子节点,也没有多余的空间用来存储当前节点信息,我们该如何对当前节点元素完成父子节点的定位操作。