当前位置：首页 > news >正文

堆的实现（偷懒版）

news 来源：原创 2024/9/19 13:48:19

🌹个人主页🌹：喜欢草莓熊的bear

🌹专栏🌹：数据结构

前言

一、堆的实现

1.1 堆的向下调整算法

思路：

1.2 堆的向上调整算法

1.3 堆的创建

1.4 堆的复杂度计算

向下调整建堆的复杂度：

向上调整建堆的复杂度：

1.5 堆的插入

1.6 堆的删除

1.7 堆的代码实现

总结

前言

在上期内容介绍了二叉树、还简单提了一下堆的概念和大堆、小堆。回顾一下堆是首先是完全二叉树，因为是完全二叉树所以使用数组储存比较合理。

一、堆的实现

1.1 堆的向下调整算法

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

给上一个例子

int arr[] = {27,15,19,18,28,34,65,49,25,37};

上面这幅图就是向下调整的算法的过程图

思路：

假设我们通过向下调整算法建立小堆，我们就需要从根的左右子树开始，比较得出左右子树小的那一个和根比较，谁小谁就是根。我们之前还介绍父亲节点和孩子节点的概念，我们这里就要使用到。根据我们上面的思路，向下调整算法需要通过比较还在节点后进行调整。所以我们需要知道父亲节点然后再找到孩子节点为什么要知道父亲节点呢？我们通过数组储存着堆，下标就可以帮助我们找到孩子节点。

大致思路就是这样我们来写代码：

void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child = parent * 2 + 1;while (child < n){//假设法if (a[child] > a[child + 1] && child + 1 < n)//比较左右子树，找到较小的子树。{child++;}if (a[parent] > a[child])//数据交换{Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

解释一下个别代码，child + 1 < n 防止数组越界。

1.2 堆的向上调整算法

向上调整我们需要从最后一层向上调整，所以我们是通过孩子节点得到父亲节点。大致思路和向下调整一样，比较孩子节点的大小后再和父亲节点比较一直比较到根节点。根据child = parent *2+1 反推得到 parent = （ child -1 ）/2 。

直接上代码：

void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustUp(HPDataType* a,int child)//向上调整
{int 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;}}
}

1.3 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

给上一个例子：

int a[] = {1,5,3,8,7,6};

1.4 堆的复杂度计算

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

向下调整建堆的复杂度：

向上调整建堆的复杂度：

是O(N) = N * logN 得到方法和向下调整一样推导就可以了。

1.5 堆的插入

先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。

堆的插入需要用的向上调整

1.6 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

1.7 堆的代码实现

堆的初始化、销毁都是很简单和之前写的栈啊等等都十分相似。剩下一些获取堆顶元素、堆的个数、堆的判断都比较简单就不讲解了给上了代码。

typedef int HPDataType;typedef struct Heap//因为堆的定义就是满二叉树与完全二叉树，用数组储存非常好。
{HPDataType* a;//数组int size;int capacity;
}Heap;//小堆情况下的初始化
void HPInit(Heap* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestory(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* x, HPDataType* y)//交换数据
{HPDataType tmp = *x;*x = *y;*y = tmp;
}void ADjustUp(HPDataType* a,int child)//向上调整
{int 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 ADjustDown(HPDataType* a, int n,int parent)//向下调整
{int child = parent * 2 + 1;while (child < n){//假设法if (a[child] > a[child + 1] && child + 1 < n){child++;}if (a[parent] > a[child]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//入堆
void HPPush(Heap* php, HPDataType x)
{assert(php);//扩容if (php->size == php->capacity){int Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, Newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("ralloc fail");return;}php->a = tmp;php->capacity = Newcapacity;}php->a[php->size++] = x; ADjustUp(php->a,php->size - 1);
}//出堆（消除堆顶数据）
void HPPop(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);
}//取堆顶数据
HPDataType HPTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//堆的数据个数
int HPSize(Heap* php)
{assert(php);return php->size;
}//堆的判空
bool HPEmpty(Heap* php)
{assert(php);return php->size == 0;
}