堆（1）

未分类 • 463 • 0

tgw 7 月前

以下代码gitee仓库地址tgw/数据结构。

堆的概念：如果有一个关键码的集合K = {k1 ，k2 ，k3 ，k4…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中.

大根堆：父节点大于或等于子节点的堆

小跟堆：父节点小于或等于父节点的堆

堆的实现：

首先定义：

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#include
#include
#include
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);
bool HPEmpty(HP* php);

结构体里面一共包括3个成员：实现的堆的数组，大小，空间

下面是具体函数的实现：

核心算法就是向上调整算法，向下调整算法：

void AdjustUp(HPDataType* a, int child)
{
// 初始条件
// 中间过程
// 结束条件
int parent = (child – 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child – 1) / 2;
}
else
{
break;
}
}
}

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, newcapacity * sizeof(HPDataType));
    if (tmp == NULL)
    {
        perror("realloc fail");
        return;
    }

    php->a = tmp;
    php->capacity = newcapacity;
}

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

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

}

void AdjustDown(HPDataType* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n) // child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a[child + 1] < a[child])
{
++child;
}

    if (a[child] < a[parent])
    {
        Swap(&a[child], &a[parent]);
        parent = child;
        child = parent * 2 + 1;
    }
    else
    {
        break;
    }
}

}

向下调整算法示意图：