背景

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

然而普通堆它有一個(gè)缺點(diǎn)，它沒(méi)辦法快速的定位一個(gè)元素，因此它也沒(méi)辦法快速刪除一個(gè)堆中元素，需要遍歷整個(gè)堆去查詢目標(biāo)元素，時(shí)間復(fù)雜度是O(n)，因?yàn)槎训慕Y(jié)構(gòu)在邏輯上是這樣的：

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

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

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

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

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

原理

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

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

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

然后我們使用map記錄每個(gè)key對(duì)應(yīng)的下標(biāo)：

隨機(jī)訪問(wèn)

這時(shí)候比如我們最簡(jiǎn)單的隨機(jī)訪問(wèn)一個(gè)元素C，那么就是從map[C]得到元素在heap里面的index=2，因此可以拿到元素的值。

index = m[C] // 獲取元素C在heap的下標(biāo)
return h[index] // 獲取index在heap的值

刪除

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

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

map里面的元素index維護(hù)

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

對(duì)于swap(i, j)來(lái)說(shuō)需要交換兩個(gè)元素的index：

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

pop()需要?jiǎng)h除元素的索引：

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

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

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

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

Golang實(shí)現(xiàn)

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

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

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

LessFunc主要用于比較兩個(gè)元素大小。

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

移除堆頂元素

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

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

添加元素

這里的參數(shù)和普通的堆有一點(diǎn)區(qū)別，也就是我們有Key和Value，因?yàn)閙ap必須使用一個(gè)Key，因此多了一個(gè)Key參數(shù)。

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

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

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

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

移除元素

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

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

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

push()、pop()和swap()

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

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

// 添加一個(gè)元素到堆的末尾
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
}

時(shí)間復(fù)雜度

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

總結(jié)

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

到此這篇關(guān)于詳解Golang如何實(shí)現(xiàn)支持隨機(jī)刪除元素的堆的文章就介紹到這了,更多相關(guān)Golang隨機(jī)刪除元素內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論