堆学习笔记

什么是堆

堆（Heap）是一种经过排序的完全二叉树，其中每个节点都比它的子节点大（或小），被称为最大堆（Max Heap）或最小堆（Min Heap）。在计算机科学中，堆经常被用作一种数据结构来实现优先队列，堆排序等算法。

最大堆

最大堆的每个节点都比它的子节点大，堆顶元素是整个堆中的最大值。例如，下面是一个6个节点的最大堆：

Copy Code
            10
          /    \
        8       7
      /   \    /
     6    5   3

最小堆

最小堆的每个节点都比它的子节点小，堆顶元素是整个堆中的最小值。例如，下面是一个6个节点的最小堆：

Copy Code
            1
          /    \
        2       3
      /   \    /
     4    5   6

堆的基本操作

堆作为一种数据结构，有以下基本操作：

插入元素

向堆中插入元素是在堆的末尾添加元素，然后通过“上滤”操作使其满足堆的性质。具体实现步骤如下：

1. 将新元素插入堆的末尾。
2. 将新元素与其父节点比较，若大于父节点则交换，重复此过程直到不再大于父节点或到达根节点。

删除元素

从堆中删除元素通常是删除堆顶元素，并把最后一个元素移动到堆顶，然后通过“下滤”操作使其满足堆的性质。具体实现步骤如下：

1. 用堆末尾元素替换堆顶元素。
2. 将新堆顶元素与其两个子节点比较，若小于其中任一子节点则与子节点交换，重复此过程直到不再小于子节点或没有子节点为止。

堆排序

堆排序利用堆的性质进行排序，首先建立一个最大堆，然后每次取出堆顶元素放到数组末尾，再对剩余元素调整成最大堆，重复此过程直到所有元素都有序。堆排序的时间复杂度为O(nlogn)。

堆的应用

优先队列

堆可以作为一种数据结构实现优先队列，即每次取出队列中最优先的元素。在堆中，堆顶元素就是最优先的元素，删除堆顶元素后，新的堆顶元素仍然是最优先的元素，因此堆可以实现高效的优先队列。

堆排序

堆排序利用堆的性质进行排序，具有以下特点：

1. 时间复杂度为O(nlogn)，与归并排序等其他时间复杂度为O(nlogn)的排序算法一样。
2. 堆排序不需要额外的空间存储数据，空间复杂度为O(1)。
3. 堆排序可以通过调整堆的结构来实现原地排序（In-place sorting），即不需要像归并排序那样需要额外的存储空间。

实例

下面是一个使用Python语言实现的最小堆：

pythonCopy Code
import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 4)

print(heapq.heappop(heap)) # output: 3
print(heapq.heappop(heap)) # output: 4
print(heapq.heappop(heap)) # output: 5
print(heapq.heappop(heap)) # output: 7

该程序使用Python标准库中的heapq模块实现了最小堆，向堆中插入元素使用heappush函数，删除堆顶元素使用heappop函数。通过以上程序可以看出，输出结果为3、4、5、7，证明该程序实现的是最小堆。