二叉树-堆（补充）

二叉树-堆

  • 1.二叉树的基本特性
  • 2.堆
    • 2.1.堆的基本概念
    • 2.2.堆的实现
      • 2.2.1.基本结构
      • 2.2.2.堆的初始化
      • 2.2.3.堆的销毁
      • 2.2.4.堆的插入
      • 2.2.5.取出堆顶的数据
      • 2.2.6.堆的删除
      • 2.2.7.堆的判空
      • 2.2.8.堆的数据个数
      • 2.2.9.交换
      • 2.2.10.打印堆数据
      • 2.2.11.堆的创建
      • 2.2.12.堆排序
      • 2.2.13.完整代码
  • 3.Top-K问题

🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【数据结构的学习】
📝📝本篇内容：二叉树的基本特性；堆；堆的基本概念；堆的实现；堆的初始化；堆的销毁；堆的插入；取出堆顶的数据；堆的删除；堆的判空；堆的数据个数；交换；打印堆数据；堆的创建；堆排序；完整代码；Top-K问题
⬆⬆⬆⬆上一篇：二叉树（三）
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-

1.二叉树的基本特性

在这里插入图片描述
上图展示的就是二叉树，我将它的规律也写在上面了
一般我们把二叉树的高度设置从1开始，从0开始的话，空树就是-1，就不太合适了
一棵N个结点的树有N-1条边
假设二叉树的第k层是满的，它的结点数为2^(k-1)个
我们的二叉树还分为满二叉树和完全二叉树，下图展示了二者的对比图
在这里插入图片描述
满二叉树：一个二叉树，如果每一层的结点都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是2^k-1,则就是满二叉树。
完全二叉树：前N-1层是满的，最后一层可以不满，但是必须从左往右是连续的，满二叉树是一种特殊的完全二叉树。
我们先来分析一下满二叉树的特性：
假设满二叉树有k层，则它的最后一层的结点有2^(k-1)个
假设满二叉树有k层，一棵满二叉树一共有2^k-1个结点，计算方法如下：

在这里插入图片描述
其实还有一个小技巧：我们的二进制的每一位的值和二叉树的每一层的结点数相等的，假设我们的二进制为11111111，它是一个unsigned char类型的最大值，此时我们计算它的十进制就通过它的再高一位的值-1计算得出，即2^8-1=255。类比到二叉树，即下一层的结点数-1，设最后一层的结点个数为2 ^3，第4层，计算整棵二叉树的结点数为2 ^4-1。

设满二叉树的总结点数为N个，树的高度为log₂(N+1)，通过2^k-1=N计算可得
完全二叉树的特性：
设完全二叉树有k层，完全二叉树总共结点最少就是最后一层只有一个，即2^(k-1)个；最多也就是满二叉树，即2 ^k-1个结点

最多不用讲怎么计算了，最少可以用之前讲的错位相减法来计算，也可以二叉树的规律来算：假设完全二叉树一共k层；那么根据前面讲的，除去最后一层一个结点，它就是一棵满二叉树，共k-1层，根据满二叉树的总共结点公式，总结点数为2^ (k-1)-1个；那么再加上去掉的一个结点，完全二叉树的总结点数即为2^(k-1)个，如下图
在这里插入图片描述
对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n2=n0+1

2.堆

2.1.堆的基本概念

接下来讲的堆是二叉树的一种存储方式，从逻辑结构（想象的结构）上看我们的堆是一棵完全二叉树，从存储结构上看堆是数组
我们的堆还分为大根堆（大堆）和小根堆（小堆）
大堆：父结点大于等于孩子结点，并且子树也同样的，大堆的根结点在整个堆中是最大的元素
大堆：父结点小于等于孩子结点，并且子树也同样的，小堆的根结点在整个堆中是最小的元素
在这里插入图片描述
在这里插入图片描述
之所以我们我们的数组只能表示完全二叉树，是因为不是完全二叉树会有空间浪费，如下图
在这里插入图片描述
并且我们的堆是数组存储还有一个特性：
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
在这里插入图片描述

2.2.堆的实现

2.2.1.基本结构

//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型

typedef struct Heap
{
	T* arr;//堆的存储位置
	int size;//堆的数据个数
	int capacity;//堆的容量
}Heap;

void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空

void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
void AdjustDown(T* arr, int size, int parent);//向下调整

void HeapSort(int* arr,int n);//堆排序

上述代码已经将存储堆的结构体已经写好，同时把我们的堆的各种函数调用已经声明好了

2.2.2.堆的初始化

void HeapInit(Heap* heap)//堆的初始化
{
	assert(heap);
	heap->arr = NULL;
	heap->capacity = heap->size = 0;
}

我们这边的写法是一开始不给数组任何的空间，后期直接使用realloc开辟

2.2.3.堆的销毁

void HeapDestory(Heap* heap)//将堆销毁
{
	assert(heap);
	free(heap->arr);//释放空间
	heap->size = heap->capacity = 0;
}

不要忘记释放开辟的空间！！！

2.2.4.堆的插入

由于我们数组的特性，头插需要移动元素什么的，效率极低，但是可以尾插，所以说堆一般性就都是在尾部插入

//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{
	int parent = (child - 1) / 2;//找父结点
	//使用parent>=0有点不合理，倒数第二次运行循环时child已经是0了，应该结束
	//但是（child-1）/2导致parent依旧为0，再次进入循环，然后通过else中的break
	while (child>0)
	{
		//孩子结点大于父结点
		if (arr[child] > arr[parent])
		{
			//交换
			swap(&arr[child], &arr[parent]);
			//继续向上调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			//如果孩子结点小于父结点，就不用向上调整了
			break;
		}
	}
}

void HeapPush(Heap* heap, T x)//堆的插入
{
	assert(heap);
	//空间不足开辟内存
	if (heap->size == heap->capacity)
	{
		int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;
		//realloc的第一个元素是NULL的话，功能和malloc一样
		T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));

	if (newarr == NULL)
	{
		perror("realloc fail");
		exit(-1);
	}

		//修改已经开辟好空间后的信息
		heap->arr = newarr;//realloc可能不在原位扩容，所以说这一步是必要的
		heap->capacity = newcapacity;
	}

	//正式插入
	heap->arr[heap->size] = x;
	heap->size++;//数据个数+1
	
	//向上调整，保证是一个堆
	AdjustUp(heap->arr, heap->size - 1);
}

我们默认建立的是大堆哈，如果想要建立小堆，只需要将向上调整中的比较孩子结点和父结点的>变成<即可
在这里插入图片描述
代码和图片也展示在了上面，可以通过图片来理解一下，之所以这样写是因为我们在没有进行插入前，我们的结构肯定是堆的，但是插入后，我们需要进行调整才能保证堆的结构，我们写的是大堆，
因此需要和父结点进行比较，如果比父结点大，那么继续交换。但是由于交换后，可能还是比祖父结点大，也就还需要不停地调整。向上调整是对插入结点的祖先进行调整

2.2.5.取出堆顶的数据

T HeapTop(Heap* heap)//取出堆顶数据
{	
	assert(heap);
	assert(heap->size > 0);
	return heap->arr[0];
}

我们的可以用于Top-k问题，举个例子，我们在10000个人里面，选出最有钱的人，我们的堆就发挥了大用处，因为它的堆顶的数据，即数组第一个元素是最大（最小）的，我们只需要取出后，再删除就可以选出第二大的…第n大的，因此我们还需要来实现一下删除才能彻底理解

2.2.6.堆的删除

void AdjustDown(T* arr, int size,int parent)
{
	//选出左孩子和右孩子中较大的那个
	//假设较大的是左孩子
	int child = parent * 2 + 1;
	//孩子结点存在才向下调整
	while (child<size)
	{
		
		if (child + 1 < size && arr[child + 1] > arr[child])
		{
			//进行判断，如果右孩子大于左孩子，就+1，因为左孩子和右孩子之间就相差1
			child++;
		}
		
		//孩子结点大于父节点，就需要交换，保证大堆的特性
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			//继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			//如果孩子结点小于父结点，说明不需要调整了，跳出循环
			break;
		}
	}

}



void HeapPop(Heap* heap)//删除堆顶数据
{
	assert(heap);
	assert(heap->size>0);
	//先将堆顶的元素和最后一个元素进行交换
	swap(&heap->arr[0], &heap->arr[heap->size - 1]);
	//堆数据个数-1
	heap->size--;
	//向下调整
	AdjustDown(heap->arr,heap->size,0);
}

在这里插入图片描述
上面已经给出了代码和交换的图片，我们首先来讲一下为什么需要通过交换才能删除这个最大（最小）元素，究其原因还是它在根节点的原因，没有办法对它进行一个直接删除，一旦直接删除，就会导致整体的一个堆结构就乱掉了。我们根结点的左子树和右子树是堆，不能破坏它，那么最好的方法就是和尾元素进行交换，然后进行向下调整，这样不但保证了结构的完整性，效率还高。
向下调整如下图:
在这里插入图片描述

2.2.7.堆的判空

bool HeapEmpty(Heap* heap)//堆是否为空
{
	assert(heap);
	return heap->size == 0;
}

2.2.8.堆的数据个数

int HeapSize(Heap* heap)//堆的数据个数
{
	assert(heap);
	return heap->size;
}

2.2.9.交换

void swap(T* x, T* y)//交换
{
	T tmp = *x;
	*x = *y;
	*y = tmp;
}

2.2.10.打印堆数据

void HeapPrint(Heap* heap)//将堆数据打印出来
{
	for (int i = 0; i < heap->size; ++i)
	{
		printf("%d ", heap->arr[i]);
	}
	printf("\n");
}

2.2.11.堆的创建

//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{
	assert(heap);
	HeapInit(heap);
	for (int i = 0; i < n; i++)
	{
		HeapPush(heap, a[i]);
	}
}


void AdjustDown(T* arr, int size, int parent);//定义在下面，这边要使用，声明一下

void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{
	assert(heap);
	HeapInit(heap);
	//开辟空间
	heap->arr = (T*)malloc(sizeof(T) * n);
	if (heap->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//拷贝数据
	memcpy(heap->arr, a, n*sizeof(T));

	heap->size = heap->capacity = n;

	//从下至上进行向下调整
	for (int end = (n - 1 - 1) / 2; end >= 0; end--)
	{
		AdjustDown(heap->arr, n, end);
	}
}

在这里插入图片描述

上面展示了代码和图片，堆的创建我们用了两种方法，第一种就比较直接，循环push即可，但它的效率不是很高，于是我们有了第二种方法，想要保证一组毫无序列的元素变成堆，就需要保证每一个子树的父节点都大于（小于）孩子节点，因此我们只能从最后一棵子树开始向下调整（叶子结点不需要调整了），这样当调整到上一层时，下层都已经是堆了，只需要对当前节点也是向下调整即可。一直到根节点完成最后一次向下调整就可以完成堆的构建。
在代码中end两次-1，第一次-1是为了找到最后一个元素在数组中的位置，第二次-1是为了找到父结点。

2.2.12.堆排序

在我们讲述堆排序前，我们先来讨论一下，当我们对于一个随机的数组，将它变成一个堆，是使用向上调整好还是向下调整好呢？我们接下来分析一下
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
可以看到，向下调整和向上调整都能建堆，如果简单来看的话会认为向上调整的时间复杂度是都是O(N*logN)，而向下调整就有点难以看出来了，我们来计算一下
在这里插入图片描述
我们的向下调整在前面的代码中已经演示过了，它从最后一个结点的父结点开始调整，并且我们要验证它的时间复杂度就得使用最坏的情况，就是满二叉树。根据上图的详细计算可以得出向下调整的时间复杂度是O(N)
接下来再来看一下，向上调整的时间复杂度计算
在这里插入图片描述
上图为向上调整的计算过程，通过规律，我们很快就算了出来，可以发现向上调整的时间复杂度是O(N *log₂N)。其实我们仔细观察一下，可以发现我们的向上调整次数其实都是聚集在最后一层，最后一层不但结点是整棵二叉树中最多的，调整次数也是最多的；反观向下调整中，结点越是在上面，调整次数越多，但结点越少，反倒是最后一层，并没有进行调整，这就是造成两者时间复杂度差距的原因，因此我们在选择调整时，优先选择向下调整

void HeapSort(int* arr,int n)//堆排序
{
	//向上调整--O(N*logN)
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/


	//向下调整--O(N)
	for (int i =(n-1-1)/2; i>=0; i--)
	{
		AdjustDown(arr, n,i);
	}

	//堆排序-升序-使用大堆
	int end = n-1;
	while (end > 0)//当end==0时说明调整结束
	{
		swap(&arr[0],&arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}

}

在这里插入图片描述

接下来就可以看我们的堆排序的代码和图片，其中我们升序时需要使用大堆，降序时使用小堆，我们通过交换+向下调整，将数据依次从数组尾部开始放，这其实就是借鉴了我们的将堆内的top数据取出再pop的思想，并且我们的这个排序只需要写向下调整的代码即可，不需要完整的把堆代码写完。
我们可以看一下如果使用top+pop函数也能达到类似排序效果
在这里插入图片描述
在这里插入图片描述
我们接下来再看一下堆排序的时间复杂度
在这里插入图片描述
经过上面的分析，就可以知道一开始建堆向下调整的时间复杂度是O(N)，循环交换+向下调整的时间复杂度是O(N*log₂N)，那么根据时间复杂度的计算方式，堆排序的时间复杂度为O(N*log₂N)

2.2.13.完整代码

//Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
typedef int T;//堆数据类型

typedef struct Heap
{
	T* arr;//堆的存储位置
	int size;//堆的数据个数
	int capacity;//堆的容量
}Heap;

void HeapInit(Heap* heap);//堆的初始化
void HeapCreate1(Heap* heap, T* a, int n);//创建堆方法1
void HeapCreate2(Heap* heap, T* a, int n);//创建堆方法2
void HeapDestory(Heap* heap);//将堆销毁
void HeapPush(Heap* heap,T x);//堆的构建
void HeapPrint(Heap* heap);//将堆数据打印出来
T HeapTop(Heap* heap);//取出堆顶数据
void HeapPop(Heap* heap);//删除堆顶数据
int HeapSize(Heap* heap);//堆的数据个数
bool HeapEmpty(Heap* heap);//堆是否为空

void swap(T* x, T* y);//交换
void AdjustUp(T* arr, int child);//向上调整
void AdjustDown(T* arr, int size, int parent);//向下调整

void HeapSort(int* arr,int n);//堆排序

//Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapInit(Heap* heap)//堆的初始化
{
	assert(heap);
	heap->arr = NULL;
	heap->capacity = heap->size = 0;
}

//简单粗暴的一种方法
void HeapCreate1(Heap* heap, T* a, int n)//创建堆1
{
	assert(heap);
	HeapInit(heap);
	for (int i = 0; i < n; i++)
	{
		HeapPush(heap, a[i]);
	}
}


void AdjustDown(T* arr, int size, int parent);//定义在下面，这边要使用，声明一下

void HeapCreate2(Heap* heap, T* a, int n)//创建堆2
{
	assert(heap);
	HeapInit(heap);
	//开辟空间
	heap->arr = (T*)malloc(sizeof(T) * n);
	if (heap->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//拷贝数据
	memcpy(heap->arr, a, n*sizeof(T));

	heap->size = heap->capacity = n;

	//从下至上进行向下调整
	for (int end = (n - 1 - 1) / 2; end >= 0; end--)
	{
		AdjustDown(heap->arr, n, end);
	}
}



void HeapDestory(Heap* heap)//将堆销毁
{
	assert(heap);
	free(heap->arr);//释放空间
	heap->size = heap->capacity = 0;
}


void swap(T* x, T* y)//交换
{
	T tmp = *x;
	*x = *y;
	*y = tmp;
}

//我们默认建立大堆哈
void AdjustUp(T* arr,int child)//向上调整
{
	int parent = (child - 1) / 2;//找父结点
	//使用parent>=0有点不合理，倒数第二次运行循环时child已经是0了，应该结束
	//但是（child-1）/2导致parent依旧为0，再次进入循环，然后通过else中的break
	while (child>0)
	{
		//孩子结点大于父结点
		if (arr[child] > arr[parent])
		{
			//交换
			swap(&arr[child], &arr[parent]);
			//继续向上调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			//如果孩子结点小于父结点，就不用向上调整了
			break;
		}
	}
}

void HeapPush(Heap* heap, T x)//堆的插入
{
	assert(heap);
	//空间不足开辟内存
	if (heap->size == heap->capacity)
	{
		int newcapacity = heap->capacity == 0 ? 4 : heap->capacity * 2;
		//realloc的第一个元素是NULL的话，功能和malloc一样
		T* newarr = (T*)realloc(heap->arr, newcapacity*sizeof(T));

	if (newarr == NULL)
	{
		perror("realloc fail");
		exit(-1);
	}

		//修改已经开辟好空间后的信息
		heap->arr = newarr;//realloc可能不在原位扩容，所以说这一步是必要的
		heap->capacity = newcapacity;
	}

	//正式插入
	heap->arr[heap->size] = x;
	heap->size++;//数据个数+1
	
	//向上调整，保证是一个堆
	AdjustUp(heap->arr, heap->size - 1);
}

void HeapPrint(Heap* heap)//将堆数据打印出来
{
	for (int i = 0; i < heap->size; ++i)
	{
		printf("%d ", heap->arr[i]);
	}
	printf("\n");
}


T HeapTop(Heap* heap)//取出堆顶数据
{	
	assert(heap);
	assert(heap->size > 0);
	return heap->arr[0];
}

void AdjustDown(T* arr, int size,int parent)
{
	//选出左孩子和右孩子中较大的那个
	//假设较大的是左孩子
	int child = parent * 2 + 1;
	//孩子结点存在才向下调整
	while (child<size)
	{
		
		if (child + 1 < size && arr[child + 1] > arr[child])
		{
			//进行判断，如果右孩子大于左孩子，就+1，因为左孩子和右孩子之间就相差1
			child++;
		}
		
		//孩子结点大于父节点，就需要交换，保证大堆的特性
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			//继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			//如果孩子结点小于父结点，说明不需要调整了，跳出循环
			break;
		}
	}

}



void HeapPop(Heap* heap)//删除堆顶数据
{
	assert(heap);
	assert(heap->size>0);
	//先将堆顶的元素和最后一个元素进行交换
	swap(&heap->arr[0], &heap->arr[heap->size - 1]);
	//堆数据个数-1
	heap->size--;
	//向下调整
	AdjustDown(heap->arr,heap->size,0);
}


int HeapSize(Heap* heap)//堆的数据个数
{
	assert(heap);
	return heap->size;
}

bool HeapEmpty(Heap* heap)//堆是否为空
{
	assert(heap);
	return heap->size == 0;
}


void HeapSort(int* arr,int n)//堆排序
{
	//向上调整--O(N*logN)
	/*for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}*/


	//向下调整--O(N)
	for (int i =(n-1-1)/2; i>=0; i--)
	{
		AdjustDown(arr, n,i);
	}

	//堆排序-升序-使用大堆
	int end = n-1;
	while (end > 0)//当end==0时说明调整结束
	{
		swap(&arr[0],&arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}

}

//main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//验证Push能否正常工作
void Test1()
{
	Heap heap;
	HeapInit(&heap);
	int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	for (int i = 0; i < sizeof(array) / sizeof(T); i++)
	{
		HeapPush(&heap,array[i]);
	}
	HeapPrint(&heap);
}

//验证能否正常使用Pop并模拟排序
void Test2()
{
	Heap heap;
	HeapInit(&heap);
	int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	for (int i = 0; i < sizeof(array) / sizeof(T); i++)
	{
		HeapPush(&heap, array[i]);
	}
	HeapPrint(&heap);

	for (int i = 0; i < sizeof(array) / sizeof(T); i++)
	{	
		printf("%d ", HeapTop(&heap));
		HeapPop(&heap);
	}
	printf("\n");
}

//验证Create
void Test3()
{
	Heap heap;
	int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	HeapCreate2(&heap,array,sizeof(array)/sizeof(int));
	HeapPrint(&heap);
	for (int i = 0; i < sizeof(array) / sizeof(T); i++)
	{
		printf("%d ", HeapTop(&heap));
		HeapPop(&heap);
	}
	printf("\n");
}

//验证堆排序
void Test4()
{
	Heap heap;
	int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	HeapSort(array, sizeof(array) / sizeof(int));
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		printf("%d ", array[i]);
	}
}


int main()
{
	Test3();
	return 0;
}

3.Top-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
① 总共N个数据，用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
② 设求前K个最大的元素，建小堆，用剩余的N-K个元素依次与堆顶元素来比较，比堆顶大的就替换，然后进行向下调整
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

//Top-K问题
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(T* x, T* y)//交换
{
	T tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustDown(T* arr, int size, int parent)
{
	//选出左孩子和右孩子中较小的那个
	//假设较小的是左孩子
	int child = parent * 2 + 1;
	//孩子结点存在才向下调整
	while (child < size)
	{

		if (child + 1 < size && arr[child + 1] < arr[child])
		{
			//进行判断，如果右孩子小于左孩子，就+1，因为左孩子和右孩子之间就相差1
			child++;
		}

		//孩子结点小于父节点，就需要交换，保证小堆的特性
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			//继续向下调整
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			//如果孩子结点大于父结点，说明不需要调整了，跳出循环
			break;
		}
	}

}


int  main()
{
	int  k = 5;//求Top-10
	int n = 20;//数据数量


	srand((unsigned)time(NULL));
	//1.生成一堆随机数写入文件中
	//1.1打开文件
	FILE* fin = fopen("data.txt", "w");
	int flag = k;
	//1.2写入
	for (int i = 0; i < n; i++)
	{
		//i%3保证是随机添加，而不是连续，flag保证添加了k个
		if (i % 3 == 0 && flag-- > 0)
		{
			//1.3方便测试，添加几个大于等于10000的数据
			fprintf(fin, "%d\n", 10000+i);
		}
		else
		{
			fprintf(fin, "%d\n", rand() % 10000);
		}
	}

	//1.4关闭文件
	fclose(fin);

	//2.建立小堆
	//2.1开辟空间
	
	int* array = (int*)malloc(sizeof(int) * k);

	//2.2向下调整
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(array, n, i);
	}

	//3.用剩余的N-K个元素依次与堆顶元素来比较，比堆顶大的就替换，然后进行向下调整
	//3.1打开文件
	FILE* fout = fopen("data.txt", "r");
	//3.2从文件读取
	int value = 0;
	while (fscanf(fout, "%d", &value) != EOF)
	{
		//3.3和堆顶进行比较
		if (array[0] < value)
		{
			array[0] = value;
			//3.4向下调整
			AdjustDown(array, k, 0);
		}
	}
	//3.4关闭文件
	fclose(fout);


	//4.验证结果
	//10000 10006 10003 10009 10012
	for (int i = 0; i < k; i++)
	{
		printf("%d ", array[i]);
	}
	printf("\n");

	return 0;
}

它的时间复杂度的计算过程：前面讲的向下调整的建堆过程的时间复杂度是O(N)，N是结点个数，那么代入到这，K也是结点个数(数组大小)，那么建堆过程的复杂度为O(K);还需要比较+向下调整，堆的大小是K，需要调整次数为log₂K-1(-1不包含自己层，并且这里的log₂K是比较精确的，不像前面排序会改变end，导致每次调整时间复杂度逐渐减小)，时间复杂度是O(log₂K)，需要比较N-K次，那么总的时间复杂度就是(N-K) * log₂K。综上所述，K+(N-K) * log₂K=>Top-K时间复杂度为O(N*log₂K)，空间复杂度是O(K)，这个空间K是存放堆的数据的
假设有100亿整数的数据，找Top10，那么就需要100亿*4byte=400亿byte=40G(1G=1024 *1024 *1024byte≈10亿byte)，对于现在的电脑来说40G还是不现实，如果以后真有了，就可以建立一个N个数的大堆，Pop个K次，依次取堆顶，那么它的时间复杂度就为O(N+log₂N *K)， 建堆需要O(N)，K个数据需要向下调整log₂N，这其实和堆排序的时间复杂度计算方式差不多，只是向下调整K次和全部调整的区别。
其实如果真的能够实现40G的内存的话，两个的时间复杂度差不多，O(N *log₂K)忽略log₂K，O(N+log₂N *K)忽略log₂N *K，都是O(N)，在N这个大数量级上其实也是可以忽略的！

🌸🌸二叉树-堆的知识大概就讲到这里啦，博主后续会继续更新更多数据结构的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/961571.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

JVM01_概述、跨平台原理、分类、三大商业虚拟机

JVM01_概述、跨平台原理、分类、三大商业虚拟机

①. 什么是JVM&#xff1f; ①. JVM 是 java虚拟机&#xff0c;是用来执行java字节码(二进制的形式)的虚拟计算机 ②. jvm是运行在操作系统之上的&#xff0c;与硬件没有任何关系 ②. Java的跨平台及原理 ①. 跨平台&#xff1a;由Java编写的程序可以在不同的操作系统上运行&am…
阅读更多...
实现基础的shell程序

实现基础的shell程序

1. 实现一个基础的 shell 程序&#xff0c;主要完成两个命令的功能 cp 和 ls 1.1.1. cp 命令主要实现&#xff1a; ⽂件复制⽬录复制 1.1.2. ls 命令主要实现&#xff1a; ls -l 命令的功能 1.1. 在框架设计上&#xff0c;采⽤模块化设计思想&#xff0c;并具备⼀定的可扩…
阅读更多...
idea修改模块名导致程序编译出错

idea修改模块名导致程序编译出错

本文简单描述分别用Idea菜单、pom.xml文件管理项目模块module 踩过的坑&#xff1a; 通过idea菜单创建模块&#xff0c;并用idea菜单修改模块名&#xff0c;结构程序编译报错&#xff0c;出错的代码莫名奇妙。双击maven弹窗clean时&#xff0c;还是报错。因为模块是新建的&am…
阅读更多...
C27.【C++ Cont】时间、空间限制和STL库的简单了解

C27.【C++ Cont】时间、空间限制和STL库的简单了解

&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;春节篇&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8;&#x1f9e8; 目录 1.竞赛中的…
阅读更多...
ResNet 残差网络

ResNet 残差网络

目录 网络结构 残差块&#xff08;Residual Block&#xff09; ResNet网络结构示意图 残差块&#xff08;Residual Block&#xff09;细节 基本残差块&#xff08;ResNet-18/34&#xff09; Bottleneck残差块&#xff08;ResNet-50/101/152&#xff09; 残差连接类型对比 变体网…
阅读更多...
组件框架漏洞

组件框架漏洞

一.基础概念 1.组件 定义&#xff1a;组件是软件开发中具有特定功能或特性的可重用部件或模块&#xff0c;能独立使用或集成到更大系统。 类型 前端 UI 组件&#xff1a;像按钮、下拉菜单、导航栏等&#xff0c;负责构建用户界面&#xff0c;提升用户交互体验。例如在电商 AP…
阅读更多...
电脑无法开机，重装系统后没有驱动且驱动安装失败

电脑无法开机，重装系统后没有驱动且驱动安装失败

电脑无法开机&#xff0c;重装系统后没有驱动且驱动安装失败 前几天电脑突然坏了&#xff0c;电脑卡住后&#xff0c;强制关机&#xff0c;再开机后开机马上就关机。尝试无数次开机后失败&#xff0c;进入BIOS界面&#xff0c;发现已经没有Windows系统了。重新安装系统后&…
阅读更多...
NLP自然语言处理通识

NLP自然语言处理通识

目录 ELMO 一、ELMo的核心设计理念 1. 静态词向量的局限性 2. 动态上下文嵌入的核心思想 3. 层次化特征提取 二、ELMo的模型结构与技术逻辑 1. 双向语言模型&#xff08;BiLM&#xff09; 2. 多层LSTM的层次化表示 三、ELMo的运行过程 1. 预训练阶段 2. 下游任务微调 四、ELMo的…
阅读更多...
二进制安卓清单 binary AndroidManifest - XCTF apk 逆向-2

二进制安卓清单 binary AndroidManifest - XCTF apk 逆向-2

XCTF 的 apk 逆向-2 题目 wp&#xff0c;这是一道反编译对抗题。 题目背景 AndroidManifest.xml 在开发时是文本 xml&#xff0c;在编译时会被 aapt 编译打包成为 binary xml。具体的格式可以参考稀土掘金 MindMac 做的类图&#xff08;2014&#xff09;&#xff0c;下面的博…
阅读更多...
Mac Electron 应用签名（signature）和公证（notarization）

Mac Electron 应用签名（signature）和公证（notarization）

在MacOS 10.14.5之后&#xff0c;如果应用没有在苹果官方平台进行公证notarization(我们可以理解为安装包需要审核&#xff0c;来判断是否存在病毒)&#xff0c;那么就不能被安装。当然现在很多人的解决方案都是使用sudo spctl --master-disable&#xff0c;取消验证模式&#…
阅读更多...
stack 和 queue容器的介绍和使用

stack 和 queue容器的介绍和使用

1.stack的介绍 1.1stack容器的介绍 stack容器的基本特征和功能我们在数据结构篇就已经详细介绍了&#xff0c;还不了解的uu&#xff0c; 可以移步去看这篇博客哟&#xff1a; 数据结构-栈数据结构-队列 简单回顾一下&#xff0c;重要的概念其实就是后进先出&#xff0c;栈在…
阅读更多...
【Rust自学】15.0. 智能指针(序)：什么是智能指针及Rust智能指针的特性

【Rust自学】15.0. 智能指针(序)：什么是智能指针及Rust智能指针的特性

喜欢的话别忘了点赞、收藏加关注哦&#xff0c;对接下来的教程有兴趣的可以关注专栏。谢谢喵&#xff01;(&#xff65;ω&#xff65;) 15.0.1 指针的基本概念 指针是一个变量在内存中包含的是一个地址&#xff0c;指向另一个数据。 Rust 中最常见的指针是引用&#xff0c…
阅读更多...
单调栈算法

单调栈算法

文章目录 题目概述题目详解739.每日温度1475.商品折扣后的最终价格84.柱状图中最大的矩形 题目概述 单调栈&#xff1a;栈&#xff0c;并且栈是有序的 单调栈的两种写法&#xff1a; 左 -> 右&#xff0c;或者右 -> 左 建议使用左到右的写法 及时去掉无用元素&#xff0c…
阅读更多...
vue-有关于TS与路由器

vue-有关于TS与路由器

title: vue(TS)路由器 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端Vue3-第二部分 这里是代码中出现TS的&#xff0c;后面是路由器 现在先上代码&#xff0c;步步分析。 eg1-props的使用 步步分析代码&#xff08;先理解&#xff0c;再实践&#xff09; 框架…
阅读更多...
【AI编辑器】字节跳动推出AI IDE——Trae，专为中文开发者深度定制

【AI编辑器】字节跳动推出AI IDE——Trae，专为中文开发者深度定制

目录 一、背景 二、核心特性 2.1 AI驱动的代码自动生成 2.2 智能问答与代码补全 2.3 多语言支持 2.4 插件与扩展 三、架构 四、下载使用 4.1 下载与安装 4.2 界面与配置 五、应用实践 5.1 快速生成代码 5.2 智能问答与调试 5.3 团队协作与代码审查 六、与Cursor…
阅读更多...
(done) ABI 相关知识补充：内核线程切换、用户线程切换、用户内核切换需要保存哪些寄存器？

(done) ABI 相关知识补充：内核线程切换、用户线程切换、用户内核切换需要保存哪些寄存器？

由于操作系统和编译器约定了 ABI&#xff0c;如下&#xff1a; 编译器在对 C 语言编译时&#xff0c;会自动 caller 标注的寄存器进行保存恢复。保存的步骤通常发生在进入函数的时候&#xff0c;恢复的步骤通常发生在从函数返回的时候。 内核线程切换需要保存的寄存器&#…
阅读更多...
把本地搭建的hexo博客部署到自己的服务器上

把本地搭建的hexo博客部署到自己的服务器上

配置远程服务器的git 安装git 安装依赖工具包 yum install -y curl-devel expat-devel gettext-devel openssl-devel zlib-devel安装编译工具 yum install -y gcc perl-ExtUtils-MakeMaker package下载git&#xff0c;也可以去官网下载了传到服务器上 wget https://www.ke…
阅读更多...
71-《颠茄》

71-《颠茄》

颠茄 颠茄&#xff0c;别名&#xff1a;野山茄、美女草、别拉多娜草&#xff0c;拉丁文名&#xff1a;Atropa belladonna L.是双子叶植物纲、茄科、颠茄属多年生草本&#xff0c;或因栽培为一年生&#xff0c;根粗壮&#xff0c;圆柱形。茎下部单一&#xff0c;带紫色&#xff…
阅读更多...
二次封装的方法

二次封装的方法

二次封装 我们开发中经常需要封装一些第三方组件&#xff0c;那么父组件应该怎么传值&#xff0c;怎么调用封装好的组件原有的属性、插槽、方法&#xff0c;一个个调用虽然可行&#xff0c;但十分麻烦&#xff0c;我们一起来看更简便的方法。 二次封装组件&#xff0c;属性怎…
阅读更多...
计算机组成原理（2）王道学习笔记

计算机组成原理（2）王道学习笔记

数据的表示和运算 提问&#xff1a;1.数据如何在计算机中表示&#xff1f; 2.运算器如何实现数据的算术、逻辑运算&#xff1f; 十进制计数法 古印度人发明了阿拉伯数字&#xff1a;0&#xff0c;1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6&#…
阅读更多...
最新文章

Copyright @ 2022~2023