在本文中，我们将了解 Python 中的堆是什么以及怎样实现它。我们将通过最小堆的 python 程序实现来理解堆的概念。最后，我们将学习堆数据结构的时间复杂度和应用。那么，让我们开始吧！
什么是堆？
堆是一种遵循“完全”二叉树属性并满足堆属性的数据结构。因此，它也被称为二叉堆。完全二叉树是每一层都被填满，并且所有节点都尽可能靠左的树。在二叉树中，有可能最后一层是空的并且没有被填充。在堆数据结构中，我们为树的每个节点分配键值或权重。将根节点键值与子节点进行比较，然后根据比较大小将树相应地排列为两类，即最大堆和最小堆。堆数据结构可以用作堆排序算法来对数组或列表中的元素进行排序。堆排序算法可用于优先队列、订单统计、Prim 算法或Dijkstra 算法等。简而言之，堆数据结构在要重复删除最高或最低优先级对象时经常被使用。
建堆-Heapify？
首先我们需要了解什么是 heapify。使用二叉树创建堆数据结构的过程称为 Heapify。heapify 过程用于创建 Max-Heap 或 Min-Heap。让我们使用下面的示例来研究 Heapify：
考虑如下图所示的输入数组：
使用这个数组，我们将创建完整的二叉树。 我们从最后一个非叶子节点 (len(array)//2-1) 开始，将其作为当前的节点。如果要创建Min-Heap,我们要保证任何当前节点小于他的两个子节点。设当前节点的序号是k，那么其左子节点的序号是2k+1，右子节点是2k+2。Heapify就是要保证上述的局部性质，首先完成父节点的heapify，还要沿着一条树的路径递归完成子节点的heapify。接下来就是倒着数组序号进行Heapify，这样就完成了整个数组的堆化。数组在堆化过程中是以如下方式变化的：[3, 9, 2, 1, 4, 5]--> [3, 1, 2, 9, 4, 5]--> [3, 1, 2, 9, 4, 5]--> [1, 3, 2, 9, 4, 5]。以下程序演示了怎样heapify一个数组。时间复杂度是O(nlogn)
def min_heapify(A,k):
print(A)
l = left(k)
r = right(k)
if l < len(A) and A[l] < A[k]:
smallest = l
else:
smallest = k
if r < len(A) and A[r] < A[smallest]:
smallest = r
if smallest != k:
A[k], A[smallest] = A[smallest], A[k]
min_heapify(A, smallest)
def left(k):
return 2 * k + 1
def right(k):
return 2 * k + 2
def build_min_heap(A):
n = int((len(A)//2)-1)
for k in range(n, -1, -1):
min_heapify(A,k)
A = [3,9,2,1,4,5]
build_min_heap(A)理解min-heapify函数
此函数可以将节点及其所有后代（子节点及其子节点）遵循堆属性。它通过交换节点的键值来重新组织堆里的数据，使得当前节点成为其子树中的最小节点，遵循堆属性。
该函数首先在给定节点及其子节点中找到具有最小值的节点。然后它将给定节点（比如 i）与找到的最小值节点（比如 j）交换，然后在节点 j 上（递归地）调用 min-heapify 函数，以确保分配给节点 j 的新值确实不要破坏其子树中的堆属性。由于最多要遍历树的深度，所以它的时间复杂度是O(d)，其中d是深度，或者，就节点数而言，O(log n)，n是堆中的元素。
退出堆顶元素：heappop函数
该函数弹出堆的最小值（根元素）。
这实际上是通过将根节点与最后一个节点交换并删除现在的最后一个节点（包含最小值）然后为根节点调用 min-heapify 以在由于交换引起的更改后维护堆属性来完成的。
由于我们只需要调用一次min-heapify，因此时间复杂度为 O(log n)，其中 n 是元素的数量，或者 O(h)，其中 h 是树的高度，即 log n。
加入新元素：heappush 函数
此函数将一个新元素推入堆中，并将其排列到正确的位置，同时保持堆属性。
这实际上是通过在堆的末尾添加一个新节点来完成的。现在为了维护堆属性，我们从最后一个节点向上遍历（并在需要的地方交换）以修复可能被违反的堆属性。
与 heappop 类似，这里的时间复杂度是 O(log n)，因为我们只需要遍历子树的高度。
获得最小值：extractMin 函数
此函数从堆中返回最高优先级（根元素）。由于我们只需要返回根的值而不对堆进行任何更改，并且根在 O(1) 时间内可以访问，因此函数的时间复杂度为 O(1)。
import sys
#defining a class min_heap for the heap data structure
class min_heap:
def __init__(self, sizelimit):
self.sizelimit = sizelimit
self.cur_size = 0
self.Heap = [0]*(self.sizelimit + 1)
self.Heap[0] = sys.maxsize * -1
self.root = 1
# helper function to swap the two given nodes of the heap
# this function will be needed for heapify and insertion to swap nodes not in order
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
# THE MIN_HEAPIFY FUNCTION
def min_heapify(self, i):
# If the node is a not a leaf node and is greater than any of its child
if not (i >= (self.cur_size//2) and i <= self.cur_size: if self.heapi> self.Heap[2 * i] or self.Heap[i] > self.Heap[(2 * i) + 1]):
if self.Heap[2 * i] < self.heap2 i 1: swap the node with the left child and then call the min_heapify function it self.swapnodesi 2 i self.min_heapify2 i else: swap the node with right child and then call the min_heapify function it self.swapnodesi 2 i 1 self.min_heapify2 i 1 the heappush function def heappushself element: if self.cur_size>= self.sizelimit :
return
self.cur_size+= 1
self.Heap[self.cur_size] = element
current = self.cur_size
while self.Heap[current] < self.Heap[current//2]:
self.swapnodes(current, current//2)
current = current//2
# THE HEAPPOP FUNCTION
def heappop(self):
last = self.Heap[self.root]
self.Heap[self.root] = self.Heap[self.cur_size]
self.cur_size -= 1
self.min_heapify(self.root)
return last
# THE BUILD_HEAP FUNCTION
def build_heap(self):
for i in range(self.cur_size//2, 0, -1):
self.min_heapify(i)
# helper function to print the heap
def print_heap(self):
for i in range(1, (self.cur_size//2)+1):
print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) + " Right Child is "+ str(self.Heap[2 * i + 1]))
# Driver Code
minHeap = min_heap(10)
minHeap.heappush(15)
minHeap.heappush(7)
minHeap.heappush(9)
minHeap.heappush(4)
minHeap.heappush(13)
minHeap.print_heap()