为什么heap Delete元素的复杂度等于O(logn)，Build的复杂度是O(n)？

为什么heap Delete元素的复杂度等于O(logn)，Build的复杂度是O(n)？

Heap（堆）是一种特殊的数据结构，常用于实现优先队列。它具有以下特点：

• 堆是一个完全二叉树，即除了最后一层外，其他层都是满的，最后一层从左到右填充。
• 堆中的每个节点的值都必须满足堆的性质，即父节点的值要么大于等于（最大堆）或小于等于（最小堆）其子节点的值。

在堆中，删除元素和构建堆的复杂度是不同的。

1. 删除元素的复杂度为O(logn)： 当我们删除堆中的一个元素时，通常是删除堆顶元素（根节点）。删除堆顶元素后，为了维持堆的性质，我们需要进行一系列的操作：
   • 将堆的最后一个元素移动到堆顶位置。
   • 与其子节点进行比较，将较大（或较小）的子节点与父节点交换位置，直到满足堆的性质。 这个过程称为堆的调整（Heapify）。由于堆是一个完全二叉树，堆的高度为logn，所以堆的调整的时间复杂度为O(logn)。

• 构建堆的复杂度为O(n)： 构建堆是将一个无序的数组转化为一个堆的过程。具体步骤如下：
  • 从最后一个非叶子节点开始，依次向上进行堆的调整。
  • 对于每个非叶子节点，与其子节点进行比较，将较大（或较小）的子节点与父节点交换位置，直到满足堆的性质。 这个过程称为堆的建立（Build Heap）。由于堆的高度为logn，而非叶子节点的数量为n/2，所以堆的建立的时间复杂度为O(n)。

综上所述，删除元素的复杂度为O(logn)，而构建堆的复杂度为O(n)。