C语言实现堆

布满荆棘的人生 2023-01-02 14:28 136阅读 0赞

# 堆的实现 #

今天来介绍一个新的数据结构：**堆**

大家都记得，内存空间存储中，将局部变量，函数参数等存储在栈上，系统自动释放；全局变量存储在静态存储区；动态开辟的内存空间都在堆上开辟，系统不会自动释放空间，由程序员手动释放。

当然，此处的堆是内存空间的一种存储结构

今天我们所介绍的堆结构是一种二叉树结构，主要应用于 系统目录的存储，比如linux系统下目录的存储方式就是一个二叉树的堆来存储，以根目录下分级目录存储

**堆是一种二叉树的结构，满足二叉树的性质**

### **堆的性质：** ###

**1.堆中某个节点的值总是不大于或不小于其父节点的值；**

**2.堆总是一棵完全二叉树。**

### 二叉树的性质： ###

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为 底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，

则对 于序号为i的结点有：**1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点**

**2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子**

**3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子**  
为直观表示堆结构，小堆结构如下图：以顺序表的方式存储

![20210106152314439.png][]

大堆结构如下图：

![20210106154042568.png][]

### 堆的实现： ###

**（1）堆的结构创建及初始化**

typedef int HPDataType;
    typedef struct Heap
    {
    	HPDataType* _a;
    	int _size;
    	int _capacity;
    }Heap;
    
    // 堆的构建
    void HeapInit(Heap* hp)
    {
    	if (hp == NULL)
    	{
    		return;
    	}
    	hp->_a = NULL;
    	hp->_capacity = hp->_size = 0;
    }
    // 堆的销毁
    void HeapDestory(Heap* hp)
    {
    	free(hp->_a);
    	hp->_a = NULL;
    	free(hp);
    	hp = NULL;
    }

**（2）维护最小堆 向下调整**

找到当前节点的子节点，先找到子节点中最小的一个

如果当前节点大于最小的子节点，交换，更新当前位置为最小孩子位置

否则 跳出，结束调整

void shiftdown(int* arr, int n, int curpos)
    {
    	int child = 2 * curpos + 1;//根据当前位置，给出左孩子位置由于关系：左孩子+1=右孩子
    	while (child < n)//直到孩子索引越界  即再找不到孩子节点
    	{
    		if (child + 1 < n&&arr[child + 1] < arr[child])//左右孩子比较找最小值
    			child++;//右孩子小，child++， 否则  child不变      由于关系：左孩子+1=右孩子
    		if (arr[child] < arr[curpos])//a当前位置与孩子中的小值比较  当前位置值大 向下调整
    		{
    			//交换
    			int tmp = arr[child];
    			arr[child] = arr[curpos];
    			arr[curpos] = tmp;
    
    			curpos = child;//交换完成后  用之前孩子位置 更新当前位置
    			child = 2 * curpos + 1;//根据当前位置，给出左孩子位置
    		}
    		else
    		{
    			break;
    		}
    	}
    }

**（3）维护最小堆，向上调整**

当前节点和父节点比较，如果小于父节点，交换二者，更新当前节点位置为父节点位置，从当前父节点继续向上查找

否则，跳出 ，结束调整

void shiftup(int* newarr, int n, int curpos)
    {
    	//维护小堆  从底向上找
    	//int curpos = n;
    	int parent = (curpos - 1) / 2;//根据当前位置，给出左孩子位置由于关系：左孩子+1=右孩子
    	while (curpos > 0)
    	{
    		if (newarr[curpos] < newarr[parent])//和父节点比较
    		{
    			//交换
    			int tmp = newarr[parent];
    			newarr[parent] = newarr[curpos];
    			newarr[curpos] = tmp;
    
    			curpos = parent;//交换完成后  更新当前位置
    			parent = (curpos - 1) / 2;
    		}
    		else
    			break;
    	}
    }

**（4）堆的插入：**

尾部插入，然后执行向上调整，维护最小堆

void checkcapacity(Heap *hp)
    {
    	if (hp->_size == hp->_capacity)
    	{
    		hp->_capacity = hp->_capacity == 0 ? 1 : 2 * hp->_capacity;
    		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType)*hp->_capacity);
    	}
    }
    // 堆的插入
    void HeapPush(Heap* hp, HPDataType x)
    {
    	//检测容量
    	checkcapacity(hp);
    	//尾插
    	hp->_a[hp->_size++] = x;
    	//向上调整
    	shiftup(hp->_a, hp->_size, hp->_size - 1);
    }

**（5）堆的删除**

堆顶元素和堆的最后一个元素交换，然后尾删操作，并维护堆的特性

void swap(int*a, int*b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    // 堆的删除
    void HeapPop(Heap* hp)
    {
    	if (hp == NULL || hp->_size == 0)
    		return;
    	//堆顶元素和最后一个元素交换
    	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
    	//尾删
    	hp->_size--;
    	//向下调整  维护最小堆  从小到大
    	shiftdown(hp->_a, hp->_size, 0);
    }

**（6）堆顶元素，堆判空**

// 取堆顶的数据
    HPDataType HeapTop(Heap* hp)
    {
    	return hp->_a[0];
    }
    // 堆的数据个数
    int HeapSize(Heap* hp)
    {
    	return hp->_size;
    }
    // 堆的判空
    int HeapEmpty(Heap* hp) 
    {
    	if (hp == NULL || hp->_size == 0)
    		return 1;
    	else
    		return 0;
    }

**（7）堆排序：**

**维护大堆 从小到大排序 维护小堆 从大到小排序**

**以下图为例：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

void HeapSort(int* a, int n)
    {
    	//1 建堆
    	for (int i = (n - 2) / 2; i >= 0; i--)//经过每一个节点的父节点
    	{
    		shiftdown(a, n, i);//i为调整的起始位置
    	}
    	while (n > 0)
    	{
    		swap(&a[0], &a[n - 1]);
    		n--;
    		shiftdown(a, n, 0);
    	}
    }

结果如下：从小打到排序前提就是维护大堆

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

**（8）前k大值：**

// TopK问题：找出N个数里面最大/最小的前K个问题。
    // 比如：未央区排名前10的泡馍，西安交通大学王者荣耀排名前10的韩信，全国排名前10的李白。等等问题都是Topk问题，
    // 需要注意：
    // 找最大的前K个，建立K个数的小堆
    // 找最小的前K个，建立K个数的大堆
    void PrintTopK(int* a, int n, int k)
    {
    	Heap hp;
    	HeapInit(&hp);
    	for (int i = 0; i < n; i++)
    	{
    		HeapPush(&hp, a[i]);//建大堆
    	}
    	while (k--)
    	{
    		printf("%d ",HeapTop(&hp));
    		HeapPop(&hp);
    	}
    }

测试代码：

void TestTopk()
    {
    	int n = 10000;
    	int*a = (int*)malloc(sizeof(int)*n);
    	srand(time(0));
    	for (int i = 0; i < n; i++)
    	{
    		a[i] = rand() % 1000000;
    	}
    	a[5] = 1000000 + 1;
    	a[1231] = 1000000 + 2;
    	a[531] = 1000000 + 3;
    	a[5121] = 1000000 + 4;
    	a[115] = 1000000 + 5;
    	a[2335] = 1000000 + 6;
    	a[9999] = 1000000 + 7;
    	a[76] = 1000000 + 8;
    	a[423] = 1000000 + 9;
    	a[3144] = 1000000 + 10;
    	PrintTopK(a, n, 10);
    }

输出结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

**最终测试：以维护大堆结构 依次弹出栈顶元素，以及从小到大排序和前k大元素**

//*************************************
    void test1()
    {
    	Heap hp;
    	HeapInit(&hp);
    	HeapPush(&hp, 28);
    	HeapPush(&hp, 29);
    	HeapPush(&hp, 45);
    	HeapPush(&hp, 46);
    	HeapPush(&hp, 25);
    	HeapPush(&hp, 38);
    	HeapPush(&hp, 19);
    	HeapPush(&hp, 8);
    	while (!HeapEmpty(&hp))
    	{
    		printf("%d ", HeapTop(&hp));
    		HeapPop(&hp);
    	}
    }
    
    void test2()
    {
    	int arr[] = { 100,20,3,6,89,12,15,36,25 };
    	int len = sizeof(arr) / sizeof(int);
    	HeapSort(arr, len);
    	for (int i = 0; i < len; i++)
    		printf("%d ", arr[i]);
    }
    
    void TestTopk()
    {
    	int n = 10000;
    	int*a = (int*)malloc(sizeof(int)*n);
    	srand(time(0));
    	for (int i = 0; i < n; i++)
    	{
    		a[i] = rand() % 1000000;
    	}
    	a[5] = 1000000 + 1;
    	a[1231] = 1000000 + 2;
    	a[531] = 1000000 + 3;
    	a[5121] = 1000000 + 4;
    	a[115] = 1000000 + 5;
    	a[2335] = 1000000 + 6;
    	a[9999] = 1000000 + 7;
    	a[76] = 1000000 + 8;
    	a[423] = 1000000 + 9;
    	a[3144] = 1000000 + 10;
    	PrintTopK(a, n, 10);
    }
    
    
    int main()
    {
    	printf("大堆堆顶元素依次输出：\n");
    	test1();
    	printf("\n");
    	printf("从小到大依次排序：\n");
    	test2();
    	printf("\n");
    	printf("输出前k大元素：\n");
    	TestTopk();
    	return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

[20210106152314439.png]: /images/20221119/3ccaa3648140413c9491eceaff6b98c7.png
[20210106154042568.png]: /images/20221119/36fe89c56baf470a8bd230b1981af50d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221119/281d0739358844268b64e3ccd860f8d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221119/0eed95c4c8a941c5b24a69827e9839b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221119/ef56d8d989164aa1b623d381efa6d015.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221119/9f56f0d2407d4d2c8bbfe7785fb52ff1.png