【数据结构】--- 深入剖析二叉树（中篇）--- 认识堆&&堆排序&&Topk

 Welcome to 9ilk's Code World

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏：     数据结构之旅 

文章目录

🏠 初识堆

📒 堆的概念

📒 堆的性质

🏠 向上调整算法 && 向下调整算法

📒 向上调整算法

📒 向下调整算法

📒 向上调整 vs 向下调整

🏠 堆的应用场景

📒 堆排序

📒 Top K问题

上篇我们讲解了树以及二叉树，相信小伙伴们对二叉树有了初步的了解，本篇文章我们来了解下由二叉树延伸出来的堆以及堆排序，Top K问题。

🏠 初识堆

     我们知道二叉树的顺序结构适合于完全二叉树和满二叉树，而我们今天的主角堆也是个完全二叉树，因此它也是使用顺序结构的数组来存储

📒 堆的概念

堆的概念（来自度娘）：

⚠️

• 我们这里的堆是一种数据结构，而操作系统虚拟进程地址空间的堆区是操作系统中管理内存的一块区域分段。
• 堆分为大堆和小堆。大堆指的是双亲结点的值域大于孩子结点，小堆指的是双亲结点的值域小于孩子结点。
• 堆只规定了孩子和双亲的关系，并未规定兄弟间的大小关系
• 堆在物理层面是数组，逻辑结构上是二叉树。

📒 堆的性质

• 堆中某个节点的值总是不大于或不小于其父节点的值
   
• 堆总是一棵完全二叉树
   

🏠 向上调整算法 && 向下调整算法

对于这样的一个小堆，我们要插入2这个数据，此时不满足小堆的要求，若要调整可能会影响祖先，那有什么方法能解决这个问题呢？这里就要介绍一个新的算法 --- 向上调整算法

📒 向上调整算法

我们先上个动图来感受下 ~ 

我们可以看到这个过程是针对某个结点而言的，若要满足小堆，依次拿这个结点向上与它的祖先比较，如果它比祖先小就交换，直到小于它的某个祖先或交换到根结点的位置。

⚠️  向上调整算法只能帮助我们使根结点的值域最小，而不能保证所有其他结点的大小关系！

• 代码分析及实现

1.首先需要实现一个交换数组数据的Swap函数

2.如何找某个结点child的祖先parent，这里就要用到我们上节的知识：parent =(child - 1)/ 2;

3.何时不交换：当小于它的某个祖先时或交换到根结点的位置（child>0）

void Swap(Datatype& x,Datatype& y)
{
      Datatype temp = x;
                  x = y;
                  y = temp;
}

void AdjustDown(int* arr,int child)
{
        int parent = (child - 1) / 2;//双亲结点
        while(child > 0)
        {
              if(arr[child] < arr[parent])
              {
                  Swap(arr[child],arr[parent]);
                  child = parent;//更新孩子和双亲
                  parent = (parent-1)/2;     
              }
              else
               {
                    break;
               }
        }
}

• 利用向上调整算法建堆

假设已知数组a[ ] = {1,5,3,8,7,6}，如何把它建成一个大堆呢？这里就可以用到我们的向上调整算法。

整个过程就是，我们每次向新数组插入数据时，采用向上调整算法进行调整。

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

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 = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		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);
}

int main()
{
    int arr[] = {1,5,3,8,7,6};
    HP hp;
    HPInit(&hp);
    for(int i = 0; i < sizeof(arr)/sizeof(arr[0]);i++)
     {
          HPPush(&hp,arr[i]);
     } 
    return 0;
}

📒 向下调整算法

对于这样的一个小堆我们要删除堆顶数据10，应该怎么删呢？有的小伙伴认为直接循环覆盖不就行了，但这样做会出现两个问题：1.挪动覆盖时间复杂度是O(N) 2.堆结构破坏，父子兄弟间关系乱套。有什么解决方法呢？我们可以采取这样的一个方法

1.首尾（根结点和最后一个叶子结点）交换数据，删除尾部数据

2.对根结点采用向下调整算法恢复堆的结构

我们上动图 ~ 

由动图我们可以知道，向下调整大致是这样的一个流程：若要保证是小堆，先找出左右孩子中较小的那一个，如果调整节点比较小的那个要大，就两者交换。

• 向下调整代码分析及实现

1.需要一个交换函数

2.选出左右孩子较小的那个（假设小堆），同时要保证有右孩子！

3.调整后的更新 parent = child; child = 2*child + 1;

4.调整结束条件：调整结点比较小孩子结点小 或 调整到二叉树最后一层(child < n)

void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (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;
		}
	}
}

• 利用向下调整算法实现删除堆顶数据

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);//首尾交换
	php->size--;//删除尾部数据

	AdjustDown(php->a, php->size, 0);//向下调整
}

• 利用向下调整建堆

利用向下调整建堆我们需要从倒数第一个非叶子结点开始，这与向上调整调整有所不同

从倒数第一个非叶子结点开始的原因：

1. 向下调整的前提是结点的左右子树都是堆

如上图若要建小堆，27的右子树是小堆，但左子树不是小堆，若向下调整，会使原本应为根节点的15被忽视。

2.从倒数第一个非叶子结点开始的话，就可以先调整每个子树为小堆或大堆

动图 part ~

• 代码分析以及实现

我们需要确定倒数第一个非叶子结点。

1.最后一个叶子结点下标为n-1

2.倒数第一个非叶子结点即为最后一个叶子结点的父亲

3.由于parent = (child - 1) / 2 , 因此倒数第一个非叶子结点下标为（n-1-1）/ 2

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;

	// 向下调整
	for (int i = (php->size-1 - 1)/2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

📒 向上调整 vs 向下调整

• 时间复杂度 ：向上调整 vs 向下调整

由于时间复杂度要考虑最坏的情况，所以二叉树中的结点最坏调整高度次，因此Push操作或向上调整算法的时间复杂度是O(logN);而对于Pop操作，我们一次向下调整最坏是从根结点开始调整，最坏要调整高度h次，因此Pop操作或向下调整算法的时间复杂度是O(logN)

结论： 

1.完全二叉树Pop和Push操作的时间复杂度都是O(logN)

2.向上调整算法和向下调整算法的时间复杂度都是O(logN)

向下调整和向上调整都是O(logN)，我们是不是可以随意用呢？别急，我们分析建堆层面 ~ 

• 时间复杂度： 向上调整建堆 vs 向下调整建堆

向上调整建堆

假设在最坏情况下，设树的高度为h,累计调整次数为f(h)，f(h)为每个结点调整次数之和，由于每一层结点个数为2^(i-1),则有：

         f(h) = (2^1)*1 + (2^2)*2 + (2^3)*3 +... + (2^(h-1))*(h-1);

---> 2f(h) = (2^2)*1 + (2^3)*2 + (2^4)*3 +... + (2^(h-1))*(h-2) + (2^(h)*(h-1));

--->错位相减得  f(h) = (2^h)*(h-2)+2     (1)

由于 2^(h) - 1 = N -->  h = log(N + 1)    (2)

联立（1)  (2) 得  f(N) =  (N+1)(log(N+1) - 2) + 2 

由f(N)得   向上调整建堆的时间复杂度为O(N*logN)

向下调整建堆

假设在最坏情况下，设树的高度为h,累计调整次数为f(h)，f(h)为每个结点调整次数之和，由于每一层结点个数为2^(i-1),则有：

         f(h) = (2^(h-2))*1 + (2^(h-3))*2 + (2^(h-4))*3 + ... + (2^0)*(h-1)

---> 2f(h) = (2^(h-1))*1 + (2^(h-2))*2 + (2^(h-3))*3 + ... + (2^0)*(h-2) + (2^0)*(h-1)

--->错位相减得  f(h) =  2^(h) + h - 2;   (1)

由于 2^(h) - 1 = N -->  h = log(N + 1)    (2)

联立（1)  (2)  得  f(N) = N + 1 + log(N+1) - 2;

由f(N)得  向上调整建堆的时间复杂度为O(N)

不同算法建堆差异的原因

我们发现向下调整建堆的时间复杂度小于向上调整建堆，效率较高，原因在于完全二叉树层数越大，该层结点数越多，而向下调整是先对倒数第一层的结点（可以说集合了这颗树的大部分结点）开始调整，且调整次数只有1次，也就是说向下调整对结点调整次数是多 x 少，对大部分结点的调整次数少 ；而向上调整建堆是从根结点开始调整，可以说是多 x 多，对大部分结点调整次数多。

因此对同样时间复杂度的算法，采用向下调整建堆的方法效率更高一些！

🏠 堆的应用场景​​​​​​​

对于堆，我们主要有两个应用场景堆排序和Top K问题

📒 堆排序

• 第一种堆排序

我们前面实现了Pop操作，同时我们知道向上调整或算法可以使根结点为最大或最小，因此我们可以先对数组初始化建小堆，此时若要升序根节点值就是最小的再不断Pop操作就能实现排序

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);
	
	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;

	for (int i = (php->size-1 - 1)/2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}


bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

void HeapSort(int* a, int n)
{
	HP hp;
	HPInitArray(&hp, a, n); //初始化堆
	int i = 0;
	while (!HPEmpty(&hp))
	{
		a[i++] = HPTop(&hp);//取堆顶数据
		HPPop(&hp);//删除数据
	}
	HPDestroy(&hp);
}

对于这种堆排序思路比较简单容易理解，但是存在两个问题：1.需要我们自己实现一个堆的数据结构 2.调用HpInitArray()，空间复杂度为O(N)

• 第二种堆排序

若我们跟第一种堆排序一样升序建小堆而不申请空间原地操作，会有什么问题？

答案是这样我们虽然能得到最小的，但要得到次小的，要重新建堆O(N),重复下来整个过程的时间复杂度是N + N -1 + N - 2 + ... + 1 --> O(N^2) 这个效率是大大不行的，有什么解决之法？那我们就反着来，升序建大堆看看 ~ 

大概流程是：

1.若要升序初始化建大堆

2.首尾交换数据，缩小范围

3.向下调整根结点 循环往复（2）(3) 直到范围缩小为0

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (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;
		}
	}
}

void HeapSort(int* a, int n)
{
	// a数组直接建堆 O(N)
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

这种堆排序主要是升序建大堆，再利用堆删除数据的思想，时间复杂度是O(NlogN)

📒 Top K问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决。

基本思路如下：

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

要前k个最大的元素，则先对前k个元素建小堆；要前k个最小的元素，则先对前k个数据建大堆

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

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

说明：若要前k个最大，建小堆就能保证前k大的能通过向下调整沉进这个“三角形”里,同时前k大之外的数据能不断被剔除出去，因为会往上“浮动”

void topk()
{
	printf("请输入k：>");
	int k = 0;
	scanf("%d", &k);

	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
     //申请空间准备建堆
	int val = 0;
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc error");
		return;
	}
    
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
	}

	// 建k个数据的小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minheap, k, i);
	}
    //判断调整
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，比堆顶的值大，就替换他进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}

	fclose(fout);

}

本次分享到这里就结束啦，下篇我们将讲解二叉树结构及其遍历和相关oj题，记得三连呀 ~