[C语言实现]数据结构堆之《害怕二叉树所以天赋全点到堆上了》

?作者: FlashRider

?专栏: 数据结构

?知识概要：详解堆的概念、小根堆与大根堆的区别、以及代码实现。

什么是堆？

如何实现堆？

代码实现堆(小根堆)

定义堆以及堆的初始化和销毁。

堆的插入

堆的删除

获取堆的元素长度和获取堆顶元素

代码测试

TopK问题

文章来源地址https://uudwc.com/A/Xvnk

什么是堆？

我们先来一点二叉树的知识。首先我们需要知道，树的一个节点如果含有子节点，那么这个节点可以称为父节点，一个节点含有的子树个数称为该节点的度，而度都为2的树，则称为二叉树。
完全二叉树则是最后一排子节点可以不全都是2个的二叉树 ( 满二叉树也是完全二叉树 )。
还有满二叉树，也就是每一个父结点的子节点都有2个的二叉树。

一个堆(Heap)通常可以看作一个完全二叉树，准确来说任何一个顺序表都可以看作一个完全二叉树。但是根在完全二叉树的基础上有一些特性。

小根堆：任何一个父节点都比子节点的值要小。

大根堆：任何一个父节点都比子节点的值要大。

如何实现堆？

我们知道，堆可以看作一个完全二叉树，且满足堆本身的特性(小根堆大根堆)，而顺序表也可以看作一个完全二叉树。比如SeqList a = {1, 2, 3, 4, 5};

而图中1 < 2 && 1 < 3; 2 < 4 && 2 < 5 所有的父节点的大于子节点，这个恰好满足小根堆特性，如果倒过来也可以满足大根堆特性，所以可以用顺序表来实现堆。
我们用下标为0的地方当作根节点，然后根的左子节点，根的右子节点，以此类推。

[0]为父节点 [1] [2]为子节点 [1]为父节点 [3][4]为子节点 [2]没有子节点所以后面为空。
我们还可以发现一个下标的规律：左子节点 = 父节点 * 2 + 1 右子节点 = 父节点 * 2 + 2
父节点 = (子节点 - 1) / 2 (整除，向下取整)
因此用顺序表存储可以让我们轻易的通过子节点找到父节点，父节点找到子节点。

代码实现堆(小根堆)

定义堆以及堆的初始化和销毁。

因为我们使用顺序表来实现堆，所以按照顺序表的定义初始化方法来写。

typedef int HPDataType;//元素类型
typedef struct Heap
{
    HPDataType* a;//首元素地址
    int size;//当前长度
    int capacity;//最大长度
}HP;
//初始化堆
void HeapInit(HP* root);
//销毁堆
void HeapDestroy(HP* root);

void HeapInit(HP* root)
{
    assert(root);//断言
    root->a = NULL;
    root->size = root->capacity = 0;
}
void HeapDestroy(HP* root)
{
    assert(root);
    free(root->a);//释放开辟的内存空间
    root->a = NULL;
    root->size = root->capacity  = 0;
}

堆的插入

如果当前数据是一个小根堆，我们如果要在后面插入一个数据(比如插入一个比父节点更小的数据)，并不能和保证它还是堆，所以我们在尾部插入数据之后，需要将这个数进行向上调整，以保证满足小根堆的特性。

void HeapPush(HP* root, HPDataType x);
void AdjustUp(HPDataType*a, int child);

void HeapPush(HP* root, HPDataType x)
{
    assert(root);
    //判满
    if(root->size == root->capacity)
    {
        int newcapacity = root->capacity == 0 ? 4 : root->capacity * 2;//增容
        //内存开辟扩容
        HPDataType* tmp = (HPDataType*)realloc(root->a, sizeof(HPDataType)*newcapacity);
        if(tmp == NULL)//内存开辟是否成功
        {
            printf("realloc fail\n");
            exit(-1);
        }
        root->capacity = newcapacity;
        root->a = tmp;
    }
    root->a[root->size] = x;
    root->size++;
    //将尾部插入的数据向上调整
    AdjustUp(root->a, root->size - 1);
}
void AdjustUp(HPDataType*a, int child)
{
    assert(a);
    while(child > 0)
    {
        int parent = (child - 1) / 2; //之间总结的公式算出父节点
        if(a[parent] > a[child]) //如果父节点更大 就不满足小根堆 需要交换
        {
            int tmp = a[parent];
            a[paretn] = a[child];
            a[child] = tmp;
            child = parent;//交换后更新子节点
        }
        else break; //如果父节点更小 满足小根堆 不需要再调整
    }
}

堆的删除

堆的删除是从堆顶删除元素，但是同样的道理，我们删除堆顶元素后，不能保证接下来的数据还是一个堆，并且挪动大量元素会很麻烦，所以我们把首元素和尾元素交换，直接删除尾元素就等于删除堆顶元素了，之后再让交换后的堆顶元素向下调整保证是堆即可。

void HeapPop(HP* root);
void AdjustDown(HPDataType* a, int n, int parent);
bool HeapEmpty(HP* root);//是否为空
void HeapPop(HP* root)
{
    assert(root);
    assert(!HeapEmpty(root));//如果堆为空就没元素可以pop了
    //交换首尾元素
    HPDataType tmp = root->a[root->size - 1];
    root->a[root->size - 1] = root->a[0];
    root->a[0] = tmp;
    //删除尾元素
    root->size--;
    //将堆顶向下调整 
    AdjustDown(root->a, root->size, 0);
}
void AdjustDown(HPDataType* a, int n, int parent)
{
    assert(a);
    int child = parent * 2 + 1;//算出左孩子
    while(child < n)//比到最后一个节点结束
    {
        if(child + 1 < n && a[child] > a[child+1])
            child++; //如果右子节点存在 且小于左子节点 则child变为右子节点。
        if(a[child] < a[parent])//保证满足小根堆
        {
            HPDataType tmp = a[child];
            a[child] = a[parent];
            a[parent] = tmp;
            parent = child;
            child = parent * 2 + 1;//更新子节点和父节点
        }
        else break;
    }
}
bool HeapEmpty(HP* root)
{
    assert(root);
    return root->size == 0; //为空返回真 不为空返回假
}

获取堆的元素长度和获取堆顶元素

void HeapSize(HP* root);
void HeapTop(HP* root);

void HeapSize(HP* root)
{
    assert(root);
    return root->size;
}
void HeapTop(HP* root)
{
    assert(root);
    assert(!HeapEmpty(root));
    return root->a[0];
}

代码测试

堆以及写的差不多了，我们来测试一下是否成功。

int main()
{
	HP hp;
	HeapInit(&hp);
	int a[] = {65, 100, 70, 32, 50, 60};
	for(int i = 0; i < 6; i++)
		HeapPush(&hp, a[i]);
	while(!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}
	return 0;
}

测试结果：

测试没问题，满足小根堆。

TopK问题

给一组长度为n的数据，要求在这n个数中找出最大/最小的K个数据。

如果我们暴力直接遍历的话，时间复杂度非常高，数据量一旦比较大就会TLE。

但是堆可以解决这种问题。

找最大：建小堆。

找最小：建大堆。

如果给你一万个数，要求找最大的10个，我们只需要把前10个建成小堆。然后把剩下的数据和堆顶元素比较（小堆的堆顶元素最小）如果比堆顶还小直接排除，如果比堆顶大则变成新的堆顶并向下调整。最后就能得到最大的10个数。

void PrintTopK(int k, int* a, int n)
{
	Heap hp;
    HeapInit(&hp);
    for(int i = 0; i < k; i++)
        HeapPush(&hp, a[i]);
    for(int i = k; i < n; i++)
    {
        if(a[i] > HeapTop(&hp))
        {
            hp.a[0] = a[i];
            AdjustDown(hp.a, k, 0);
        }
    }
    for(int i = 0; i < k; i++)
    {
    	printf("%d ", HeapTop(&hp));
    	HeapPop(&hp);
	}
}
int main()
{
    int arr[20] = {1,2,3,4,5,10,12,15,20,6,7,8,9,11,13,14,18,19,16,17};
    PrintTopK(5, arr, 20);
    return 0;
}

运行结果：

没有任何问题。