堆

堆（Heap）是一种基于树的数据结构，常用于实现优先队列和排序算法。堆分为最大堆和最小堆两种类型，它们的主要区别在于根节点的值。

最大堆（Max Heap）是一种堆，其中每个节点的值都大于或等于其子节点的值。根节点的值是堆中的最大值。

最小堆（Min Heap）是一种堆，其中每个节点的值都小于或等于其子节点的值。根节点的值是堆中的最小值。

堆通常使用数组来实现，其中每个元素对应堆中的一个节点。堆的根节点存储在数组的第一个元素中，其余节点按照从上到下、从左到右的顺序存储。

堆的基本操作包括插入、删除和查找。插入操作将一个新元素插入到堆中，删除操作将堆中的最大或最小元素删除，查找操作用于查找堆中的最大或最小元素。

堆的插入操作通常是将新元素添加到堆的末尾，然后通过上滤操作将其移动到正确的位置。上滤操作将新元素与其父节点比较，如果新元素比父节点大（或小），则交换它们的位置，直到新元素到达正确的位置为止。

堆的删除操作通常是将堆的根节点删除，然后通过下滤操作将堆的最后一个元素移动到根节点的位置。下滤操作将根节点与其子节点比较，如果根节点比子节点小（或大），则交换它们的位置，直到根节点到达正确的位置为止。

堆的查找操作通常是返回堆的根节点的值，即最大或最小元素的值。

堆的时间复杂度为 O(log n)，其中 n 是堆中元素的数量。堆的空间复杂度为 O(n)。