二叉堆与优先队列

二叉堆是一种支持插入、删除、查询最值的数据结构即是满足“堆性质”的完全二叉树树的每一个节点都带有一个权值如果对于树的每一个节点的权值都小于等于其父节点的权值则该完全二叉树为“大根堆”反之为“小根堆”。priority_queue(优先队列,这里容易踩坑优先队列并不是有序队列它只保证堆顶最大/最小整体并不排序大家看到下面自然就会明白)通常就是由二叉堆实现的默认是“大根堆”priority_queueint max_heap;当然也可以自定义“小根堆”只需要多提供两个模板参数底层容器类型和比较函数。// greaterint 表示数字越小优先级越高 priority_queueint,vectorint,greaterintmin_heap;对于自定义数据类型也可以通过重载运算符使priority_queue实现“大根堆”和“小根堆”struct Node { int x,w; bool operator(const Nodeu)const { return wu.w;//小根堆return wu.w;//大根堆 } }; priority_queue Node pq;但是priority_queue只支持push()、top()、pop()的操作不支持Remove()操作即将某个节点从二叉树中删除这就需要我们通过手写堆来实现我们如果逐层从左往右为树中的节点依次编号并且将此编号作为节点在数组中存储的位置下标这里也是用到了映射的思想我们会发现父节点的编号等于子节点编号除于2左子节点编号等于父节点编号乘2右子节点编号等于父节点编号乘2加1这是写手写堆的关键以“大根堆”为例如图16(1) / \ 14(2) 10(3) / \ / 8(4) 7(5) 9(6) heap[]{0,16,14,10,8,7,9};一般手写堆的常见操作InsrertInsert(val)操作是向二叉堆中插入一个带有权值val的新节点将这个新节点首先放在用于存储二叉堆的数组末尾然后再向上不断交换直至满足该二叉堆的性质时间复杂度为堆的深度即O(log n)。int heap[N],n; void up(int p)//向上调整 { while(p1) { if(heap[p]heap[p/2])//子节点父节点 { swap(heap[p],heap[p/2]); p/2; } else break; } } void Insert(int val) { heap[n]val; up(n); }GetTopGetTop()操作返回二叉堆的堆顶权值即最大值heap[1],时间复杂度O(1)。int GetTop() { return heap[1]; }ExtractExtract()操作是将堆顶二叉堆中移除。首先将堆顶heap[1]与存储在数组末尾的节点heap[n]交换然后删除数组末尾节点(n--)最后将堆顶通过交换的方式向下调整直至满足堆性质。时间复杂度为堆的深度即O(log(n))。int heap[N],n; void down(int p)//向下调整 { int xp*2//p的左子节点 while(xn) { if(xnheap[x]heap[x1]) x;//左右子节点中取最大的 if(heap[x]heap[p])//子节点大于父节点 { swap(heap[x],heap[p]); px,xp*2; } else break; } } void Extract() { heap[1]heap[n--]; down(1); }RemoveRemove(p)操作是将p位置节点从二叉堆中删除先把heap[p]与heap[n]交换然后令n--注意此时heap[p]可能向下或向上调整来满足此堆性质时间复杂度仍为O(log n)。void Remove(int p) { heap[p]heap[n--]; up(p),down(p); }