HeapHeapHeap：一种可以在一堆数字中快速找到最大值或最小值的数据结构。根节点最大的堆称为大顶堆或大根堆，根节点最小的堆称为小顶堆或小根堆。常见的堆有二叉堆、斐波那契堆等，堆本身是一个比较抽象的数据结构，所以有具体的实现，可以分为二叉堆（binaryheaps，Binary）和斐波那契堆（tree-based）。那么如果要实现的话，二叉堆一般面试还是经常用到。当然，在工业级应用比较厉害的还是Fibonacci和非常严格的Fibonacci。因为斐波那契堆比较复杂，你可能不知道怎么实现，但是你可以看到它的时空复杂度比较好。它的实现也是基于树的，但是二叉树不是很多而是多叉的。假设是一个大顶堆，常用操作（API）：find-max:O(1)delete-max:O(logN)insert(create):O(logN)orO(1)"heap"这种数据结构为什么有用？它经常用于许多在线情况。比如经常一个一个的统计，同时也经常从另一边删除一些数据。这些数据的最大值是多少？多少？这里的最大值可能代表优先级最高的节点，也可能代表需要最先处理的节点数。例如，在你的任务流中，你需要取出优先级最高的任务，先处理它。那么这个数据结构就更加有用了。可能有人会疑惑我是不是可以用数组来实现呢？还是可以直接排序？这里我们可以想一下：假设维护一个数组，每插入一个新的元素，就需要执行一次所谓的操作，这样的话，时间复杂度就会是nlogn，效率不够。另外，删除可能比较麻烦。如果最后删除最大值或最小值也可以。可以是O(1)的时间复杂度，但是如果在最顶层，就得把整个数组的前面元素删掉，然后把整个数组往前移，这样时间复杂度又变差了。不同实现的比较：https://en.wikipedia.org/wiki/Heap_(data_structure)当你提到“堆”时，不要以为它默认就是二叉堆。同时你要知道堆的实现有很多种。二叉堆本身只是因为实现起来比较容易，它的时间效率在堆中是比较差的。二叉堆的本质是通过完全二叉树实现的（注意：不是二叉搜索树）；什么是完全二叉树？即它的根和每一层节点都是满的，除了最底层的叶子节点可能不是满的，其他上层节点都是满的。二叉堆（bigtop）满足以下性质：性质1：是一棵完全树；性质2：树中任意节点的总值>=其子节点的值；由于性质2，可以保证根节点是最大的节点，所以我们在访问最大值的时候直接返回根节点的值。这里有个问题要思考：为什么要做树状结构？其实很方便，因为找最大值是O(1)，还算满意，但是问题是如果后面要删除一个元素或者添加一个元素，怎么办？让这个操作高效，至少logn。二叉堆的实现细节二叉堆一般都是通过“数组”来实现的。假设数组中“第一个元素”的索引为0，则父节点与子节点的位置关系如下：索引为i的左节点子节点的索引为(2?i+1);索引为i的右孩子的索引为(2*i+2)；索引为i的父节点的索引为floor((i?1)/2)；因为一棵完全二叉树是依次放在一个一维数组中的，那么它的孩子和父亲的关系就可以直接用下班的数学关系来表示了。插入操作新元素总是先插入到堆尾，然后向上（一直到根）调整整个堆的结构HeapifyUp当堆需要维护的时候，也就是插入元素的时候，当你想删除元素，怎么办？该怎么办？例子：85添加到二叉堆的细节分为两步：第一步：先在堆尾插入新元素；（新的元素可能特别大，也可能特别小，所以要做的一件事就是重新维护堆的所有元素，把新的元素移动到堆的相应位置）第二步：调整结构依次将整个堆，称为HeapifyUp85，按照上面的方法插入到堆的末尾。也就是一维数组的尾部，一维数组的尾部就是上图中的位置，因为这是一棵完全二叉树，所以它的尾部就是50之后的节点。插入之后，heap此时会被销毁。它的每个节点都必须大于其儿子的属性。接下来要做的就是85一个一个往上漂。如何漂浮？即85大于其父节点，则与父节点交换，直到根大于根，再与根交换。85继续往前走后，需要再次和80进行比较，可以得到同一个道理：也就是说，每次这个节点和它的父亲比较，如果大于它的父亲，则交换直到它不再大于它的父亲。DeleteMax删除堆顶操作将堆尾元素替换到堆顶（即堆顶替换删除）然后从根向下调整整个堆的结构（一直到堆尾）heap)HeapifyDown示例：90从二叉堆中删除Heap实现代码模板Java版//Javaimportjava.util.Arrays;importjava.util.NoSuchElementException;publicclassBinaryHeap{privatestaticfinalintd=2;privateint[]heap;privateintheapSize;/***Thiswillinitializeourheapwithdefaultsize。*/publicBinaryHeap(intcapacity){heapSize=0;heap=newint[capacity+1];Arrays.fill(heap,-1);}publicbooleanisEmpty(){returnheapSize==0;}publicbooleanisFull(){returnheapSize==heap。length;}privateintparent(inti){return(i-1)/d;}privateintkthChild(inti,intk){returnd*i+k;}/***Insertsnewelementintoheap*Complexity:O(logN)*Asworstcasescenario,weneedtotraversetilltheroot*/publicvoidinsert(intx){if(isFull()){thrownewNoSuchElementException("Heapisfull,Nospacetoinsertnewelement");}heap[heapSize]=x;heapSize++;heapifyUp(heapSize-1);}/***Deleteselementatindexx*复杂度:O(logN)*/publicintdelete(intx){if(isEmpty()){thrownewNoSuchElementException(“堆空，Noelementtodelete");}intmaxElement=heap[x];heap[x]=heap[heapSize-1];heapSize--;heapifyDown(x);returnmaxElement;}/***在插入元素时保持堆属性。*/privatevoidheapifyUp(inti){intinsertValue=heap[i];while(i>0&&insertValue>heap[parent(i)]){heap[i]=heap[parent(i)];i=parent(i);}heap[i]=insertValue;}/***在删除元素时保持堆属性。*/privatevoidheapifyDown(inti){intchild;inttemp=heap[i];while(kthChild(i,1)=heap[child]){break;}heap[i]=heap[child];i=child;}heap[i]=temp;}privateintmaxChild(inti){intleftChild=kthChild(i,1);intrightChild=kthChild(i,2);returnheap[leftChild]>heap[rightChild]?leftChild:rightChild;}/***Printsallelementsoftheheap*/publicvoidprintHeap(){System.out.print("nHeap=");for(inti=0;iusingnamespacestd;classBinaryHeap{public:BinaryHeap(intcapacity);voidinsert(intx);interase(intx);intfindMax();voidprintHeap();boolisEmpty(){returnheapSize==0;}boolisFull(){returnheapSize==capacity;}~BinaryHeap(){delete[]heap;}private:voidheapifyUp(inti);voidheapifyDown(inti);intmaxChild(inti);intparent(inti){return(i-1)/2;}intkthChild(inti,intk){return2*i+k;}private:int*heap;intheapSize;intcapacity;};/***Thiswillinitializeourheapwithdefaultsize.*/BinaryHeap::BinaryHeap(intcapacity){this->heapSize=0;this->capacity=capacity;this->heap=newint[capacity+5];}/***Insertsnewelementintoheap*Complexity:O(logN)*Asworstcasescenario,weneedtotraversetilltheroot*/voidBinaryHeap::insert(intx){try{if(isFull())throw-1;heap[heapSize]=x;heapSize++;heapifyUp(heapSize-1);return;}catch(inte){cout<<"Heapisfull,Nospacetoinsertnewelement"<0&&insertValue>heap[parent(i)]){heap[i]=heap[parent(i)];i=parent(i);}heap[i]=insertValue;}/***在删除元素时保持堆属性。*/voidBinaryHeap::heapifyDown(inti){intchild;inttemp=heap[i];while(kthChild(i,1)=heap[child]){break;}heap[i]=heap[child];i=child;}heap[i]=temp;}intBinaryHeap::maxChild(inti){intleftChild=kthChild(i,1);intrightChild=kthChild(i,2);returnheap[leftChild]>heap[rightChild]?leftChild:rightChild;}/***此方法返回堆的最大元素。*复杂度：O(1)*/intBinaryHeap::findMax(){try{if(isEmpty())throw-1;returnheap[0];}catch(inte){cout<<"Heapisempty."<0&&this.compare(value,this.data[Math.floor((index-1)/2)])<0){this.data[index]=this.data[Math.floor((index-1)/2)];this.data[Math.floor((index-1)/2)]=value;index=Math.floor((index-1)/2);}}delete(index){if(this.data.length===0)return;letvalue=this.data[index];leti=index;//fixheapwhile(i=this.data.length)break;//无右子节点if(right>=this.data.length){this.data[i]=this.data[left];i=left;break;}//比较左右子节点的大小，较小的添加到父节点if(this.compare(this.data[left],this.data[right])<0){this.data[i]=this.data[left];i=left;}else{this.data[i]]=this.data[right];i=right;}}//检查最后一个vacancy是最后一个叶节点if(ib-a);maxHeap.insert(10);maxHeap.insert(4);maxHeap.insert(9);maxHeap.insert(1);maxHeap.insert(7);maxHeap.insert(5);maxHeap.insert(3);maxHeap.printHeap();maxHeap.delete(5);maxHeap.printHeap();maxHeap.delete(2);maxHeap.printHeap();Python版本PythonimportsysclassBinaryHeap:def__init__(self,capacity):self.capacity=capacityself.size=0self.Heap=[0]*(self.capacity+1)self.Heap[0]=-1*sys.maxsizeself.FRONT=1defparent(self,pos):returnpos//2defleftChild(self,pos):return2*posdefrightChild(self,pos):return(2*pos)+1defisLeaf(self,pos):ifpos>=(self.size//2)andpos<=self.size:returnTruereturnFalsedefswap(self,fpos,spos):self.Heap[fpos],self.Heap[spos]=self.Heap[spos],self.Heap[fpos]defheapifyDown(self,pos):ifnotself.isLeaf(pos):if(self.Heap[pos]>self.Heap[self.leftChild(pos)]orself.Heap[pos]>self.Heap[self.rightChild(pos)]):ifself.Heap[self.leftChild(pos)]=self.capacity:returnsself.size+=1self.Heap[self.size]=elementcurrent=self.sizewhileself.Heap[current]
