堆排序与数据结构中的堆

堆（heap）是一种特殊的数据结构，其特点是可以通过数组来表示一棵完全二叉树。堆的主要性质包括：

1. **父子节点关系**：对于最大堆，每个节点的值都不小于其子节点的值；对于最小堆，每个节点的值都不大于其子节点的值。
2. **完全二叉树**：堆总是一棵完全二叉树，这意味着除了最后一层外，所有层都是满的，且最后一层的节点尽可能靠左排列。

### 堆的分类

根据根节点的值，堆可以分为两种类型：
- **最大堆（大顶堆）**：根节点是堆中最大的元素。
- **最小堆（小顶堆）**：根节点是堆中最小的元素。

常见的堆实现包括二叉堆、斐波那契堆等。二叉堆是最常用的堆实现方式之一，它通过数组存储，并且满足以下条件：

设一个包含n个元素的序列{k1, k2, ..., kn}，当且仅当满足以下关系时，该序列为堆：

- 对于最大堆：ki >= k2i 和 ki >= k2i+1 (i = 1, 2, ..., n/2)
- 对于最小堆：ki <= k2i 和 ki <= k2i+1 (i = 1, 2, ..., n/2)

### 堆的操作

堆支持多种操作，包括但不限于：

- **build**：创建一个空堆。
- **insert**：向堆中插入新元素。
- **update**：调整新元素的位置以保持堆的性质。
- **get**：获取当前堆顶元素的值。
- **delete**：删除堆顶元素。
- **heapify**：在删除堆顶元素后重新调整堆以保持其性质。

某些堆实现还支持其他操作，如检查堆中是否存在某个元素。

### 建堆效率

对于包含n个节点的堆，高度d = log₂n。建堆的时间复杂度为O(n)，因为大部分节点位于树的底部，而这些节点不需要移动。插入、删除普通元素和删除最小元素的平均时间复杂度为O(log n)。

### 堆的应用

堆广泛用于动态内存分配和释放，特别是在程序需要动态分配对象时。例如，当程序所需对象的数量和大小事先未知，或对象太大不适合使用栈分配器时，堆是一个很好的选择。

在操作系统和运行时库中，堆用于管理进程内的内存分配。默认情况下，操作系统会为每个进程创建一个称为进程堆的默认堆。此外，应用程序或加载的动态链接库（DLL）也可以创建并使用单独的堆。

### 代码实现示例

以下是一个最小堆的C++实现：

```cpp
#pragma once
template
class MinHeap {
private:
T* _heap;
int _size;
int _capacity;

public:
MinHeap(int capacity) : _capacity(capacity), _size(0) {
_heap = new T[_capacity];
}

~MinHeap() {
delete[] _heap;
}

bool isEmpty() const {
return _size == 0;
}

bool isFull() const {
return _size == _capacity;
}

bool add(const T& value) {
if (isFull()) {
return false;
}
_heap[_size++] = value;
adjustUp(_size - 1);
return true;
}

void adjustDown(int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;

if (left <_size && _heap[left] <_heap[smallest]) {
smallest = left;
}
if (right <_size && _heap[right] <_heap[smallest]) {
smallest = right;
}

if (smallest != index) {
std::swap(_heap[index], _heap[smallest]);
adjustDown(smallest);
}
}

void adjustUp(int index) {
while (index > 0 && _heap[(index - 1) / 2] > _heap[index]) {
std::swap(_heap[(index - 1) / 2], _heap[index]);
index = (index - 1) / 2;
}
}
};
```

此代码实现了最小堆的基本功能，包括插入和调整操作。