堆与二叉搜索树的比较

# 2.1 堆的基本概念和性质

### 2.1.1 堆的定义和分类

堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。堆可以分为两种类型：

- **小顶堆：**根节点的值是最小的，并且每个节点的值都大于或等于其子节点的值。
- **大顶堆：**根节点的值是最大的，并且每个节点的值都小于或等于其子节点的值。

### 2.1.2 堆的性质和特点

堆具有以下性质和特点：

- **完全二叉树：**堆是一棵完全二叉树，即除了最后一层之外，每一层都填满了节点。
- **堆序性：**堆中每个节点的值都大于或等于（小顶堆）或小于或等于（大顶堆）其子节点的值。
- **高度平衡：**堆的高度总是尽可能小，即对于一个有 n 个节点的堆，其高度为 log₂n。
- **高效插入和删除：**在堆中插入或删除元素的时间复杂度为 O(log₂n)。

# 2. 堆的理论与实践

### 2.1 堆的基本概念和性质

#### 2.1.1 堆的定义和分类

堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。它可以分为两种类型：

* **最大堆：**每个节点的值都大于或等于其子节点的值。
* **最小堆：**每个节点的值都小于或等于其子节点的值。

#### 2.1.2 堆的性质和特点

堆具有以下性质和特点：

* **完全二叉树：**堆是一棵完全二叉树，即除了最后一层外，每一层都完全填满。
* **最大/最小值：**最大堆的根节点包含最大值，而最小堆的根节点包含最小值。
* **层次性：**堆中每个节点的值都大于或等于其子节点的值，形成一种层次结构。
* **平衡性：**堆通常是平衡的，即左右子树的高度差不大于 1。

### 2.2 堆的构建与操作

#### 2.2.1 堆的构建算法

构建堆可以使用两种算法：

* **自上而下构建：**从根节点开始，将每个节点与其子节点进行比较，并交换不满足堆性质的节点。
* **自下而上构建：**从叶子节点开始，将每个节点与其父节点进行比较，并交换不满足堆性质的节点。

#### 2.2.2 堆的插入和删除操作

堆的插入和删除操作需要保持堆的性质：

**插入操作：**

1. 将新元素插入到树的末尾。
2. 将新元素与其父节点进行比较，如果违反堆性质，则交换两者。
3. 重复步骤 2，直到达到根节点或满足堆性质。

**删除操作：**

1. 将根节点的值替换为树的最后一个元素。
2. 删除树的最后一个元素。
3. 将根节点与其子节点进行比较，如果违反堆性质，则交换两者。
4. 重复步骤 3，直到达到叶子节点或满足堆性质。

# Python 代码示例：

class Heap:
    def __init__(self, arr):
        self.heap = arr
        self.build_heap()

    def build_heap(self):
        # 自上而下构建堆
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self.heapify(i)

    def heapify(self, i):
        # 维护堆性质
        left = 2 * i + 1
        right = 2 * i + 2
        largest = i
        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right
        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self.heapify(largest)

    def insert(self, value):
        # 插入操作
        self.heap.append(value)
        self.build_heap()

    def delete(self):
        # 删除操作
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.heapify(0)

**代码逻辑解读：**

* `Heap` 类初始化时，调用 `build_heap()` 方法构建堆。
* `build_heap()` 方法采用自上而下构建算法，从根节点开始，维护堆性质。
* `heapify()` 方法递归地维护堆性质，将违反堆性质的节点与子节点交换。
* `insert()` 方法将新元素插入堆中，并调用 `build_heap()` 方法重新构建堆。
* `delete()` 方法删除堆顶元素，并调用 `heapify()` 方法维护堆性质。

# 3. 二叉搜索树的理论与实践

### 3.1 二叉搜索树的