数据结构与算法-堆（数据结构与算法 堆）

堆（Heap）是一种特殊的数据结构，它是一棵完全二叉树，并且满足堆的性质：对于任意节点i，其父节点的值小于等于（或大于等于）其子节点的值。

堆通常用数组来实现，数组中的元素按照完全二叉树的顺序存储。对于任意节点i，其左子节点的索引为2i+1，右子节点的索引为2i+2，父节点的索引为(i-1)/2。

堆分为最小堆和最大堆两种类型。在最小堆中，父节点的值小于等于其子节点的值；在最大堆中，父节点的值大于等于其子节点的值。

堆的主要操作包括插入和删除。插入操作将新元素添加到堆的末尾，然后通过上浮操作将其调整到合适的位置。删除操作通常删除堆顶元素，然后将堆的最后一个元素放到堆顶，并通过下沉操作将其调整到合适的位置。

堆的时间复杂度如下：

- 插入操作的时间复杂度为O(log n)，其中n是堆中元素的数量。

- 删除操作的时间复杂度为O(log n)。

- 查找堆顶元素的时间复杂度为O(1)。

堆的应用非常广泛，特别适用于需要快速查找最大/最小元素的场景，如优先队列、堆排序等。它的实现相对简单，且具有较高的效率。