目录
一、需要实现的功能
二、具体功能的实现
1.初始化堆
2.堆的销毁
3.交换函数
4.打印堆中的全部元素
5.向上调整我们的元素
6.堆元素的插入
7.向下调整
8.删除堆顶的元素
9.判断我们当前的堆是否为空
10.输出我们堆中的元素个数
11.查找我们当前堆顶的元素
12.合集
三、堆排序的实现
方法一：
方法二：
方法三：
一、需要实现的功能
#pragma once
// 小堆
#include
#include
#include
#include
//将我们的数据类型定义为int
typedef int HPDataType;
//这里定义我们堆的结构体
//其中a为我们的顺序表，用来实现我们堆的物理上的存储逻辑
//size为我们当前顺序表的最大的空间大小
//capacity为我们当前堆存储的元素个数。
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
//定义我们的交换函数，用来交换两个数据的具体值，将在下面的程序中调用
void Swap(HPDataType* pa, HPDataType* pb);
//实现堆数据结构的初始化 *** 作。
void HeapInit(HP* php);
//实现堆结构摧毁的 *** 作
void HeapDestroy(HP* php);
//将我们堆中数据打印出来的 *** 作
void HeapPrint(HP* php);
// 插入x以后，保持他依旧是(大/小)堆
void HeapPush(HP* php, HPDataType x);
// 删除堆顶的数据。(最小/最大)
void HeapPop(HP* php);
//判断我们的堆是否为空
bool HeapEmpty(HP* php);
//查看我们的堆的大小
size_t HeapSize(HP* php);
//返回我们堆定的元素
HPDataType HeapTop(HP* php);
将我们的顺序表置空，同时将我们的size和capacity置为0
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
分别将我们的堆中的顺序表的空间释放，同时将我们的size和capacity置为0
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}使用传址的方式来交换我们的数据，如果使用传值的方式，对于形参的拷贝是不会影响实参的。
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}从我们的堆的顺序表中顺序将我们全部的元素依次打印出来（注意，我们的size存储的我们当前顺序表中的最大元素，而我们的数组的下标是从0开始的，所以我们的i要小于size）
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}void AdjustUp(HPDataType* a, size_t child)
{
//完全二叉树中寻找我们的父节点
size_t parent = (child - 1) / 2;
//当我们的孩子结点存在的时候，一直迭代
while (child > 0)
{
//如果我们的孩子结点比我们的父节点更大，我们就交换我们的孩子结点和我们的父节点
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
//再将我们的孩子指针指向我们的父节点，也就是我们交换之前的孩子结点，然后再计算出我们当前的父节点，实现我们代码的迭代
child = parent;
parent = (child - 1) / 2;
}
//如果我们的孩子结点小于我们的父节点，就说明我们我们的向上调整已经完成了，现在我们的二叉树又是一棵大根堆的二叉树了。
else
{
break;
}
}
}void HeapPush(HP* php, HPDataType x)
{
assert(php);
//判断我们当前的存储空间已经满了的时候，我们开辟一块更大的空间来存储我们的数据
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
//如果我们的空间开辟失败，我们将返回如下的错误提示
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
//将我们堆的指针指向我们新开辟的空间，同时将我们的最大存储容量更新
php->a = tmp;
php->capacity = newCapacity;
}
//将我们的要插入的元素放到我们列表的最后的位置
php->a[php->size] = x;
++php->size;
// 向上调整，控制保持是一个大根堆
AdjustUp(php->a, php->size - 1);
}向下调整主要用于我们堆元素的删除
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
//向下调整就意味着我们之前插入元素之后，我们的新插入的元素可能随着向上调整会被调整到根节点，我们需要使用向下调整的办法来讲我们的元素插入到正确的位置
size_t parent = root;
//找到我们当前父节点的左孩子结点
size_t child = parent * 2 + 1;
//如果我们的左孩子结点存在的话，进入循环
while (child < size)
{
// 1、选出左右孩子中大的那个
if (child + 1 < size && a[child+1] > a[child])
{
++child;
}
// 2、如果孩子大于父亲，则交换，并继续往下调整
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}// 删除堆顶的数据。(最小/最大)
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
//将我们堆定的元素交换到我们的堆顺序表的末尾位置，然后将我们的当前容量--，来表示我们最大元素的删除。
//这样 *** 作不会更改我们堆中其他元素的关系，只需要将我们堆顶的元素重新向下调整到合适的位置就可以了
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
AdjustDown(php->a, php->size, 0);
}bool HeapEmpty(HP* php)
{
assert(php);
//如果我们当前的元素个数为0，也就是空就返回TRUE
return php->size == 0;
}size_t HeapSize(HP* php)
{
assert(php);
//直接返回我们的堆中当前元素大小的参数就可以了
return php->size;
}HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
//返回我们顺序表中的第0号元素，也就是我们的堆顶元素
return php->a[0];
}#include "Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
void AdjustUp(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
//if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
++php->size;
AdjustUp(php->a, php->size - 1);
}
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child+1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
--php->size;
AdjustDown(php->a, php->size, 0);
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}因为我们的堆顶元素一定为最大或最小，所以我们每次都将我们堆定的元素取出，然后把我们的剩下的元素重新调整为一个大根堆或一个小根堆，进行迭代，就可以实现我们的排序思想。
void HeapSort(int* a, int size)
{
//创建我们的队列
HP hp;
//初始化我们的队列
HeapInit(&hp);
//创建堆，将我们的要排序的数列中的元素一个个传入，搭建我们的堆
for (int i = 0; i < size; ++i)
{
HeapPush(&hp, a[i]);
}
//设置一个j来作为我们数组的伪指针
size_t j = 0;
//当我们的堆不为空的时候
while (!HeapEmpty(&hp))
{
//因为我们排序所生成的是一个大根堆，所以我们堆顶的元素就是我们最大的元素
//将我们最大的元素赋值给我们的数组的第一个元素
a[j] = HeapTop(&hp);
//将我们的伪指针后移
j++;
//将我们的堆顶元素弹出，调用我们之前写的堆的代码
//我们剩下的元素又会重新生成一个大根堆，第二大的元素会被调换到我们的根节点的位置，然后我们就通过迭代来实现我们的堆排序
HeapPop(&hp);
}
HeapDestroy(&hp);
}在上面的方法中，由于我们有对数组元素的拷贝，堆的生成需要开辟的空间比较大，所以我们不妨直接对我们需要排序的数组直接进行 *** 作。
//从前往后依，采用向上调节的方式调整我们的原数组，从而生成一个堆。
for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}但是，这种生成方法的时间复杂度为：O(N*logN)
就如我们下面这张图中所展示的，计算出我们最坏的情况一共需要调整的结点，再利用差比数列计算出我们的复杂度，为我们的 O(N*logN)
方法三：//在这种方法中，我们是找到我们所有叶子结点的父节点来进行向下调整，
//而在我们的堆为完全二叉树，我们只有n0与n2的结点，并且n0=n2+1
//在n-1找到的是我们数组的最后一个元素的位置（我们数组的下标是从0开始的），
//由于我们总的结点数为n0+n2，而n0=n2+1
//所以将我们的n-1再减去1除以2，就得到我们所有叶子结点的父节点。
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDown(a, n, i);
}这种方法的时间复杂度为O(N)
在这种建堆的方法中，我们第一层的2^0个元素最大需要调整h-1次
第二层2^1个元素最大需要调整h-2次
……
第h-1层有2^h-2个元素最大需要调整的次数为1次
T(N)=2^1(h-1)+2^2(h-2)+……2^(h-2)1
然后我们采用错位相减的方式可以算出我们的T(N)=2^h-1-h
h=log2(n+1)
带入T(N)就可以得到我们的T(N)为n-log2(n+1)，约为N
可以看出我们这种算法更优
以下是我们的堆排序的算法。
void HeapSort(int* a, int n)
{
//完成我们大根堆的搭建
for (int i = (n-2)/2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
//我们大根堆中的一个元素肯定是我们整个数组中最大的元素，我们将它与我们队尾的元素交换
//不再将它参与到我们的排序中
//然后将我们队首的元素进行向下调整
//依此迭代。
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 4, 2, 7, 8, 5, 1, 0, 6 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}注意：按照我们上面的算法，我们想要升序排序的话，我们需要创建大根堆，如果想要实现降序排序的话，我们需要创建小根堆。
注：为什么我们不采用小根堆的方式来实现升序序列？
因为我们如果采用小根堆的方式搭建完小根堆，我们的第一个元素确实是我们最小的元素，但是我们剩余的元素需要全部重新排序成一个新的小根堆，时间复杂度太大。不像我们之前的大根堆排序一样，只需要进行向下调整 *** 作就可以重新将我们剩下的元素排列成一个大根堆。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）