数据结构——堆（存储完全二叉树）

一、堆的概念

堆是一种顺序存储完全二叉树的数据结构。

二、堆的一些性质

堆分为小堆和大堆：

小堆要求父亲结点数据小于孩子结点；

大堆要求父亲结点数据小于孩子结点。

如何根据孩子结点下标找到父亲结点？

parent = (child - 1) / 2

如何根据父亲结点下标找到孩子结点？

child = 2 * parent + 1 （左孩子）

三、堆的结构定义

堆的结构中包含数组、堆大小、堆容量

//堆的结构定义

typedef int HPDataType;

typedef struct Heap {

HPDataType* a;

int size;

int capacity;

}HP;

四、堆的初始化

将数组初始化为空，堆大小和容量都初始化为0

//堆的初始化

void HPInit(HP* php)

{

php->a = NULL;

php->size = 0;

php->capacity = 0;

}

五、堆打印

打印数组

//堆打印

void HPPrint(HP* php)

{

assert(php);

for (int i = 0; i < php->size; i++)

{

printf("%d ", php->a[i]);

}

printf("\n");

}

六、向上调整算法

孩子结点与父亲结点比较，如果孩子结点小于父亲结点，就将孩子结点与父亲结点交换。

注意第二个循环条件：是 child > 0，为什么不是 parent >=0 呢？

因为parent最小是0，永远不会小于0。但是该代码也能跑，因为当parent为0时，重置下标时，child重置为0，而parent = (child - 1) / 2也重置为0，此时a[child] = a[parent]，因此循环结束。

//向上调整算法

void AdjustUp(HPDataType*a, int child)

{

int parent = (child - 1) / 2;

while (a[child] < a[parent] && child > 0)//孩子结点比父亲结点小

{

//交换父亲结点和孩子结点的数据

HPDataType tmp = a[child];

a[child] = a[parent];

a[parent] = tmp;

//父亲结点和孩子结点下标重置

child = parent;

parent = (child - 1) / 2;

}

}

七、堆的插入

插入数据前先检查堆容量是否足够，容量不够则扩容，容量足够则将数据存入数组中，再用向上调整算法将新插入的数据进行调整。

//堆的插入

void HPPush(HP* 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, sizeof(HPDataType) * newcapacity);

if (tmp == NULL)

{

perror("realloc fail");

exit(-1);

}

php->a = tmp;

php->capacity = newcapacity;

}

php->a[php->size++] = x;

//向上调整算法

AdjustUp(php->a, php->size - 1);

}

八、向下调整算法

将父亲结点与孩子结点比较，如果父亲结点大于孩子结点，则交换

由于可能有两个孩子结点，先要确认右孩子是否存在，如果存在取较小的孩子结点与父亲结点交换

//向下调整算法

void AdjustDown(HPDataType* a, int size, int parent)

{

int child = parent * 2 + 1;

while (child < size)

{

if (child + 1 < size)//存在右孩子

{

if (a[child + 1] < a[child])//右孩子比左孩子小，用右孩子顶替父亲结点位置

{

child = child + 1;

}

}

if (a[child] < a[parent])

{

//交换父亲结点与孩子结点

HPDataType tmp = a[child];

a[child] = a[parent];

a[parent] = tmp;

//重置父亲结点和孩子结点

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

九、堆的删除

堆的删除是删除堆顶元素，因为删除堆尾元素是没有意义的。

删除堆顶即删除二叉树的根，删除后还要使之成为一个完全二叉树，所以需要用次小值去顶替堆顶的位置。

具体方法：

先将堆尾元素与堆顶元素交换位置，然后删除堆尾元素，再利用向下调整算法将堆顶位置元素向下调整到合适的位置。

//堆的删除

void HPPop(HP* php)

{

assert(php);

assert(php->size);//空堆不可删除

//交换堆顶元素和堆底元素

HPDataType tmp = php->a[0];

php->a[0] = php->a[php->size - 1];

php->a[php->size - 1] = tmp;

//删除堆底元素

php->size--;

//向下调整算法

AdjustDown(php->a, php->size, 0);

}

十、取堆顶元素

先判断堆是否为空，不空则返回堆顶元素

//取堆顶元素

HPDataType HPTop(HP* php)

{

assert(php);

assert(php->size);

return php->a[0];

}

十一、求堆大小

返回size即可

//求堆大小

size_t HPSize(HP* php)

{

assert(php);

return php->size;

}

十二、堆判空

利用size判断堆是否为空

//判空

bool HPEmpty(HP* php)

{

assert(php);

return php->size == 0;

}

十三、测试代码

void test01()

{

//创建堆

HP hp;

//初始化堆

HPInit(&hp);

//堆插入

HPPush(&hp, 1);

HPPush(&hp, 5);

HPPush(&hp, 3);

HPPush(&hp, 6);

HPPush(&hp, 7);

HPPush(&hp, 5);

HPPush(&hp, 4);

HPPush(&hp, 9);

HPPush(&hp, 8);

//堆打印

HPPrint(&hp);

//堆插入

HPPush(&hp, 1);

//堆打印

HPPrint(&hp);

//堆删除

HPPop(&hp);

//堆打印

HPPrint(&hp);

//取堆顶元素

printf("%d\n", HPTop(&hp));

//求堆大小

printf("%zd\n", HPSize(&hp));

//堆判空

if (HPEmpty(&hp))

printf("空\n");

else

printf("非空\n");

}

int main()

{

test01();

return 0;

}