第詳解Golang如何實現(xiàn)支持隨機刪除元素的堆目錄背景原理數(shù)據(jù)結構隨機訪問刪除map里面的元素index維護Golang實現(xiàn)數(shù)據(jù)結構移除堆頂元素添加元素移除元素push()、pop()和swap()時間復雜度總結

背景

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

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

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

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

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

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

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

原理

數(shù)據(jù)結構

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

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

然后我們使用map記錄每個key對應的下標：

隨機訪問

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

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

returnh[index]//獲取index在heap的值

刪除

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

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

swap(index,n-1)//和最后一個元素交換

pop()//移除最后一個元素，也就是元素C

down(index)//從index向下調整堆

up(index)//從index向上調整堆

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ù)結構使用到了map和heap，因此起了一個比較短的名字叫meap，也就是m[ap]+[h]eap。

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

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

typeMeap[Kcomparable,Vany]struct{

h[]Entry[K,V]

mmap[K]int

lessFuncLessFunc[K,V]

typeEntry[Kcomparable,Vany]struct{

KeyK

ValueV

typeLessFunc[Kcomparable,Vany]func(e1Entry[K,V],e2Entry[K,V])bool

移除堆頂元素

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

func(h*Meap[K,V])Pop()Entry[K,V]{

n:=h.Len()-1

h.swap(0,n)//堆頂和最后一個元素交換

h.down(0,n)//調整堆

returnh.pop()//移除堆中最后一個元素

}

添加元素

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

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

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

func(h*Meap[K,V])Push(keyK,valueV){

//如果堆中已經(jīng)包含這個元素

//更新值并調整堆

ifh.Contains(key){

index:=h.m[key]//元素在堆中下標

h.h[index].Value=value//更新堆中元素值

h.fix(index)//向上向下調整堆

return

//否則添加元素

h.push(key,value)//添加元素到堆的最后面

h.up(h.Len()-1)//向上調整堆

}

移除元素

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

func(h*Meap[K,V])Remove(keyK){

i,ok:=h.m[key]//獲取元素在堆中下標

if!ok{//如果元素不存在則直接返回

return

n:=h.Len()-1//最后一個元素索引

ifn!=i{//如果被移除的元素就是堆中最后一個元素，則沒必要調整了，直接移除即可

h.swap(i,n)//和最后一個元素交換

if!h.down(i,n){//向下調整

h.up(i)//向上調整

h.pop()//移除堆中最后一個元素

}

push()、pop()和swap()

涉及到調整map中index的操作都集中到這三個操作之中：

//swap兩個元素的時候

//兩個元素在map里的下標也要交換

func(h*Meap[K,V])swap(i,jint){

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(keyK,valueV){

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)//刪除堆尾元素索引

returnelem

}

時間復雜度

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

操作時間復雜度描述Push()O(log(n))添加元素Pop()O(log(n))移除堆頂元素Peek()O(1)獲取堆頂元素Get()O(1)獲取元素Remove()O(log(n))刪除元素

總結

map的引入解決了heap無法隨機刪除的問題，從而能夠解決更多的