数据结构
堆(heap)

堆(heap)是一种满足特定条件的完全二叉树,主要可分为两种类型:

  • 小顶堆(min heap):任意节点的值小于或等于其子节点的值。
  • 大顶堆(max heap):任意节点的值大于或等于其子节点的值。

heap

堆作为完全二叉树的一个特例,具有以下特性。

  • 最底层节点靠左填充,其他层的节点都被填满。
  • 我们将二叉树的根节点称为“堆顶”,将底层最靠右的节点称为“堆底”。
  • 对于大顶堆(小顶堆),堆顶元素(根节点)的值是最大(最小)的。

常用操作

堆的常用操作见下表:

方法名描述时间复杂度
push()元素入堆O(logn)O(\log n)
pop()堆顶元素出堆O(logn)O(\log n)
peek()访问堆顶元素(对于大 / 小顶堆分别为最大 / 小值)O(1)O(1)
size()获取堆的元素数量O(1)O(1)
isEmpty()判断堆是否为空O(1)O(1)

我们来看一个 max heap 的例子:

// Go 语言中可以通过实现 heap.Interface 来构建整数大顶堆
// 实现 heap.Interface 需要同时实现 sort.Interface
type intHeap []any
 
// Push heap.Interface 的方法,实现推入元素到堆
func (h *intHeap) Push(x any) {
    // Push 和 Pop 使用 pointer receiver 作为参数
    // 因为它们不仅会对切片的内容进行调整,还会修改切片的长度。
    *h = append(*h, x.(int))
}
 
// Pop heap.Interface 的方法,实现弹出堆顶元素
func (h *intHeap) Pop() any {
    // 待出堆元素存放在最后
    last := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return last
}
 
// Len sort.Interface 的方法
func (h *intHeap) Len() int {
    return len(*h)
}
 
// Less sort.Interface 的方法
func (h *intHeap) Less(i, j int) bool {
    // 如果实现小顶堆,则需要调整为小于号
    return (*h)[i].(int) > (*h)[j].(int)
}
 
// Swap sort.Interface 的方法
func (h *intHeap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
 
// Top 获取堆顶元素
func (h *intHeap) Top() any {
    return (*h)[0]
}
 
/* Driver Code */
func TestHeap(t *testing.T) {
    /* 初始化堆 */
    // 初始化大顶堆
    maxHeap := &intHeap{}
    heap.Init(maxHeap)
    /* 元素入堆 */
    // 调用 heap.Interface 的方法,来添加元素
    heap.Push(maxHeap, 1)
    heap.Push(maxHeap, 3)
    heap.Push(maxHeap, 2)
    heap.Push(maxHeap, 4)
    heap.Push(maxHeap, 5)
 
    /* 获取堆顶元素 */
    top := maxHeap.Top()
    fmt.Printf("堆顶元素为 %d\n", top)
 
    /* 堆顶元素出堆 */
    // 调用 heap.Interface 的方法,来移除元素
    heap.Pop(maxHeap) // 5
    heap.Pop(maxHeap) // 4
    heap.Pop(maxHeap) // 3
    heap.Pop(maxHeap) // 2
    heap.Pop(maxHeap) // 1
 
    /* 获取堆大小 */
    size := len(*maxHeap)
    fmt.Printf("堆元素数量为 %d\n", size)
 
    /* 判断堆是否为空 */
    isEmpty := len(*maxHeap) == 0
    fmt.Printf("堆是否为空 %t\n", isEmpty)
}

堆的存储与表示

完全二叉树非常适合用数组来表示。由于堆正是一种完全二叉树,因此我们将采用数组来存储堆。

当使用数组表示二叉树时,元素代表节点值,索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。

给定索引 i,其左子节点的索引为 2i+1,右子节点的索引为 2i+2,父节点的索引为(i-1)/2(向下整除)。当索引越界时,表示空节点或节点不存在。

可以将索引映射公式封装成函数,方便后续使用:

/* 获取左子节点的索引 */
func (h *maxHeap) left(i int) int {
    return 2*i + 1
}
 
/* 获取右子节点的索引 */
func (h *maxHeap) right(i int) int {
    return 2*i + 2
}
 
/* 获取父节点的索引 */
func (h *maxHeap) parent(i int) int {
    // 向下整除
    return (i - 1) / 2
}

访问堆顶元素

堆顶元素即为二叉树的根节点,也就是列表的首个元素:

/* 访问堆顶元素 */
func (h *maxHeap) peek() any {
    return h.data[0]
}

元素入堆

给定元素 val ,我们首先将其添加到堆底。添加之后,由于 val 可能大于堆中其他元素,堆的成立条件可能已被破坏, 因此需要修复从插入节点到根节点的路径上的各个节点,这个操作被称为堆化 heapify。

考虑从入堆节点开始,从底至顶执行堆化。我们比较插入节点与其父节点的值,如果插入节点更大,则将它们交换。 然后继续执行此操作,从底至顶修复堆中的各个节点,直至越过根节点或遇到无须交换的节点时结束。

代码如下所示:

/* 元素入堆 */
func (h *maxHeap) push(val any) {
    // 添加节点
    h.data = append(h.data, val)
    // 从底至顶堆化
    h.siftUp(len(h.data) - 1)
}
 
/* 从节点 i 开始,从底至顶堆化 */
func (h *maxHeap) siftUp(i int) {
    for true {
        // 获取节点 i 的父节点
        p := h.parent(i)
        // 当“越过根节点”或“节点无须修复”时,结束堆化
        if p < 0 || h.data[i].(int) <= h.data[p].(int) {
            break
        }
        // 交换两节点
        h.swap(i, p)
        // 循环向上堆化
        i = p
    }
}

堆顶元素出堆

堆顶元素是二叉树的根节点,即列表首元素。为了尽量减少元素索引的变动,我们采用以下操作步骤。

  • 交换堆顶元素与堆底元素(交换根节点与最右叶节点)
  • 交换完成后,将堆底从列表中删除
  • 从根节点开始,从顶至底执行堆化操作

“从顶至底堆化”的操作方向与“从底至顶堆化”相反,我们将根节点的值与其两个子节点的值进行比较,将最大的子节点与根节点交换。然后循环执行此操作,直到越过叶节点或遇到无须交换的节点时结束。

与元素入堆操作相似,堆顶元素出堆操作的时间复杂度也为 O(logn),代码如下:

/* 元素出堆 */
func (h *maxHeap) pop() any {
    // 判空处理
    if h.isEmpty() {
        fmt.Println("error")
        return nil
    }
    // 交换根节点与最右叶节点(交换首元素与尾元素)
    h.swap(0, h.size()-1)
    // 删除节点
    val := h.data[len(h.data)-1]
    h.data = h.data[:len(h.data)-1]
    // 从顶至底堆化
    h.siftDown(0)
 
    // 返回堆顶元素
    return val
}
 
/* 从节点 i 开始,从顶至底堆化 */
func (h *maxHeap) siftDown(i int) {
    for true {
        // 判断节点 i, l, r 中值最大的节点,记为 max
        l, r, max := h.left(i), h.right(i), i
        if l < h.size() && h.data[l].(int) > h.data[max].(int) {
            max = l
        }
        if r < h.size() && h.data[r].(int) > h.data[max].(int) {
            max = r
        }
        // 若节点 i 最大或索引 l, r 越界,则无须继续堆化,跳出
        if max == i {
            break
        }
        // 交换两节点
        h.swap(i, max)
        // 循环向下堆化
        i = max
    }
}