1.堆的概念及结构
如果有一个关键码的集合K = {K0 ,K1 ,K2 ,K3…,K(N-1) },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:Ki <= K2*i+1且 Ki<=K2*i+2 ) i = 0,1, 2…,则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。
2.堆的性质
(1)堆中某个结点的值总是不大于或不小于其父结点的值;
(2)堆总是一棵完全二叉树。
3.堆的实现
1.第一种
/*向上调整算法(此代码适合大堆)*/
void xiangshang(int *a,int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] < a[child]){int c;c = a[parent];a[parent] = a[child];a[child] = c;}/*else{break;}*/child = parent;parent = (child - 1) / 2;}
}
/*建堆(此代码会建成大堆)*/
void jiandui(int *b,int n)
{for (int i = 0; i < n; i++){xiangshang(b, i);}
}
第一种建堆的具体讲解请看《四种排序方法的补充》 ,里面配有图文讲解,也有向上调整算法与向下调整算法(后面要用到)的图文讲解,希望你可以有耐心的看另一篇文章,希望我的这些讲解对你有用。
C--四种排序方法的补充-CSDN博客
2.第二种
1.创建堆所需要的模型
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
size是确定我开辟的空间中,用掉了多少空间。capacity是确定我开辟了多少个空间。
2.堆的初始化
/*初始化*/
void Init(HP* ps)
{assert(ps);ps->a = NULL;ps->size = ps->capacity = 0;
}
3.堆的销毁
/*销毁*/
void Destroy(HP* ps)
{assert(ps);free(ps->a);ps->a = NULL;
}
这里要注意的是free(ps->a)之后,free(ps)是错误的操作。不可以销毁ps
4.插入
/*插入(通过插入会形成大堆)*/
void HeapPush(HP* ps, HPDataType x)
{assert(ps);assert(x);if (ps->capacity == 0){HPDataType* b = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (b == NULL){perror("malloc");exit(0);}ps->capacity = 4;ps->a = b;}if (ps->size == ps->capacity){HPDataType newcapacity = 2 * ps->capacity;HPDataType* b = (HPDataType*)realloc(ps->a, newcapacity * sizeof(HPDataType));if (b == NULL){perror("relloc");exit(0);}ps->a = b;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;xiangshang(ps->a, ps->size - 1);
}
在插入之前我要先判断我是否开辟了空间,然后判断这个空间是否已经被填满。最后再将你所需要的数字放入到最后的位置,通过向上调整算法完成排序。
5.删除元素
/*向下调整算法(此代码适合大堆)*/
void xiangxia(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if ((child + 1) < n && a[child + 1] > a[child]){child++;}if (a[child] > a[parent]){int c;c = a[child];a[child] = a[parent];a[parent] = c;}parent = child;child = parent * 2 + 1;}
}
/*删除元素(此代码在删除元素后还是会形成大堆)*/
void HeapPop(HP* ps)
{assert(ps);assert(ps->size > 0);HPDataType b = ps->a[0];ps->a[0] = ps->a[ps->size - 1];ps->a[ps->size - 1] = b;ps->size--;xiangxia(ps->a, ps->size, 0);
}
删除元素删除的是根的元素,所以我先将根元素与最后的一个元素进行调换位置,然后让size--,(size--是因为下一次插入时,会将那个元素覆盖掉。)最后通过向下调整对这个堆重新排序,(注意:这个代码的前提是这个堆是大堆)让第二个大的坐到根的位置。
6.返还树根元素
/*返回树根元素*/
HPDataType HeapTop(HP* ps)
{assert(ps);assert(ps->size > 0);return ps->a[0];
}
7.判断是否为空
/*判断是否为空*/
bool HeapEmpty(HP* ps)
{return ps->size == 0;
}
因为当我初始化之后,size便是0,只有当插入元素之后,size才会大于或等于1。
8.算多少个
/*算多少个数*/
int HeapSize(HP* ps)
{assert(ps);return ps->size;
}
9.打印树的内容
/*打印树的内容*/
void HeapPrintf(HP* ps,int size)
{int i = 0;for (; i < size; i++){printf("%d ", ps->a[i]);}
}