堆(Heap)

介绍 #

堆(heap)分为最大堆(大根堆/大顶堆)和最小堆(小根堆/小顶堆),通常用完全二叉树实现,完全二叉树又可以用数组实现,故堆通常以数组形式的存储,而非二叉树的链式存储。常见的堆有二叉堆裴波那契堆等,通常也用堆来实现优先队列(Priority Queue)。

堆的特点 #

堆属性非常有用,因为堆常常被当做优先队列使用,因为可以快速地访问到“最重要”的元素。

  1. 在最大堆中,父节点的值比每一个子节点的值都要大。
  2. 在最小堆中,父节点的值比每一个子节点的值都要小。
  3. 满足完全二叉树的特性:在当前层级所有的节点都已经填满之前不允许开始下一层的填充。

如图,这是一个最大堆,转化为数组之后:[ 10, 7, 2, 5, 1 ],故堆的查找的时间复杂度为 O(1)。

在堆中,在当前层级所有的节点都已经填满之前不允许开是下一层的填充,所以堆总是有这样的形状:

基于二叉堆的性质,当数组的第一个空着,arr[1] 为根节点时,每个节点的父节点和左右孩子的索引都可以通过简单的运算得到:

// 父节点的索引
int parent(int root) {
    return root / 2;
}
// 左孩子的索引
int left(int root) {
    return root * 2;
}
// 右孩子的索引
int right(int root) {
    return root * 2 + 1;
}

arr[0] 为根节点时:

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

堆和树的区别 #

节点的顺序在二叉搜索树中,左子节点必须比父节点小,右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小,而在最小堆中,它们都必须比父节点大。

内存占用普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数组来存储数据,且不使用指针。

平衡二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到 O(log n) 。你可以按任意顺序位置插入/删除数据,或者使用 AVL 树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证 O(log n) 的性能。

搜索在二叉树中搜索会很快,但是在堆中搜索会很慢。在堆中搜索不是第一优先级,因为使用堆的目的是将最大(或者最小)的节点放在最前面,从而快速的进行相关插入、删除操作。

常用操作 #

以最大堆为例。

堆的插入、删除操作都可能需要交换节点,以便把节点放到合适的位置,交换的次数最多为二叉树的深度,因此如果堆中有n个节点那么它的插入和删除操作的时间复杂度都是 O(logn) 。

插入结点 #

步骤如下:

  1. 在最大堆中添加新的节点,应该先从上到下、从左到右找出第 1 个空缺的位置,并将新节点添加到该空缺位置。
  2. 如果新节点的值比它的父节点的值大,那么交换它和它的父节点。
  3. 重复这个过程,直到新节点的值小于或等于它的父节点,或者它已经到达堆的顶部位置。

新结点上浮的过程一般叫 **swim 上浮 **。

删除结点 #

通常只删除对顶部的元素,步骤如下:

  1. 将堆最底层最右边的结点移到堆的顶部。
  2. 如果此时它的左子节点或右子节点的值大于它,那么它和左右子节点中值较大的节点交换。
  3. 如果交换之后节点的值仍然小于它的子节点的值,则再次交换,直到该节点的值大于或等于它的左右子节点的值,或者到达最低层为止。

这里结点下沉的过程一般叫 sink 下沉

各语言实现 #

除了 Java,一般都需要自己实现一个堆类用来初始化实例,尤其是所用语言的标准库没有帮你实现的情况下。

golang #

go 内置了 container/heap 实现堆,实现这个 interface 的实例就可看做是一个堆。

type Interface interface {
	sort.Interface
	Push(x any) // add x as element Len()
	Pop() any   // remove and return element Len() - 1.
}

初始化一个堆:

package main

import (
	"container/heap"
	"fmt"
)

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x any) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
	h := &IntHeap{2, 1, 5}
	heap.Init(h)
	heap.Push(h, 3)
	fmt.Printf("minimum: %d\n", (*h)[0])
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
}
// minimum: 1
// 1 2 3 5

通常用二叉堆实现优先队列(Priority Queue)。

优先队列的性质是,队列是排好序的。插入或删除元素的时候,元素会自动排序。

func (pq *PriorityQueue) Push(x any) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
	item.value = value
	item.priority = priority
	heap.Fix(pq, item.index)
}

// This example creates a PriorityQueue with some items, adds and manipulates an item,
// and then removes the items in priority order.
func main() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Item{
			value:    value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// Insert a new item and then modify its priority.
	item := &Item{
		value:    "orange",
		priority: 1,
	}
	heap.Push(&pq, item)
	pq.update(item, item.value, 5)

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%.2d:%s ", item.priority, item.value)
	}
}
// 05:orange 04:pear 03:banana 02:apple

JavaScript 实现 #

常见题型 #

剑指 Offer 40. 最小的k个数

215. 数组中的第K个最大元素

其他问题 #

斐波那契堆 #

斐波那契堆 - wiki

堆排序 #

参考本站另一篇 排序算法

优先队列 #

普通队列遵循先进先出,优先队列的出队顺序取决于“优先级”(一般是按大小排序),和入队顺序无关,通常用堆来实现优先队列(Abstract Data Type,ADT),也有二项堆、平衡树、线段树等其他方式实现。

优先队列的使用场景还挺多:

  • 数据压缩:赫夫曼编码算法;
  • 最短路径算法:Dijkstra算法;
  • 最小生成树算法:Prim算法;
  • 事件驱动仿真:顾客排队算法;
  • 选择问题:查找第k个最小元素;

参考 #

https://www.jianshu.com/p/6b526aa481b1

https://labuladong.github.io/algo/2/21/62/

https://github.com/sisterAn/JavaScript-Algorithms/issues/60