数据结构——堆

堆的基本知识

堆的实现

堆的定义

堆的初始化

堆的销毁

堆的调整

向上调整

向下调整

堆的插入

堆的删除

取堆顶的数据

堆的判空

堆的应用

堆排序

向下调整建堆

向上调整建堆

利用堆删除来排序

堆的基本知识

堆（Heap）是一种特殊的树状数据结构。

主要特性

堆通常是一棵完全二叉树。
堆中的每一个节点必须满足特定顺序要求，以这个要求分出大根堆和小根堆。

大根堆：任何一个父节点的值都大于或等于它的子节点的值。

小根堆：任何一个父节点的值都小于或等于它的子节点的值。

基本操作

插入（Insertion）：在堆中添加新元素，同时保持堆的属性。
删除（Deletion）：通常指的是删除堆顶元素，然后重新调整堆以保持其属性。
查找堆顶元素（Find Top）：在最大堆中找到最大元素，在最小堆中找到最小元素。
堆调整（Heapify）：将堆的某一部分重新调整，以恢复堆属性。

应用场景

优先级队列
堆排序
内存管理

实现方式

一般用数组实现

父子节点之间的索引：

1.父节点：i

2.左节点：2 * i + 1

3.右节点 2 * i + 2

4通过子节点i 找父节点（i - 1）/ 2

堆的实现

堆的定义

typedef int HPDataType;typedef struct Heap
{HPDataType* arr;int size;int capacity;
}HP;

跟我们定义顺序表类似，一个动态申请的数组、有效数据个数、最大可容纳数据个数。

堆的初始化

将arr置空，将capacity和size置0。

//堆的初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 0;
}

堆的销毁

将动态申请的数组free掉，把capacity和size置0。

// 堆的销毁
void HPDestroy(HP* php)
{assert(php);free(php->arr);php->capacity = php->size = 0;
}

堆的调整

调整算法用于堆的插入和删除后恢复堆的属性，但是用调整算法的前提是堆原本是有序的（大根堆或者小根堆）

向上调整

首先算出parent的索引，parent跟child比较，若child大于parent，则交换，然后更新parent、child，直到child小于等于0或者child小于parent了。


void AdjustUp(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0{if (arr[child] > arr[parent]){//交换Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;;}}
}

注意，循环条件不能用parent >= 0来判断，因为当child = 1，parent = 0时，child = parent后，child = 0，然后parent = (0 - 1) / 2 == 0,达不到理想终止的效果。（虽然最后循环也能停止，因为循环里arr[child] > arr[parent]不成立，break掉了，但是代码还是有问题的，要改正）

向下调整

向下调整与向上调整是类似的，但也有区别。

以大根堆为例，需要先找到左右孩子中较大的一个，再跟父亲比较。

//向下调整
void AdjustDown(HPDataType* arr, int size, int parent)
{assert(arr);int child = 2 * parent + 1;while (child < size){//找两个孩子中较大的孩子 假设法 大的那个是左孩子if (child + 1 < size && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

堆的插入

堆的插入只能尾插，不能随便插入到其他位置。

插入数据后使用向上调整恢复堆的属性。

//检查空间是否足够
void CheckCapacity(HP* php)
{assert(php);if (php->capacity == php->size){int NewCapacity = (php->capacity == 0 ? 4 : 2 * php->capacity);HPDataType* tep = (HPDataType*)realloc(php->arr, NewCapacity * sizeof(HPDataType));if (tep == NULL){perror("realloc fail!");return;}php->arr = tep;php->capacity = NewCapacity;}
}// 堆的插入
void HPPush(HP* php, HPDataType x)
{assert(php);//插入之前检查空间是否足够CheckCapacity(php);php->arr[php->size++] = x;AdjustUp(php->arr, php->size-1);
}

堆的删除

堆的删除是删除堆顶的数据，首先将堆顶数据和最后一个数据交换，让size--，然后使用向下调整算法恢复堆的属性。

// 堆的删除 删除堆顶数据
//堆顶与尾交换 size-- 然后向下调整
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->arr[0], &php->arr[--php->size]);AdjustDown(php->arr, php->size, 0);
}

取堆顶的数据

注意判断堆不为空就行了。

//取堆顶的数据
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->arr[0];
}

堆的判空

判断size == 0就行。

//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

堆的应用

堆排序

堆排序主要利用堆的思想进行排序。

步骤：

1.建堆（升序建大堆；降序建小堆）

2.利用堆删除的思想来排序。（这也解释了为什么升序要建大堆，因为大堆确定了最大元素在堆顶）

向下调整建堆

从最后一个非叶子节点开始，向上遍历直到根节点，对每个节点进行调整，以确保其满足堆的性质。

步骤：

从最后一个非叶子节点开始，该节点的索引为 n/2 - 1，其中 n 是数组的长度。
对每个节点，检查其子节点，如果存在违反堆性质的情况（在最大堆中，子节点大于父节点；在最小堆中，子节点小于父节点），则交换父节点和较大的子节点。
继续这个过程，直到节点满足堆性质或到达根节点。

void AdjustDown(int* arr, int size, int parent)
{int child = 2 * parent + 1;while (child < size){//假设法找出左右孩子中大的那个节点if (child + 1 < size && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}

时间复杂度O(n)

向上调整建堆

从第一个内部节点开始，向下遍历直到根节点，对每个节点进行调整。这种方法从底部开始，逐步向上调整节点。

步骤：

从第一个内部节点开始，该节点的索引为 n/2，其中 n 是数组的长度。
对每个节点，检查其父节点，如果当前节点违反了堆性质（在最大堆中，当前节点大于父节点；在最小堆中，当前节点小于父节点），则交换它们。
将交换后的节点视为新的当前节点，重复上述过程，直到当前节点满足堆性质或到达根节点。

void AdjustUp(HPDataType* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while(child > 0)// parent >= 0 是错的 parent = (0 - 1) / 2 == 0{if (arr[child] > arr[parent]){//交换Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;;}}
}

时间复杂度O(nlogn)

对比两种建堆方式，我们应当使用向下调整建堆。

利用堆删除来排序

当数组建堆建好后，交换堆顶元素和最后一个元素，缩小堆的范围，向下重新调整堆，重复此过程，直到堆的大小为1，说明数组已经排序好了。

void Swap(int* p1, int* p2)
{int tep = *p1;*p1 = *p2;*p2 = tep;
}void AdjustDown(int* arr, int size, int parent)
{int child = 2 * parent + 1;while (child < size){//假设法找出左右孩子中大的那个节点if (child + 1 < size && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int* arr, int size)
{//向下建堆 //升序 建大堆//降序 建小堆for (int i = (size - 2) / 2; i >= 0; i--){AdjustDown(arr, size, i);//大堆}int end = size - 1;while (end >= 0){Swap(&arr[end], &arr[0]);AdjustDown(arr, end, 0);end--;}
}

堆排序的总时间复杂度是 O(n)（构建堆）+ O(nlogn)（堆排序过程），结果是 O(nlogn)。