数据结构-堆

1. 定义：

堆是一种特殊的完全二叉树。在堆中，所有的父节点都满足特定的顺序关系（大于或小于）与它们的子节点。这种属性使得堆在处理优先级队列和排序操作时非常有效。

2. 类型：

常见的两种类型的堆是最大堆和最小堆。在最大堆中，每个父节点的值都大于或等于其子节点的值；而在最小堆中，每个父节点的值都小于或等于其子节点的值。

3. 操作：

主要操作包括插入（添加新元素）和删除（移除顶部元素）。插入操作涉及将新元素添加到堆的末尾，然后进行上浮调整。删除操作通常移除顶部元素，然后将末尾元素移到顶部，并进行下沉调整以保持堆的属性。
在 Python 中，可以使用 heapq 模块来表示和操作堆数据结构。heapq 提供了一些实用函数来操作最小堆和最大堆（可以通过对输入数据的负值进行处理来实现最大堆）。堆通常是一种二叉堆数据结构，是一种特殊的树结构，它满足堆的性质，即父节点的值小于或等于其子节点的值。
下面是一些 heapq 模块的基本操作示例：

1. heapq.heappush(heap, item)：向堆中插入一个元素 item。
2. heapq.heappop(heap)：从堆中弹出最小元素，并返回该元素。
3. heapq.heapify(x)：将列表 x 转换为堆。
4. heapq.heappushpop(heap, item)：向堆中插入一个元素 item，然后弹出堆中的最小元素。
5. heapq.heapreplace(heap, item)：将堆中的最小元素替换为新元素 item。
6. heapq.nlargest(n, iterable)：返回 iterable 中的前 n 个最大元素。
7. heapq.nsmallest(n, iterable)：返回 iterable 中的前 n 个最小元素。

import heapq

# 创建一个空的列表作为堆
heap = []

# 向堆中插入元素
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)

# 输出堆中的最小元素
print("堆中的最小元素:", heapq.heappop(heap))

# 在堆中插入一个新元素并弹出最小元素
print("插入新元素 4 并弹出最小元素:", heapq.heappushpop(heap, 4))

# 将列表转换为堆
data = [5, 1, 9, 3, 6]
heapq.heapify(data)
print("转换后的堆:", data)

# 查找列表中前 3 个最小元素
print("列表中前 3 个最小元素:", heapq.nsmallest(3, data))

# 查找列表中前 2 个最大元素
print("列表中前 2 个最大元素:", heapq.nlargest(2, data))

不使用模块

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def insert(self, key):
        self.heap.append(key)
        i = len(self.heap) - 1
        while i != 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[self.parent(i)], self.heap[i] = self.heap[i], self.heap[self.parent(i)]
            i = self.parent(i)

    def heapify(self, i):
        smallest = i
        l = self.left(i)
        r = self.right(i)

        if l < len(self.heap) and self.heap[l] < self.heap[smallest]:
            smallest = l

        if r < len(self.heap) and self.heap[r] < self.heap[smallest]:
            smallest = r

        if smallest != i:
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            self.heapify(smallest)

    def extract_min(self):
        if len(self.heap) == 0:
            return None

        root = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify(0)

        return root

# 示例用法
heap = MinHeap()
heap.insert(5)
heap.insert(2)
heap.insert(8)
heap.insert(3)

print("堆中的最小元素:", heap.extract_min())  # 输出：2
print("堆中的最小元素:", heap.extract_min())  # 输出：3

4. 应用：

堆在多种算法和数据结构中有广泛应用，如堆排序、优先级队列、带权图的最短路径算法（如Dijkstra算法）、和哈夫曼编码等。

5. 时间复杂度：

堆的操作通常具有高效的时间复杂度。例如，插入和删除操作通常具有对数时间复杂度（O(log n)），这使得它们在处理大量数据时仍然保持高效。