【数据结构】二叉树的顺序结构（堆）及实现

约定不等于承诺〃 2023-02-18 09:43 5阅读 0赞

**1. 前言**  
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。  
**2.堆的概念及结构**  
如果有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

**堆的性质**  
1.堆中某个节点的值总是不大于或不小于其父节点的值；  
2.堆总是一棵完全二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]

**3.堆的实现**  
**3.1 堆的向下调整**  
条件：在调整某个节点时，必须满足该节点左右子树满足堆的性质  
步骤：  
1.如果右孩子存在的情况下，找parent的左右孩子中较小的孩子，用child标记。  
2.检测parent是否比较小的孩子大  
是：将双亲与孩子节点中的值进行交换，继续向下调整  
否：parent节点已经满足堆的特性，直接返回。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]

**3.2 堆的创建**  
a.根据元素个数初始化堆空间  
b.将数组中的元素拷贝到堆结构中的连续空间—完全二叉树  
c.对堆结构中的数据进行调整，使其满足堆的性质  
\#\#1.找完全二叉树第一个非叶子节点（最后一个节点的双亲）LastNotLeaf=(size-2)/2  
\#\#2.从LastNotLeaf位置向前一直调整到根节点位置：每个节点向下调整  
**3.3 堆的插入**  
先将数据插入到数组的末尾，采取向上调整，直到满足堆的性质。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]

**3.4 堆的删除**  
删除的是堆顶元素  
1.检测堆是否为空，若为空直接返回，否则进行2；  
2.将堆顶元素与堆中最后一个元素进行交换，有效元素个数减一，然后对堆顶元素进行向下调整。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]

**3.5 代码实现**  
**Heap.h**

#pragma once
    
    typedef int HDataType;
    
    int Less(HDataType left, HDataType right);//小堆
    int Greater(HDataType left, HDataType right);//大堆
    //Cmp的函数指针类型变量：Cmp即可以指向Less,也可以指向Greater
    int (*Cmp)(HDataType left, HDataType right);
    
    typedef int(*CMP)(HDataType, HDataType);
    
    typedef struct Heap
    {
        
    	HDataType* array;
    	int capacity;
    	int size;
    	CMP Cmp; //函数指针
    }Heap;
    
    void HeapInit(Heap* hp, int initCap,CMP cmp);
    void HeapCreate(Heap* hp, int* array, int size,CMP cmp);
    void HeapPush(Heap* hp, HDataType data);
    void HeapPop(Heap* hp);
    HDataType HeapTop(Heap* hp);
    int HeapEmpty(Heap* hp);
    int HeapSize(Heap* hp);
    void HeapDestroy(Heap* hp);

**Heap.c**

#include "Heap.h"
    #include <malloc.h>
    #include <assert.h>
    #include <stdio.h>
    #include <string.h>
    
    int Less(HDataType left, HDataType right)
    {
        
    	return left < right;
    }
    int Greater(HDataType left, HDataType right)
    {
        
    	return left > right;
    }
    //初始化一个空堆
    void HeapInit(Heap* hp, int initCap,CMP cmp)
    {
        
    	assert(hp);
    	initCap = initCap < 10 ? 10 : initCap;
    	hp->array = (HDataType*)malloc(sizeof(HDataType)* initCap);
    	if (NULL == hp->array)
    	{
        
    		assert(0);
    		return;
    	}
    	hp->capacity = initCap;
    	hp->size = 0;
    	//接收比较的方式
    	hp->Cmp = cmp;
    }
    //交换两个数据
    void Swap(HDataType* left, HDataType* right)
    {
        
    	HDataType temp = *left;
    	*left = *right;
    	*right = temp;
    }
    //向下调整
    void AdjustDown(Heap* hp, int parent)
    {
        
    	//用child标记parent的较小的孩子--默认先标记parent的左孩子
    	int size = hp->size;
    	int *array = hp->array;
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
        
    		//找到parent两个孩子中较小的孩子
    		if (child + 1 < size&&hp->Cmp(array[child+1],array[child]))
    			child += 1;
    		//检测parent是否满足堆的性质
    		if (hp->Cmp(array[child],array[parent]))
    		{
        
    			Swap(&array[child], &array[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
        
    			return;
    		}
    	}
    }
    //用数组中的元素创建堆
    void HeapCreate(Heap* hp, int* array, int size, CMP cmp)
    {
        
    	//1.先将数组中的元素放在堆结构中
    	HeapInit(hp, size,cmp);
    	memcpy(hp->array, array, sizeof(HDataType)*size);
    	hp->size = size;
    	//2.进行调整
    	for (int root = (size - 2) / 2; root >= 0; root--)
    		AdjustDown(hp, root);
    }
    //向上调整
    void AdjustUP(Heap* hp, int child)
    {
        
    	HDataType* array = hp->array;
    	int size = hp->size;
    	int parent = ((child - 1) >> 1);
    	while (child)
    	{
        
    		if (hp->Cmp(array[child] , array[parent]))
    		{
        
    			Swap(&array[child], &array[parent]);
    			child = parent;
    			parent = ((child - 1) >> 1);
    		}
    		else
    		{
        
    			return;
    		}
    	}
    }
    //检查容量
    void CheckCapacity(Heap* hp)
    {
        
    	assert(hp);
    	if (hp->size == hp->capacity)
    	{
        
    		//1.开辟新空间
    		int newCapacity = hp->capacity * 2;
    		HDataType* temp = (HDataType*)malloc(sizeof(HDataType)*newCapacity);
    		if (NULL == temp)
    		{
        
    			assert(0);
    			return;
    		}
    		//拷贝元素
    		for (int i = 0; i < hp->size; ++i)
    			temp[i] = hp->array[i];
    		//3.释放旧空间
    		free(hp->array);
    		//4.使用新空间
    		hp->array = temp;
    		hp->capacity = newCapacity;
    	}
    }
    //插入元素
    void HeapPush(Heap* hp, HDataType data)
    {
        
    	assert(hp);
    	//0.检测是否需要扩容
    	CheckCapacity(hp);
    	//1.将新元素插入到数组的末尾
    	hp->array[hp->size++] = data;
    	//2.新元素插入后，可能会破坏堆的性质
    	AdjustUP(hp, hp->size - 1);
    }
    //删除堆顶元素
    void HeapPop(Heap* hp)
    {
        
    	if (HeapEmpty(hp))
    		return;
    	Swap(&hp->array[0], &hp->array[hp->size - 1]);
    	hp->size--;
    	AdjustDown(hp, 0);
    }
    //获取堆顶元素
    HDataType HeapTop(Heap* hp)
    {
        
    	assert(!HeapEmpty(hp));
    	return hp->array[0];
    }
    //堆为空返回非零值
    int HeapEmpty(Heap* hp)
    {
        
    	assert(hp);
    	return 0 == hp->size;
    }
    //堆中元素个数
    int HeapSize(Heap* hp)
    {
        
    	assert(hp);
    	return hp->size;
    }
    //销毁堆
    void HeapDestroy(Heap* hp)
    {
        
    	assert(hp);
    	free(hp->array);
    	hp->array = NULL;
    	hp->capacity = 0;
    	hp->size = 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617102829616.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200617110234168.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200617110320381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200617110504241.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp,size_16,color_FFFFFF,t_70