【数据结构】二叉树——堆如何实现

浅浅的花香味﹌ 2023-10-13 14:30 20阅读 0赞

**目录**

一、二叉树的顺序结构

二、堆的概念及结构

三、堆的实现

四、堆的应用

4.1 堆排序

4.1.1 建堆

4.1.2 利用堆删除思想来进行排序

4.2 TOP-K问题

很多时候，我们竞争对手是我们自己，而不是别人。

--------------------

## 一、二叉树的顺序结构 ##

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 **现实中我们通常把** **堆** **(** **一种二叉树** **)** **使用顺序结构的数组** **来存储，需要注意的是这里的堆和操作系统** **虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。**

## 二、堆的概念及结构 ##

如果有一个关键码的集合K =\{ k0,k1,k2……，k(n-1)\}【0,1,2，……，n-1这些都是下标】，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki<=k(2\*i+1)且Ki<=k2\*i+2【Ki>=k(2\*i+1)且Ki>=k(2\*i+2)】i=0,1,2…，则称为小堆【或大堆】。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

**堆的性质**:1）堆中某个节点的值总是不大于或不小于其父节点的值；2)堆总是一棵完全二叉树。

> **理解**：**堆分为大堆和小堆**；大堆/大根堆：树中父亲的数据都大于等于孩子；小堆/小根堆：树中父亲的数据都小于等于孩子

> **堆解决的问题**：堆排序、TOP-K

## 三、堆的实现 ##

**heap.h**

#pragma once
    
    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    typedef int HPDataType;
    
    typedef struct Heap
    {
    	HPDataType* a;
    	size_t size;
    	size_t capacity;
    }HP;
    
    void HeapInit(HP* php);
    void HeapDestory(HP* php);
    void HeapPrint(HP* php);
    void Swap(HPDataType* pa, HPDataType* pb);
    void HeapPush(HP* php, HPDataType x);
    void HeapPop(HP* php);
    bool HeapEmpty(HP* php);
    size_t HeapSize(HP* php);
    HPDataType HeapTop(HP* php);

**heap.c**

#include "heap.h"
    
    void HeapInit(HP* php)
    {
    	assert(php);
    	php->a = NULL;
    	php->size = php->capacity = 0;
    }
    void HeapDestory(HP* php)
    {
    	assert(php);
    	free(php->a);
    	php->a = NULL;
    	php->size = php->capacity = 0;
    }
    
    //按数组打印
    void HeapPrint(HP* php)
    {
    	assert(php);
    	for (size_t i = 0; i < php->size; ++i)
    	{
    		printf("%d ", php->a[i]);
    	}
    	printf("\n");
    }
    
    void Swap(HPDataType* pa, HPDataType* pb)
    {
    	HPDataType tmp = *pa;
    	*pa = *pb;
    	*pb = tmp;
    }
    
    bool HeapEmpty(HP* php)
    {
    	assert(php);
    	return php->size == 0;
    }
    //多少个数据
    size_t HeapSize(HP* php)
    {
    	assert(php);
    	return php->size;
    }
    HPDataType HeapTop(HP* php)
    {
    	assert(php);
    	assert(php->size > 0);
    	return php->a[0];
    }

void AdjustUp(HPDataType* a, size_t child)
    {
    	size_t parent = (child - 1) / 2;
    	//这个比较取决于大小堆
    	//小堆
    	//最后一次比较，是parent是0，进行比较，当再次进行调整后。就不需要进行了，此时的child等于0，parent也是0[因为size_t是正整数】
    	//-1/2还是等于0
    	while (child > 0)
    	{
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;//跳出循环
    		}
    	}
    }
    
    void HeapPush(HP* php, HPDataType x)
    {
    	assert(php);
    	数据插入数组后
    	//先判断是否有地方进行扩容
    	if (php->size == php->capacity)
    	{
    		size_t newCapacity = php->capacity == 0 ? 4 : (2 * (php->capacity));
    		//开辟空间，要有一个临时变量进行开辟，否则如果开辟失败，里面的数据就都找不到了
    		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
    		if (tmp == NULL)
    		{
    			printf("malloc fail\n");
    			exit(-1);
    		}
    		php->a = tmp;
    		php->capacity = newCapacity;
    	}
    	php->a[php->size] = x;
    	(php->size)++;//先插入，后size++,此时size这个下标的位置并没有值
    	向上调整的算法，成为堆
    	size_t child = (php->size) - 1;
    	AdjustUp(php->a, child);
    }

> **堆的插入**：先插入一个数字到数组的尾上【插入的这个数字后，可能不满足堆的概念】，再进行向上调整算法，直到满足堆

void AdjustDown(HPDataType* a, size_t root, size_t size)
    {
    	//找出小的
    	//注意：可能没有右孩子
    	size_t parent = root;
    	size_t child = parent * 2 + 1;
    	while (child < size)
    	{
    		//避免越界
    		if (child + 1 < size && a[child] > a[child + 1])
    		{
    			child++;
    		}
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;//跳出循环
    		}
    	}
    }
    
    void HeapPop(HP* php)
    {
    	assert(php);
    	//当删除数据的时候，要判断有没有值
    	assert(php->size > 0);
    	Swap(&php->a[0], &php->a[php->size - 1]);
    	php->size--;
    	AdjustDown(php->a, 0, php->size);
    }

> **堆的删除**：删除堆是删除**堆顶【最小或者最大的数据】**的数据，将**堆顶的数据**和**最后一个数据****交**换，然后删除数组最后一个数据，再进行向下调整算法。【先交，后删除，在进行向下调整算法】
> 
> **向下调整算法****：**首先找出两个孩子节点中小（大）的那一个，然后去和父节点比较，进行交换，父节点的数据总是小于等于（大于等于）子节点，然后再从交换的孩子向下比较】

堆的插入、删除的时间复杂度为O(logN)

## 四、堆的应用 ##

### 4.1 堆排序 ###

> 堆排序即利用 **堆的思想**来进行排序，总共分为两个步骤：
> 
> 1. **建堆（在数组上建堆，那么堆排序的空间复杂度为O(1））**
> 
> 升序：建大堆
> 
> 降序：建小堆
> 
> 2. **利用堆删除思想来进行排序**

#### 4.1.1 **建堆** ####

> 建堆有两种方法：（1）使用向上调整，插入数据的思想建堆。插入数据到新的数组，就是在不断插入的过程中向上调整实现排序 【代码1】（2）使用向下调整【从倒数第一个非叶子节点开始，即最后一个节点的父亲，即（size-1-1）/2】【找到这个父亲的节点，向下排序，然后这个父亲节点依次减一【就找到各个小堆】，依次向下排序，就成为了一个堆。】【代码2】
> 
> 【建堆结束后，可以让数组成为一个堆】

代码1展示：

void Swap(HPDataType* pa, HPDataType* pb)
    {
    	HPDataType tmp = *pa;
    	*pa = *pb;
    	*pb = tmp;
    }
    
    
    void AdjustUp(HPDataType* a, size_t child)
    {
    	size_t parent = (child - 1) / 2;
    	//这个比较取决于大小堆
    	//小堆
    	//最后一次比较，是parent是0，进行比较，当再次进行调整后。就不需要进行了，此时的child等于0，parent也是0[因为size_t是正整数】
    	//-1/2还是等于0
    	while (child > 0)
    	{
    		if (a[child] < a[parent])
    		{
    			Swap(&a[child], &a[parent]);
    			child = parent;
    			parent = (child - 1) / 2;
    		}
    		else
    		{
    			break;//跳出循环
    		}
    	}
    }
    
    void HeapSort(int* a, int n)
    {
    	//升序，建大堆，向上
    	size_t i = 0;
    	for (i = 1; i < n; ++i)
    	{
    		AdjustUp(a, i);
    	}
    }
    
    int main()
    {
    	int a[] = { 4, 3, 10 , 2, 5, 9 };
    	HeapSort(a, sizeof(a) / sizeof(int));
    	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    	return 0;
    }

代码2展示：

void HeapSort(int* a, int n)
    {
    	//升序，建堆，向上
    	/*int i = 0;
    	for (i = 1; i < n; ++i)
    	{
    		AdjustUp(a, i);
    	}*/
        //向下
    	int i = 0;
    	for (i = (n - 2) / 2; i >= 0; --i)
    	{
    		AdjustDown(a, i, n);
    	}
    }

建堆的时间复杂度：

**向上建堆**：首先每一层的节点数为2^(h-1);建堆是从第二层开始插入数据，第二层有2^(2-1)个节点，成为一个堆，向上调整的最坏次数为2^(2-1)\*1;第三层有2^(3-1)个节点，成为一个堆，向上调整的次数为2^(3-1)\*2;……；那么向上调整累积建堆次数为2^(2-1)\*1+2^(3-1)\*2+2^(4-1)\*3+……+2^(h-1)\*(h-1)。这是一个等差数列\*等比数列。利用错位相减，可以算出次数为2^h\*(h-2)+2； 最终时间复杂度为O(N\*logN)

**向下建堆**：首先每一层的节点数为2^(h-1);建堆是从（从倒数第一个非叶子节点开始）【这个非叶子节点不一定是倒数第二层的最后一个，但是此时可以把堆看做满级二叉树【两者的时间复杂度，差别不大】，那么此时的非叶子节点就是倒数第二层的最后一个】倒数第二层开始向下调整，一直到第一层向下调整结束，每一层有2^(h-1)个节点，每一个节点和下面部分成为一个堆，每个节点向下调整的最坏次数为2^(h-1)\*(h);那么向下调整累积建堆次数为2^0\*(h-1)+2^1\*(h-2)+2^2\*(h-2)+……+2^(h-2)\*1,这是一个等差数列\*等比数列。利用错位相减，可以算出次数为2^h-1-h,因为2^h-1=N,； 最终时间复杂度为O(N).。

> 总结：建堆最好用向下建堆

> 建堆：**升序建大堆，降序建小堆**。【如果升序建小堆，最小的数已经在第一个位置了，再次选出次小的，需要不断建堆选数。那么总的时间复杂度为O(N^2),既然这样，还不如直接遍历选数，时间复杂度也是O(N^2)】【升序应该建大堆】

#### **4.1.2 利用堆删除思想来进行排序** ####

> **升序，大堆为例**：建立大堆之后，最大值就在最前面，然后，最大值和最后一个值【下标为n-1】进行互换，然后不管n-1这个下标进行建堆，然后最大值再次与最后一个值进行【下标为n-2】进行互换。一直到下标为0的元素与下标为1的元素进行过交换，数组就完成了排序。【时间复杂度为：O（N\*logN）】

void HeapSort(int* a, int n)
    {
    	//升序，建堆，向上
    	/*int i = 0;
    	for (i = 1; i < n; ++i)
    	{
    		AdjustUp(a, i);
    	}*/
        //向下
    	int i = 0;
    	for (i = (n - 2) / 2; i >= 0; --i)
    	{
    		AdjustDown(a, i, n);
    	}
        size_t end = n - 1;
    	while (end > 0)
    	{
    		Swap(&a[0], &a[end]);
    		AdjustDown(a, 0, end);
    		--end;
    	}
    }

### 4.2 TOP-K问题 ###

N个数找出最大/最小的前K个

**TOP-K** **问题：即求数据结合中前** **K** **个最大的元素或者最小的元素，一般情况下数据量都比较大**。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能

数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. **用数据集合中前** **K** **个元素来建堆**

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

2. **用剩余的** **N-K** **个元素依次与堆顶元素来比较，不满足则替换堆顶元素**

将剩余N-K个元素 **依次**与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

> 时间复杂度为：O(K+logK\*(N-K));空间复杂度为：O(K).

void PrintTopK(int* a, int n, int k)
    {
    	// 建堆--用a中前k个元素建堆
    	int* kminHeap = (int*)malloc(sizeof(int) * k);
    	if (kminHeap == NULL)
    	{
    		printf("malloc fail \n");
    		exit(-1);
    	}
    	//前k个元素，放在数组里面
    	for (int i = 0; i < k; ++i)
    	{
    		kminHeap[i] = a[i];
    	}
    
    	// 建小堆
    	for (int j = (k - 2) / 2; j >= 0; --j)
    	{
    		AdjustDown(kminHeap, j, k);//k指的是下标，数组最后元素的下标，为了方便找到父节点
    	}
    
    	// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
    	for (int i = k; i < n; ++i)
    	{
    		if (a[i] > kminHeap[0])
    		{
    			kminHeap[0] = a[i];
    			AdjustDown(kminHeap, 0, k);
    		}
    	}
    
    	for (int j = 0; j < k; ++j)
    	{
    		printf("%d ", kminHeap[j]);
    	}
    	printf("\n");
    	free(kminHeap);
    }
    
    void TestTopk()
    {
    	int n = 10000;
    	int* a = (int*)malloc(sizeof(int) * n);
    	srand(time(0));
    	for (size_t 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[2305] = 1000000 + 6;
    	a[99] = 1000000 + 7;
    	a[76] = 1000000 + 8;
    	a[423] = 1000000 + 9;
    	a[0] = 1000000 + 1000;
    	PrintTopK(a, n, 10);
    }