背景

堆是一種非常常用的數(shù)據(jù)結(jié)構(gòu)，它能夠支持在O(1)的時間復(fù)雜度獲取到最大值（或最小值），因此我們經(jīng)常在需要求最值的場景使用它。

然而普通堆它有一個缺點，它沒辦法快速的定位一個元素，因此它也沒辦法快速刪除一個堆中元素，需要遍歷整個堆去查詢目標元素，時間復(fù)雜度是O(n)，因為堆的結(jié)構(gòu)在邏輯上是這樣的：

在實際實現(xiàn)中一般是使用一個數(shù)組來模擬：

也就是除了最大值（大頂堆）或最小值（小頂堆），其他元素其實是沒有排序的，因此沒辦法通過二分查找的方式快速定位。

但是我們經(jīng)常有一種場景，需要堆的快速求最值的性質(zhì)，又需要能夠支持快速的隨機訪問元素，特別是刪除元素。

比如延遲任務(wù)的場景，我們可以使用堆對任務(wù)的到期時間戳進行排序，從而實現(xiàn)到期任務(wù)自動執(zhí)行，但是它沒辦法支持隨機刪除一個延遲任務(wù)的需求。

下面將介紹一種支持O(log(n))隨機刪除元素的堆。

原理

數(shù)據(jù)結(jié)構(gòu)

一種能夠快速隨機訪問元素的數(shù)據(jù)結(jié)構(gòu)是map，map如果是哈希表實現(xiàn)則能夠在O(1)的復(fù)雜度下隨機訪問任何元素，而heap在知道要刪除的元素的下標的情況下，也可以在O(log(n))的復(fù)雜度刪除一個元素。因此我們可以結(jié)合這兩個數(shù)據(jù)結(jié)構(gòu)，使用map來記錄heap中每個元素的下標，使用heap來獲取最值。

比如對于上面的堆，我們首先給每個元素添加一個Key，這樣我們才能夠使用map：

然后我們使用map記錄每個key對應(yīng)的下標：

隨機訪問

這時候比如我們最簡單的隨機訪問一個元素C，那么就是從map[C]得到元素在heap里面的index=2，因此可以拿到元素的值。

index = m[C] // 獲取元素C在heap的下標
return h[index] // 獲取index在heap的值

刪除

而如果我們要刪除元素C，我們也是從map[C]得到元素在heap里面的index=2，然后把index為2的元素和堆最后一個元素交換，然后從index=2向上和向下調(diào)整堆，也就是：

index = m[C] // 獲取元素C在heap的下標
swap(index, n - 1) // 和最后一個元素交換
pop() // 移除最后一個元素，也就是元素C
down(index) // 從index向下調(diào)整堆
up(index) // 從index向上調(diào)整堆

map里面的元素index維護

上面使用的swap(i, j)和pop()操作都會影響到map里面元素的index，其實還有push(k, v)操作也會影響元素的index。

對于swap(i, j)來說需要交換兩個元素的index：

h[i], h[j] = h[j], h[i] // 交換堆中兩個元素
m[h[i].Key] = i // 交換map元素索引
m[h[j].Key] = j // 交換map元素索引

pop()需要刪除元素的索引：

elem = h.removeLast() // 移除最后一個元素
m.remove(elem.Key) // 移除元素索引

push(k, v)需要添加元素索引：

m[key] = n // 添加元素索引
h.addLast(Entry(K, V)) // 添加元素到堆

這樣其他操作就不需要維護map里面的索引問題了，保持和正常的堆的實現(xiàn)邏輯基本一致。

Golang實現(xiàn)

由于這個數(shù)據(jù)結(jié)構(gòu)使用到了map和heap，因此起了一個比較短的名字叫meap，也就是m[ap]+[h]eap。

數(shù)據(jù)結(jié)構(gòu)

其中主要就是一個heap和一個map，由于我們也需要從heap到map的操作，因此heap里面每個元素Entry都記錄了Key，這樣就可以從heap快速訪問到map里面的元素，實現(xiàn)map里面index的修改。

LessFunc主要用于比較兩個元素大小。

type Meap[K comparable, V any] struct {
	h        []Entry[K, V]
	m        map[K]int
	lessFunc LessFunc[K, V]
}

type Entry[K comparable, V any] struct {
	Key   K
	Value V
}

type LessFunc[K comparable, V any] func(e1 Entry[K, V], e2 Entry[K, V]) bool

移除堆頂元素

這里和正常的堆的邏輯是一樣的，也就是把堆頂元素和最后一個元素交換，然后調(diào)整堆，移除堆中最后一個元素。

func (h *Meap[K, V]) Pop() Entry[K, V] {
	n := h.Len() - 1
	h.swap(0, n) // 堆頂和最后一個元素交換
	h.down(0, n) // 調(diào)整堆
	return h.pop() // 移除堆中最后一個元素
}

添加元素

這里的參數(shù)和普通的堆有一點區(qū)別，也就是我們有Key和Value，因為map必須使用一個Key，因此多了一個Key參數(shù)。

由于有map的存在，我們可以先判斷元素是否已經(jīng)存在，如果存在則設(shè)置Value然后調(diào)整堆即可。

如果不存在則添加元素到堆的最后，然后調(diào)整堆。

func (h *Meap[K, V]) Push(key K, value V) {
	// 如果堆中已經(jīng)包含這個元素
	// 更新值并調(diào)整堆
	if h.Contains(key) {
		index := h.m[key] // 元素在堆中下標
		h.h[index].Value = value // 更新堆中元素值
		h.fix(index) // 向上向下調(diào)整堆
		return
	}

	// 否則添加元素
	h.push(key, value) // 添加元素到堆的最后面
	h.up(h.Len() - 1) // 向上調(diào)整堆
}

移除元素

我們首先通過key定位元素在堆中下標，然后把這個下標和堆最后一個元素交換，調(diào)整堆，最后把堆最后一個元素移除。

func (h *Meap[K, V]) Remove(key K) {
	i, ok := h.m[key] // 獲取元素在堆中下標
	if !ok { // 如果元素不存在則直接返回
		return
	}

	n := h.Len() - 1 // 最后一個元素索引
	if n != i { // 如果被移除的元素就是堆中最后一個元素，則沒必要調(diào)整了，直接移除即可
		h.swap(i, n) // 和最后一個元素交換
		if !h.down(i, n) { // 向下調(diào)整
			h.up(i) // 向上調(diào)整
		}
	}
	h.pop() // 移除堆中最后一個元素
}

push()、pop()和swap()

涉及到調(diào)整map中index的操作都集中到這三個操作之中：

// swap兩個元素的時候
// 兩個元素在map里的下標也要交換
func (h *Meap[K, V]) swap(i, j int) {
	h.h[i], h.h[j] = h.h[j], h.h[i] // 交換兩個元素
	h.m[h.h[i].Key] = i // 更新索引
	h.m[h.h[j].Key] = j // 更新索引
}

// 添加一個元素到堆的末尾
func (h *Meap[K, V]) push(key K, value V) {
	h.m[key] = h.Len() // 添加索引
	h.h = append(h.h, Entry[K, V]{ // 添加元素到堆尾
		Key:   key,
		Value: value,
	})
}

// 從堆的末尾移除元素
func (h *Meap[K, V]) pop() Entry[K, V] {
	elem := h.h[h.Len()-1] // 堆尾元素
	h.h = h.h[:h.Len()-1] // 移除堆尾元素
	delete(h.m, elem.Key) // 刪除堆尾元素索引
	return elem
}

時間復(fù)雜度

上面Golang實現(xiàn)中關(guān)鍵操作的時間復(fù)雜度：

總結(jié)

map的引入解決了heap無法隨機刪除的問題，從而能夠解決更多的最值問題。其實還有其他的數(shù)據(jù)結(jié)構(gòu)也能夠高效的解決最值問題，比如紅黑樹能夠在O(log(n))獲取最大最小值，zset也可以在O(log(n))的復(fù)雜度下獲取最值，而且它們也是能夠支持隨機刪除。當然如果你所使用的語言不支持紅黑樹或者zset，那么使用map+heap實現(xiàn)也是可以的，畢竟實現(xiàn)一個可刪除的堆比實現(xiàn)一個紅黑樹或者zset容易很多，而且meap獲取最值的Peek()操作的時間復(fù)雜度是O(1)。