b2b2c商城服务好的商家_久久网招聘信息_宁德市蕉城区疫情_怎么在百度上投放广告

【本节目标】

1. 堆的概念及结构
2. 堆的实现

1.堆的概念及结构

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

2.堆的实现

2.1堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

🧐🧐注意：

小堆向下调整算法要求：调整的树的左右子树都是小堆
大堆向下调整算法要求：调整的树的左右子树都是大堆

//小堆
//要让小的孩子往上挪//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
//前提：左右子树都是小堆
void AdjustDown(HPDataType* a, int n, int root)
{//找出左右孩子中小的那一个int parent = root;int child = parent * 2 + 1;//默认是左孩子小while (child < n)//n是这个结点范围{//如果右孩子小于左孩子if (child+1<n && a[child + 1] < a[child])//child+1>n说明只有左孩子没有右孩子{child++;//那就选出这个更小的孩子}if (a[child] < a[parent]){//找出的这个小的孩子小于父亲就交换Swap(&a[child], &a[parent]);parent = child;//parent走到child这个位置child = parent * 2 + 1;//重新算这个child}else{break;//如果是孩子大于等于父亲就不需要交换，跳出循环}}}//初始化
void HeapInit(Heap* php, HPDataType* a, int n)
{php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);memcpy(php->_a, a, sizeof(HPDataType) * n);php->_size = n;php->_capacity = n;//构建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//i是倒数第一个父亲结点//因为n为结点数，最后一个节点（也就是最后一个孩子）下标为n-1//然后-1/2找到其父亲，也就是倒数第一个父亲结点{AdjustDown(php->_a, php->_size, i);}}int main()
{int a[] = { 27,15,19,18,28,34,65,49,25,37 };Heap hp;HeapInit(&hp, a, sizeof(a) / sizeof(HPDataType));//a数组大小除以每个数据大小等于个数return 0;
}

AdjustDown向下调整算法：

功能：该函数用于将以root为根的子树调整为小堆。前提是root的左右子树已经是小堆。
参数：

• a：指向存储堆元素的数组的指针。
• n：数组中元素的个数，即堆的大小。
• root：要调整的子树的根节点的下标。

堆的初始化函数 HeapInit

功能：该函数用于初始化一个堆，将数组a中的元素构建成一个小堆。
参数：

• php：指向Heap结构体的指针，用于存储堆的信息。
• a：指向存储初始元素的数组的指针。
• n：数组中元素的个数。

实现步骤：

• 为php->_a分配内存，大小为n个HPDataType类型元素的大小。
• 使用memcpy函数将数组a中的元素复制到php->_a中。
• 初始化php->_size和php->_capacity为 n。
• 从倒数第一个非叶子节点开始，依次调用AdjustDown函数，将以每个非叶子节点为根的子树调整为小堆，最终将整个数组构建成一个小堆。

HeapInit(&hp, a, sizeof(a) / sizeof(HPDataType));

这行代码调用了HeapInit函数，其目的是对堆hp进行初始化。
参数解释如下：

• &hp：传递hp的地址，如此一来HeapInit函数就能够修改hp的内容。
• a：传递数组a的首地址，也就是将数组a里的元素作为堆的初始元素。
• sizeof(a) / sizeof(HPDataType)：用来计算数组a中元素的个数。sizeof(a) 算出的是整个数组的字节大小，sizeof(HPDataType) 算出的是每个元素的字节大小，二者相除就得到了元素的个数。

2.2用堆来排序

这里我们补充一个知识：
排降序：建小堆
排升序：建大堆

1. 排降序：

Heap.c函数：

test.c函数

最后实现结果：

2. 排升序

排升序就是在降序的基础上，把小堆改为大堆（修改两个地方，如下图：）

最后实现结果：

2.3堆的初始化

//初始化
void HeapInit(Heap* php, HPDataType* a, int n)
{php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);//malloc 函数用于为堆的数组分配足够的内存，大小为 sizeof(HPDataType) * nmemcpy(php->_a, a, sizeof(HPDataType) * n);//memcpy 函数将数组 a 中的元素复制到新分配的内存中，这样堆就拥有了与数组 a 相同的元素php->_size = n;//设置堆的大小和容量php->_capacity = n;//构建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--)//i是倒数第一个父亲结点//因为n为结点数，最后一个节点（也就是最后一个孩子）下标为n-1//然后-1/2找到其父亲，也就是倒数第一个父亲结点{AdjustDown(php->_a, php->_size, i);}}

代码分析：

• Heap* php：指向堆结构体的指针，用于存储堆的相关信息，如堆数组、堆大小和容量等。
• HPDataType* a：指向一个数组的指针，该数组包含了要初始化堆的元素。
• int n：表示数组a中的元素个数。

重点代码：构建堆

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(php->_a, php->_size, i);
}

这是一个for循环，用于从最后一个非叶子节点（也就是最后一个父节点）开始，自下而上地对堆进行调整，以满足堆的性质。

• i = (n - 1 - 1) / 2：计算最后一个非叶子节点的下标。在完全二叉树中，最后一个节点的下标为 n - 1，其父亲节点的下标可以通过(n - 1 - 1) / 2计算得到。
• i >= 0：循环条件，确保从最后一个非叶子节点一直处理到根节点。
• AdjustDown 函数：每次循环调用AdjustDown函数，对当前节点进行向下调整，以维护堆的性质。
• AdjustDown 函数接受三个参数：堆数组 php->_a、堆的大小php->_size和当前节点的下标 i。

2.4堆的销毁

// 堆的销毁
void HeapDestory(Heap* php)
{assert(php);free(php->_a);php->_a = NULL;php->_capacity = php->_size = 0;
}

🤔🤔🤔思考一个问题： 为什么调用 AdjustDown 函数进行向下调整？为什么不用向上调整呢？

由于叶子节点没有子节点，不需要和子节点进行值的比较，所以无论对于大顶堆还是小顶堆，叶子节点本身就天然满足堆的性质。这也是在堆初始化过程中，我们从最后一个非叶子节点开始进行调整的原因，因为叶子节点不需要调整，只需要调整非叶子节点及其子树，就能把整个完全二叉树转换为满足堆性质的结构

向下调整

堆初始化时，我们有一个无序数组，要把它转换为堆结构。从最后一个非叶子节点开始进行向下调整是合理的。因为叶子节点本身就满足堆的性质（没有子节点，无需比较调整），所以只需调整非叶子节点。从最后一个非叶子节点开始，逐步向上调整每个非叶子节点及其子树，能保证在调整上层节点时，其下层子树已经是满足堆性质的结构，最终能将整个数组转换为堆。

向上调整

向上调整更适合在已有堆结构的基础上，插入新元素的场景。当插入一个新元素时，将其放在堆的末尾，然后通过向上调整，将该元素移动到合适的位置，以维护堆的性质。但在堆初始化时，若使用向上调整，就相当于把无序数组中的元素一个一个插入到一个初始为空的堆中，这样的操作过程会比直接从非叶子节点开始向下调整更复杂，效率更低。

2.5堆的向上调整算法

//堆的向上调整算法
void AdjustUp(HPDataType* a, int n, int child)
{int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//比较当前节点 child 的值和其父节点 parent 的值。如果当前节点的值小于父节点的值，说明不满足最小堆的性质，需要进行交换{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{//孩子大于等于父亲break;}}
}

代码分析：

• HPDataType* a：这是一个指向堆数据类型的指针，用于指向堆数组的首地址。
• int n：表示堆数组a的元素个数，这个参数在当前代码中没有被使用到，可能在更完整的堆操作代码中有其他用途。
• int child：表示需要进行向上调整的孩子节点的下标。

2.6堆的插入

// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_size == php->_capacity)//当堆的当前元素数量 _size 等于堆的容量 _capacity 时，说明堆已经满了，需要进行扩容操作{php->_capacity *= 2;//将堆的容量 _capacity 扩大为原来的 2 倍HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(php->_capacity));php->_a = tmp;//a变为新开的空间//将扩容后的新内存地址赋值给 php->_a，确保堆数组指向新的内存空间}php->_a[php->_size++] = x;//将新元素 x 插入到堆数组的末尾，即 php->_a[php->_size] 位置，然后将堆的大小 _size 加 1AdjustUp(php->_a, php->_size, php->_size - 1);//调用 AdjustUp 函数对新插入的元素进行向上调整，以维护堆的性质
}

2.7堆的删除

// 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);Swap(&php->_a[0], &php->_a[php->_size - 1]);//交换第一个数据和最后一个数据php->_size--;//表示删掉了//再进行向下调整AdjustDown(php->_a, php->_size, 0);
}

2.8取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(php->_size > 0);return php->_a[0];
}

🎉🎉🎉
在这里本章就结束了~
友友们：
我们下期见~