1. 二叉堆的概念
在计算机科学中，堆（heap）是一种特殊的数据结构。二叉堆（binary heap）是堆的一种，其中每个父节点都比其子节点小（最小堆）或者大（最大堆）。
通常二叉堆用树来表示，而由于二叉堆的性质，也可以用数组来表示。二叉堆有一个最重要的性质，即对于任意一节点 its 的位置 i，它的父节点位置 parent(i) 和它的子节点位置 left(i)、right(i) 可以通过下面公式得到：
parent(i) = floor((i-1)/2)
left(i) = 2*i+1
right(i) = 2*i+2
2. 数组表示的方法
2.1 最小堆的数组表示
在最小堆的数组表示中，堆中每个父节点的值都小于或等于其子节点的值。我们可以用一个数组来表示这个二叉堆，数组中的元素按照从上到下、从左到右的顺序，依次存储着二叉堆中的每一个节点。
对于任意一个节点其在数组中的下标为 i，则节点的父节点下标为 i/2（向下取整），左子节点下标为 2*i，右子节点下标为 2*i+1。这样我们就可以使用一个数组存储最小堆，下面是最小堆的数组表示方法的C++代码实现：
class MinHeap {
private:
vector heap;
void minHeapify(int i) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int smallest = i;
if (left < heap.size() && heap[left] < heap[smallest]) {
smallest = left;
}
if (right < heap.size() && heap[right] < heap[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(heap[i], heap[smallest]);
minHeapify(smallest);
}
}
public:
MinHeap() {}
MinHeap(vector& arr) {
heap = arr;
for (int i = arr.size() / 2 - 1; i >= 0; i--) {
minHeapify(i);
}
}
int getMin() {
return heap[0];
}
void insert(int x) {
heap.push_back(x);
int i = heap.size() - 1;
while (i > 0 && heap[i] < heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void deleteMin() {
heap[0] = heap.back();
heap.pop_back();
minHeapify(0);
}
};
2.2 最大堆的数组表示
最大堆的数组表示与最小堆类似，不同的是每个父节点的值都大于或等于其子节点的值。节点在数组中的下标的计算仍然使用与最小堆同样的方式，这里不再赘述，下面是最大堆的数组表示方法的C++代码实现：
class MaxHeap {
private:
vector heap;
void maxHeapify(int i) {
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = i;
if (left < heap.size() && heap[left] > heap[largest]) {
largest = left;
}
if (right < heap.size() && heap[right] > heap[largest]) {
largest = right;
}
if (largest != i) {
swap(heap[i], heap[largest]);
maxHeapify(largest);
}
}
public:
MaxHeap() {}
MaxHeap(vector& arr) {
heap = arr;
for (int i = arr.size() / 2 - 1; i >= 0; i--) {
maxHeapify(i);
}
}
int getMax() {
return heap[0];
}
void insert(int x) {
heap.push_back(x);
int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
swap(heap[i], heap[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
void deleteMax() {
heap[0] = heap.back();
heap.pop_back();
maxHeapify(0);
}
};
3. 二叉堆的应用
二叉堆是一种非常有用的数据结构，在很多算法和数据结构中都有广泛的应用，例如堆排序、优先队列、迪杰斯特拉算法、最小生成树算法等等，这里我们以堆排序为例来介绍一下二叉堆的应用。
3.1 堆排序的概念
堆排序是一种排序算法，它使用堆的数据结构来进行排序。堆排序的时间复杂度为 O(nlogn)，与快速排序等常用排序算法相当。但相比于快速排序，堆排序是一种不稳定的排序算法。
3.2 堆排序的实现
堆排序的核心就是建立和维护二叉堆，我们可以使用最小堆或最大堆来实现这个过程。不同于直接选择排序，堆排序可以通过不断交换堆的根节点和堆的最后一个叶子节点来进行排序，这样一来就把最小值（或最大值）“选出来”了，同时二叉堆是一种非常有效的优先队列，使得堆排序具有了快速选择的特性。
下面是堆排序的C++代码实现，通过 maxHeapify 或 minHeapify 函数进行堆的建立和维护，heapSort 函数则实现了堆排序：
void maxHeapify(vector& arr, int i, int n) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr[i], arr[largest]);
maxHeapify(arr, largest, n);
}
}
void minHeapify(vector& arr, int i, int n) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right < n && arr[right] < arr[smallest]) {
smallest = right;
}
if (smallest != i) {
swap(arr[i], arr[smallest]);
minHeapify(arr, smallest, n);
}
}
void heapSort(vector& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
maxHeapify(arr, i, n);
}
for (int i = n - 1; i >= 1; i--) {
swap(arr[0], arr[i]);
maxHeapify(arr, 0, i);
}
}
4. 总结
二叉堆是一种非常实用的数据结构，它可以用于堆排序、优先队列、各种数论问题等。通过数组来表示二叉堆，可以在一定程度上简化堆的操作和实现。最小堆和最大堆在实现方式上有一些差别，因此在使用时需要注意。