数据结构之堆(Heap)

堆(Heap)数据结构详解1. 基本概念堆是一种特殊的树形数据结构它满足以下两个关键性质结构性质堆是一棵完全二叉树Complete Binary Tree这意味着除了最后一层外其他层都是满的且最后一层的节点都尽可能靠左排列。堆序性质对于堆中的任意节点其值必须满足特定的顺序关系最大堆Max Heap父节点的值大于或等于其所有子节点的值最小堆Min Heap父节点的值小于或等于其所有子节点的值2. 堆的类型2.1 最大堆Max Heap在最大堆中根节点是堆中最大的元素。对于任意节点i其父节点的值大于或等于i的值。2.2 最小堆Min Heap在最小堆中根节点是堆中最小的元素。对于任意节点i其父节点的值小于或等于i的值。3. 堆的性质和特点3.1 完全二叉树性质堆总是保持完全二叉树的结构这使得堆可以用数组来高效表示插入和删除操作都能保持这个性质3.2 堆序性质最大堆保证父节点值 ≥ 子节点值最小堆保证父节点值 ≤ 子节点值这个性质保证了堆顶元素总是最大或最小值3.3 高效性插入操作O(log n)删除操作O(log n)查找最大/最小值O(1)4. 堆的数组表示由于堆是完全二叉树我们可以用数组来表示它而不需要显式地存储树结构。这种表示方法非常高效对于索引为i的节点左子节点索引2i 1右子节点索引2i 2父节点索引(i - 1) // 24.1 数组表示示例索引 0 1 2 3 4 5 6 7 8 值 100 19 36 17 3 25 1 2 75. 堆的基本操作5.1 插入操作Insert插入操作需要保持堆的性质将新元素添加到堆的末尾向上调整Heapify Up/Sift Up将新元素与其父节点比较如果违反堆序性质则交换重复步骤2直到堆序性质满足5.2 删除操作Delete通常删除操作是指删除堆顶元素将堆顶元素与最后一个元素交换删除最后一个元素向下调整Heapify Down/Sift Down将新的堆顶元素与其子节点比较如果违反堆序性质则交换重复步骤3直到堆序性质满足5.3 建堆操作Build Heap从无序数组构建堆从最后一个非叶子节点开始对每个节点执行向下调整逐步向前处理所有节点6. 代码实现6.1 Python实现classMaxHeap:def__init__(self):self.heap[]defparent(self,i):return(i-1)//2defleft_child(self,i):return2*i1defright_child(self,i):return2*i2definsert(self,key):self.heap.append(key)self._heapify_up(len(self.heap)-1)def_heapify_up(self,i):whilei0andself.heap[self.parent(i)]self.heap[i]:self.heap[self.parent(i)],self.heap[i]self.heap[i],self.heap[self.parent(i)]iself.parent(i)defextract_max(self):ifnotself.heap:returnNoneiflen(self.heap)1:returnself.heap.pop()rootself.heap[0]self.heap[0]self.heap.pop()self._heapify_down(0)returnrootdef_heapify_down(self,i):max_indexi leftself.left_child(i)rightself.right_child(i)ifleftlen(self.heap)andself.heap[left]self.heap[max_index]:max_indexleftifrightlen(self.heap)andself.heap[right]self.heap[max_index]:max_indexrightifmax_index!i:self.heap[i],self.heap[max_index]self.heap[max_index],self.heap[i]self._heapify_down(max_index)defget_max(self):returnself.heap[0]ifself.heapelseNonedefsize(self):returnlen(self.heap)classMinHeap:def__init__(self):self.heap[]defparent(self,i):return(i-1)//2defleft_child(self,i):return2*i1defright_child(self,i):return2*i2definsert(self,key):self.heap.append(key)self._heapify_up(len(self.heap)-1)def_heapify_up(self,i):whilei0andself.heap[self.parent(i)]self.heap[i]:self.heap[self.parent(i)],self.heap[i]self.heap[i],self.heap[self.parent(i)]iself.parent(i)defextract_min(self):ifnotself.heap:returnNoneiflen(self.heap)1:returnself.heap.pop()rootself.heap[0]self.heap[0]self.heap.pop()self._heapify_down(0)returnrootdef_heapify_down(self,i):min_indexi leftself.left_child(i)rightself.right_child(i)ifleftlen(self.heap)andself.heap[left]self.heap[min_index]:min_indexleftifrightlen(self.heap)andself.heap[right]self.heap[min_index]:min_indexrightifmin_index!i:self.heap[i],self.heap[min_index]self.heap[min_index],self.heap[i]self._heapify_down(min_index)defget_min(self):returnself.heap[0]ifself.heapelseNonedefsize(self):returnlen(self.heap)6.2 Java实现publicclassMaxHeap{privateint[]heap;privateintsize;privateintmaxSize;publicMaxHeap(intmaxSize){this.maxSizemaxSize;this.size0;heapnewint[maxSize];}privateintparent(intpos){return(pos-1)/2;}privateintleftChild(intpos){return2*pos1;}privateintrightChild(intpos){return2*pos2;}privatebooleanisLeaf(intpos){returnpos(size/2)possize;}publicvoidinsert(intelement){if(sizemaxSize){return;}heap[size]element;intcurrentsize;size;while(heap[current]heap[parent(current)]){swap(current,parent(current));currentparent(current);}}publicintextractMax(){if(size0){returnInteger.MIN_VALUE;}if(size1){size--;returnheap[0];}intpoppedheap[0];heap[0]heap[size-1];size--;heapifyDown(0);returnpopped;}privatevoidheapifyDown(intpos){if(!isLeaf(pos)){intleftleftChild(pos);intrightrightChild(pos);intlargestpos;if(leftsizeheap[left]heap[largest]){largestleft;}if(rightsizeheap[right]heap[largest]){largestright;}if(largest!pos){swap(pos,largest);heapifyDown(largest);}}}privatevoidswap(intfpos,intspos){inttmpheap[fpos];heap[fpos]heap[spos];heap[spos]tmp;}}publicclassMinHeap{privateint[]heap;privateintsize;privateintmaxSize;publicMinHeap(intmaxSize){this.maxSizemaxSize;this.size0;heapnewint[maxSize];}privateintparent(intpos){return(pos-1)/2;}privateintleftChild(intpos){return2*pos1;}privateintrightChild(intpos){return2*pos2;}privatebooleanisLeaf(intpos){returnpos(size/2)possize;}publicvoidinsert(intelement){if(sizemaxSize){return;}heap[size]element;intcurrentsize;size;while(heap[current]heap[parent(current)]){swap(current,parent(current));currentparent(current);}}publicintextractMin(){if(size0){returnInteger.MAX_VALUE;}if(size1){size--;returnheap[0];}intpoppedheap[0];heap[0]heap[size-1];size--;heapifyDown(0);returnpopped;}privatevoidheapifyDown(intpos){if(!isLeaf(pos)){intleftleftChild(pos);intrightrightChild(pos);intsmallestpos;if(leftsizeheap[left]heap[smallest]){smallestleft;}if(rightsizeheap[right]heap[smallest]){smallestright;}if(smallest!pos){swap(pos,smallest);heapifyDown(smallest);}}}privatevoidswap(intfpos,intspos){inttmpheap[fpos];heap[fpos]heap[spos];heap[spos]tmp;}}7. 时间复杂度分析操作时间复杂度说明插入O(log n)向上调整的高度为树的高度删除O(log n)向下调整的高度为树的高度查找最大/最小值O(1)堆顶元素建堆O(n)从数组构建堆的优化算法堆排序O(n log n)利用堆进行排序8. 堆的应用场景8.1 优先队列堆是实现优先队列的理想数据结构可以高效地获取和删除优先级最高的元素。8.2 堆排序堆排序算法利用堆的性质可以在O(n log n)时间内完成排序。8.3 Top K问题在大量数据中找到前K个最大或最小元素。8.4 图算法Dijkstra算法中的优先队列Prim算法中的最小生成树8.5 内存管理操作系统中的内存分配和回收。8.6 事件调度按时间顺序处理事件。9. 堆的变种9.1 二叉堆最常用的堆结构本文讨论的主要类型。9.2 斐波那契堆具有更好理论性能的堆结构适用于某些特定算法。9.3 二项堆由二项树组成的堆结构。9.4 左偏堆一种自平衡的二叉堆变体。10. 总结堆是一种非常重要的数据结构它结合了数组的连续存储优势和树结构的有序性。通过完全二叉树的性质堆能够高效地支持插入、删除和查找操作特别适合需要频繁获取最大或最小值的场景。理解堆的原理和实现对于算法设计和系统优化都具有重要意义。