C++堆与优先队列：算法实现与应用场景，资源高效管理

# 1. C++堆与优先队列的基础理论

C++堆与优先队列是数据结构与算法领域中极为重要的概念，它们在高效处理大量数据的场景中扮演着关键角色。堆是一种特殊的完全二叉树，满足堆性质，通常用数组实现，并支持高效的插入和删除操作。优先队列则是一种抽象数据类型，允许插入元素，并能高效地取出当前优先级最高的元素。

堆结构为我们提供了一个方便的方法来快速访问集合中的最大或最小元素，而无需遍历整个集合。这种特性使得堆在很多算法中都得到了广泛的应用，包括但不限于排序、选择和图算法。C++标准模板库(STL)中的priority_queue是一个优先队列的实现，它使用堆结构来管理元素。通过本章的学习，你将获得对堆与优先队列理论和实际应用的深入理解。让我们开始吧。

# 2. 堆数据结构的算法实现

堆是一种特殊的完全二叉树，它满足任何一个父节点的值都大于或等于（在最小堆中）或小于或等于（在最大堆中）其子节点的值。堆通常使用数组来实现，因为数组可以非常高效地表示完全二叉树的结构。堆的性质使得它在优先队列、堆排序和其他需要高效检索最大或最小元素的场景中非常有用。

## 2.1 堆的概念及其性质

### 2.1.1 完全二叉树与堆的关系

完全二叉树是一种特殊的二叉树，它的每一层都是满的，除了最后一层可能不满，但是最后一层的节点都集中在左侧。在完全二叉树中，如果我们从最后一个非叶子节点开始，可以确保所有叶子节点都处于数组的最后两个位置上。堆作为完全二叉树的一种特例，每个父节点都大于（或小于）其子节点的值，保证了堆的有序性。

堆的性质保证了其可以通过数组索引高效地表示和操作。对于数组中的任意元素，我们可以通过简单的计算来找到它的父节点或子节点：

- 父节点索引：`(index - 1) / 2`
- 左子节点索引：`2 * index + 1`
- 右子节点索引：`2 * index + 2`

### 2.1.2 堆的操作定义与重要性

堆的主要操作包括插入（或称为推入）、删除（或称为弹出）、构建堆和堆排序。这些操作都以保持堆的性质为前提，而这些操作的时间复杂度直接关联到堆的性能表现。

- 插入操作：当一个新的元素添加到堆中时，我们需要通过上浮（或称为上滤）操作将它移动到合适的位置，以保持堆的性质。上浮操作的时间复杂度为O(log n)。
- 删除操作：从堆中删除元素通常指的是删除并返回堆顶元素，即最大或最小元素。删除操作通过下沉（或称为下滤）操作来实现，将堆顶元素与堆中最后一个元素交换，然后移除最后一个元素。接着，通过下沉操作调整新的堆顶元素，恢复堆的性质。下沉操作的时间复杂度也是O(log n)。
- 构建堆：给定一组元素，将它们构建成一个堆的过程称为堆化。这是一个O(n)的操作，它使用下沉操作从最后一个非叶子节点开始调整整个树。
- 堆排序：堆排序利用了堆的性质来实现高效的排序算法。它首先构建一个最大堆，然后逐个移除堆顶元素并将其放到数组的末尾，每移除一个元素就对剩余的堆进行下沉操作来维护最大堆的性质。

## 2.2 堆的插入与删除算法

### 2.2.1 插入操作的步骤与时间复杂度

当一个新的值需要添加到堆中时，我们首先将它放置在数组的最后一个位置，然后执行上浮操作，这个操作不断地比较当前节点与其父节点的值，如果当前节点的值更大（在最大堆中），则与父节点交换位置。这个过程一直持续到当前节点的值小于或等于其父节点的值，或者当前节点已经到达了堆顶。

void insert(int value) {
    heap.push_back(value);
    int index = heap.size() - 1;
    int parent = (index - 1) / 2;

    while (index > 0 && heap[index] > heap[parent]) {
        swap(heap[index], heap[parent]);
        index = parent;
        parent = (index - 1) / 2;
    }
}

插入操作的时间复杂度为O(log n)，因为最坏的情况下我们需要一直上浮到堆的顶部，而树的高度为log n。

### 2.2.2 删除操作的步骤与时间复杂度

删除操作首先要处理的是堆顶元素，也就是最大值（在最大堆中）。我们先将堆顶元素保存下来，然后用数组的最后一个元素替换堆顶元素的位置，接着执行下沉操作。这个过程不断地比较当前节点与其子节点的值，并与值较大的子节点交换位置。下沉操作持续进行，直到当前节点的值大于或等于其子节点的值，或者没有子节点。

int deleteMax() {
    if (heap.empty()) {
        throw std::runtime_error("Heap is empty!");
    }
    int max_value = heap[0];
    heap[0] = heap.back();
    heap.pop_back();
    int index = 0;
    int child;

    while ((child = 2 * index + 1) < heap.size()) {
        if (child + 1 < heap.size() && heap[child + 1] > heap[child]) {
            child++;
        }

        if (heap[index] < heap[child]) {
            swap(heap[index], heap[child]);
            index = child;
        } else {
            break;
        }
    }
    return max_value;
}

删除操作的时间复杂度同样是O(log n)，在最坏的情况下，我们可能需要下沉到叶子节点。

## 2.3 堆的排序算法

### 2.3.1 堆排序的基本原理

堆排序是基于比较的排序算法之一，它利用堆的性质来实现高效的排序。堆排序的基本思想是：

1. 将待排序的数组构建成一个最大堆。
2. 将堆顶元素（当前最大值）与堆的最后一个元素交换，然后缩小堆的范围，同时进行下沉操作，调整新的堆顶元素，以保持最大堆的性质。
3. 重复步骤2，直到堆的范围缩小到只剩下一个元素，排序完成。

### 2.3.2 堆排序的实现过程

void heapSort() {
    buildMaxHeap();
    for (int i = heap.size() - 1; i > 0; i--) {
        swap(heap[0], heap[i]);
        heap.resize(i);
        maxHeapify(0);
    }
}

void buildMaxHeap() {
    for (int i = heap.size() / 2 - 1; i >= 0; i--) {
        maxHeapify(i);
    }
}

void maxHeapify(int index) {
    int largest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap.size() && heap[left] > heap[largest]) {
        largest = left;
    }

    if (right < heap.size() && heap[right] > heap[largest]) {
        largest = right;
    }

    if (largest != index) {
        swap(heap[index], heap[largest]);
        maxHeapify(largest);
    }
}

堆排序的时间