后台堆是一种非常常用的数据结构，可以支持在O(1)时间复杂度内获取最大值（或最小值）)，所以我们经常在需要找到最大价值的场景中使用它。但是，普通堆有一个缺点。它不能快速定位到一个元素，所以它不能快速删除堆中的一个元素。它需要遍历整个堆来查询目标元素。时间复杂度为O(n)，因为堆结构在逻辑上是这样的：在实际实现中，一般用一个数组来模拟：即除了最大值（大堆顶）或最小值（小堆顶）heap），其他元素其实是没有排序的，所以没办法通过二分查找快速定位。但是，我们经常会有这样的场景，需要堆的性质可以快速找到最大值，还需要能够支持快速随机访问元素，尤其是删除元素。比如在延迟任务的场景下，我们可以使用堆对任务的过期时间戳进行排序，从而实现过期任务的自动执行，但是不能支持随机删除一个延迟任务的需求。下面将介绍一个支持O(log(n))随机删除元素的堆。原理数据结构一种可以快速随机访问元素的数据结构是map。如果map实现为哈希表，它可以随机访问任意一个元素，复杂度为O(1)，heap知道要删除的元素的下标。在这种情况下，也可以在O(log(n))复杂度中删除一个元素。因此，我们可以结合这两种数据结构，用map记录堆中每个元素的下标，利用堆获取最大的值。比如上面的堆，我们先给每个元素添加一个Key，这样我们就可以使用map了：然后我们用map记录每个key对应的下标：随机访问这时候比如我们最简单的随机访问一个元素C，那么从map[C]中得到元素在堆中的index=2，所以可以得到元素的值。index=m[C]//获取堆中元素C的下标returnh[index]//获取要删除的堆中index的值，如果要删除元素C，我们也获取堆中的元素heapfrommap[C]index=2，然后将index为2的元素与heap的最后一个元素交换，然后对heapfromindex=2进行上下调整，即：index=m[C]//Get堆中元素C的下标swap(index,n-1)//与最后一个元素交换pop()//移除最后一个元素，即元素Cdown(index)//调整堆从索引向下向上(index)//upfromindex调整堆图中元素的索引并维护。上面使用的swap(i,j)和pop()操作将影响地图中元素的索引。实际上，push(k,v)操作也会影响元素的索引。对于swap(i,j)，需要交换两个元素的索引：h[i],h[j]=h[j],h[i]//交换m[h[i]中的两个元素theheap.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中的索引问题，实现逻辑与普通堆基本一致。Golang意识到这个数据结构使用了map和heap，所以它有一个比较短的名字叫meap，即m[ap]+[h]eap。数据结构主要由堆和映射组成。由于我们还需要从堆中对map进行操作，所以堆中的每个元素Entry都记录了Key，这样就可以快速从堆中访问到map中的元素，实现了map。索引修改。LessFunc主要用于比较两个元素的大小：typeMeap[Kcomparable,Vany]struct{h[]Entry[K,V]mmap[K]intlessFuncLessFunc[K,V]}typeEntry[Kcomparable,Vany]struct{KeyKValueV}typeLessFunc[Kcomparable,Vany]func(e1Entry[K,V],e2Entry[K,V])bool移除堆顶元素这里是和普通堆的逻辑是一样的，就是将堆顶元素和最后一个元素交换，然后调整堆，移除堆中最后一个元素。func(h*Meap[K,V])Pop()Entry[K,V]{n:=h.Len()-1h.swap(0,n)//交换h。down(0,n)//调整堆returnh.pop()//移除堆中的最后一个元素}添加一个元素这里的参数和普通堆有点不同，就是我们有Key和Value，因为map必须使用Key，所以多了一个Key参数。由于map的存在，我们可以先判断元素是否已经存在，如果存在则设置Value，然后调整堆。如果元素不存在则将元素添加到堆的末尾，然后调整堆。func(h*Meap[K,V])Push(keyK,valueV){//如果元素已经包含在堆中//更新值并调整堆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{//元素不存在则直接返回exist}n:=h.Len()-1//最后一个元素索引ifn!=i{//如果被移除的元素是堆中的最后一个元素，则不需要调整，直接移除h.swap(i,n)//与最后一个元素交换if!h.down(i,n){//向下调整h.up(i)//向上调整}}h.pop()//移除最后一个heap中的元素}push()、pop()和swap()涉及调整map中的索引都集中在这三个操作中：//当交换两个元素时//两个元素在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]//堆尾elementh.h=h.h[:h.Len()-1]//移除堆尾元素delete(h.m,elem.Key)//删除堆尾元素索引returnelem}时间复杂度keyinGolangimplementationaboveTimecomplexityofoperation:操作时间复杂度描述Push()O(log(n))addelementPop()O(log(n))removeheaptopelementPeek()O(1)getheaptopelementGet()O(1)获取元素删除()O(log(n))删除元素总结map的引入解决了堆不能随机删除的问题，从而解决更多的最大值问题。其实还有其他数据结构可以高效解决最大值问题，比如红黑树可以在O(log(n))下获取最大值和最小值，zset也可以在O(log(n))下获取最大值O(log(n))的复杂度，并且它们还可以支持随机删除。当然如果你使用的语言不支持红黑树或者zset，使用map+heap也是可以的。毕竟实现可删除堆比实现红黑树或者zset要简单的多，而且meap获得最有价值的Peek()操作的时间复杂度是O(1)。作者：jiaxwu链接：https://juejin.cn/post/7145833385389195271来源：稀土掘金版权归作者所有。商业转载请联系作者授权，非商业转载请注明出处。
