4 条题解

  • 3
    @ 2023-5-23 21:29:07

    ……

    这道题好像不太会,代码总有问题那就简简单单的讲下堆吧😄

    1.堆的原理精讲 image

    最大堆特点：

    image

    当然，也有最小堆，最小堆就是将最大堆反过来，根结点为最小值~

    image

    堆是树中最有个性的树，他是用数组表示的树 。

    image

    2.在数组中快速创建堆

    image

    1.首先我们需要找到最后一个结点的父结点如图(a),我们找到的结点是 87，然后找出该结点的最大子节点与自己比较，若该子节点比自身大，则将两个结点交换。 图(a)中，87 比左子节点 95 小,则交换之。如图(b)所示

    image

    2.我们移动到第一步前一个父节点 93，如图(c)所示.同理做第一步的比较操作，结果不需要交换。

    image

    3.继续移动结点到前一个父结点 82,如图(d)所示,82 小于右子节点 95，则 82 与 95 交换,如图(e)所示，82 交换后，其值小于左子节点，不符合最大堆的特点，故需要继续向下调整，如图(f)所示。

    image

    4.所有节点交换完毕,最大堆构建完成~

    3.堆的算法实现 堆数据结构的定义：

    #define DEFAULT_CAPACITY 128
typedef struct _Heap {
	int* arr;		//存储堆元素的数组
	int size;		//当前已存储的元素个数
	int capacity;	//当前的存储容量
}Heap;

    建立最大堆算法： ​

    bool initHeap(Heap& heap, int* original, int size);
static void buildHeap(Heap& heap);
static void adjustDown(Heap& heap, int index);
 
//初始化堆
bool initHeap(Heap& heap, int* original, int size) {
	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
	heap.arr = new int[capacity];
	if (!heap.arr)return false;
	heap.capacity = capacity;
	heap.size = 0;
	//如果存在原始数据，则拷贝过来
	if (size > 0) {
		memcpy(heap.arr, original, size * sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}
	return true;
}
 
/*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
整体上形成一个最大堆*/
void buildHeap(Heap& heap) {
	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
		adjustDown(heap, i);
	}
}
 
void adjustDown(Heap& heap, int index) {
	int cur = heap.arr[index];  //记录父节点值
	int parent, child;
 
	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
	调整*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
		child = parent * 2 + 1; //左子节点
 
		//取两个子节点最大结点
		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
			child++;
		}
		if (cur >= heap.arr[child])break;//不大于，跳出循环
		else {
			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
			即for从第二次循环开始，初始值都为上一次的子节点位置*/
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}
	}
}

    完成测试代码 ：

    int main() {
 
	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
 
	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}
 
	for (int i = 0; i < hp.size; i++) {
		cout << hp.arr[i] << endl;
	}
	system("pause");
	return 0;
}

    image

    知识点补充： 1.memcpy(内存拷贝函数) memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。用于double、int、结构体等 double arryDouble_Src[16]; double arryDouble_Det[16];

    memcpy( arryDouble_Det, arryDouble_Src, sizeof(double)*16); int arryInt_Src[16]; int arryInt_Dst[16]; memcpy(arryInt_Dst,arryInt_Src,sizeof(int)*16);

    struct DataNum
{
int Data0;
int Data1;
}

DataNum arryStruct_Src[16];
DataNum arryStruct_Dst[16];

    memcpy( arryStruct_Dst, arryStruct_Src, sizeof(DataNum )*16);

    2. 在一般的函数前面加上static

    加了static后表示该函数失去了全局可见性，只在该函数所在作用域内可见。

    当函数声明为static以后，编译器在该目标编译单元内只含有该函数入口地址，没有函数名，其它编译器便不能通过该函数名调用该函数。

    4.插入元素 与弹出最大元素 4.1插入元素 将数字99插入到下面最大堆中

    image

    对应的数组：{95, 93, 87, 92, 86, 82}

    将新进的元素插入到大顶堆的尾部,如下图 b 所示:

    image

    对应的数组：{95, 93, 87, 92, 86, 82, 99}

    此时最大堆已经被破坏，需要重新调整, 因加入的节点比父节点大，则新节点跟父节点调换即可,如图 c所示；调整后，新节点如果比新的父节点小，则已经调整到位，如果比新的父节点大，则需要和父节点重新进行交换，如图 d, 至此，最大堆调整完成。

    image

    static bool insertHeap(Heap& heap, int value);
static void adjustUp(Heap& heap, int index);
 
bool insertHeap(Heap& heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "栈空间耗尽!\n");
		return false;
	}
 
	int index = heap.size;
	heap.arr[heap.size++] = value;//先赋值value，再size++
	adjustUp(heap, index);
}
 
void adjustUp(Heap& heap, int index) {
	if (index < 0 || index >= heap.size) {
		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
		return;
	}
	int temp = heap.arr[index];//temp为插入的值
	while (index > 0) {
		
		int parent = (index - 1) / 2;
		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
			if (heap.arr[parent] < temp) {
				heap.arr[index] = heap.arr[parent];
				heap.arr[parent] = temp;
				index = parent;
			}
			else break;    //如果没有比父结点大，则跳出
		}
		else break;  //越界，结束循环
	}
}

    完成测试代码 ：

    int main() {
 
	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
 
	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}
 
	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}
 
	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}
	system("pause");
	return 0;
}

    image

    当实现了插入功能后，对于堆的初始建立就有了两种方法。第一种就是直接将数组传入，第二种则是将元素一个个插入。相比较而言，对于一个个插入的方法比较次数更少，效率更高~

    4.2弹出最大元素

    ​ 如果我们将堆顶的元素删除，那么顶部有一个空的节点，怎么处理？

    当插入节点的时候，我们将新的值插入数组的尾部。现在我们来做相反的事情：我们取出数组中的最后一个元素​，将它​放到堆的顶部​，然后再修复堆属性。

    static bool popMax(Heap& heap, int& value);
bool popMax(Heap& heap, int& value) {
	if (heap.size < 1)return false;
	value = heap.arr[0];
 
	//将size-1的位置值赋给根节点，size本身又--
	/*相当于
		heap.arr[0] = heap.arr[heap.size-1];
		heap.size--;
	*/
	heap.arr[0] = heap.arr[--heap.size];
	adjustDown(heap, 0);  //向下执行堆调整
	return true;
}

    完成测试代码 ：

    int main() {
 
	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
 
	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}
 
	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}
 
	/*向堆中插入元素
	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}*/
 
	int value;
	while (popMax(hp, value)) {
		cout << "依次出列最大元素：" << value << endl;
	}	
	
	system("pause");
	return 0;
}

    image

    使用堆方法依次弹出最大值，执行效率高于冒泡排序~

    5.堆的实际开发应用案例 5.1优先队列 操作系统内核作业调度是优先队列的一个应用实例，它根据优先级的高低而不是先到先服务的方式来进行调度；

    image

    如果最小键值元素拥有最高的优先级，那么这种优先队列叫作 升序优先队列（即总是先删除最小的元素），类似的，如果最大键值元素拥有最高的优先级，那么这种优先队列叫作 降序优先队列（即总是先删除最大的元素）；由于这两种类型是完全对称的，所以只需要关注其中一种，如升序优先队列。

    5.2堆排序

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。

    (选择排序工作原理 -——第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零)

    核心排序如下：

    image

    image

    6.堆实现及其功能完整代码

    #include<iostream>
using namespace std;
 
#define DEFAULT_CAPACITY 128
typedef struct _Heap {
	int* arr;		//存储堆元素的数组
	int size;		//当前已存储的元素个数
	int capacity;	//当前的存储容量
}Heap;
 
 
bool initHeap(Heap& heap, int* original, int size);
static void buildHeap(Heap& heap);
static void adjustDown(Heap& heap, int index);
static bool insertHeap(Heap& heap, int value);
static void adjustUp(Heap& heap, int index);
static bool popMax(Heap& heap, int& value);
 
//初始化堆
bool initHeap(Heap& heap, int* original, int size) {
	//如果默认大小比size小，则申请默认大小的空间，否则申请size大小的空间
	int capacity = DEFAULT_CAPACITY > size ? DEFAULT_CAPACITY : size;
	heap.arr = new int[capacity];
	if (!heap.arr)return false;
	heap.capacity = capacity;
	heap.size = 0;
	//如果存在原始数据，则拷贝过来
	if (size > 0) {
		memcpy(heap.arr, original, size * sizeof(int));
		heap.size = size;
		buildHeap(heap);
	}
	return true;
}
 
/*从最后一个父节点开始（heap.size) - 1 / 2）（因为size是从1开始，所以要先减去1）
逐个调整所有的父节点（直到根节点），确保每一个父节点都是最大堆，最后
整体上形成一个最大堆*/
void buildHeap(Heap& heap) {
	for (int i = (heap.size - 1) / 2; i >= 0; i--) {
		adjustDown(heap, i);
	}
}
 
void adjustDown(Heap& heap, int index) {
	int cur = heap.arr[index];  //记录父节点值
	int parent, child;
 
	/*怕段是否存在大于当前结点的子节点，如果不存在，则堆本身平衡，不需要
	调整，如果存在，则将最大子节点与之交换，交换后，如果这个子节点还有
	子节点（即parent*2+1<heap.size 成立）则要按照相同步骤对这个子节点进行
	调整*/
	for (parent = index; (parent * 2 + 1) < heap.size; parent = child) {
		child = parent * 2 + 1; //左子节点
 
		//取两个子节点最大结点
		if (((child + 1) < heap.size) && (heap.arr[child + 1] > heap.arr[child])) {
			child++;
		}
		if (cur >= heap.arr[child])break;//不大于，跳出循环
		else {
			/*大于当前父节点，进行交换，然后从子节点位置继续向下调整，
			即for从第二次循环开始，初始值都为上一次的子节点位置*/
			heap.arr[parent] = heap.arr[child];
			heap.arr[child] = cur;
		}
	}
}
static bool popMax(Heap& heap, int& value);
bool popMax(Heap& heap, int& value) {
	if (heap.size < 1)return false;
	value = heap.arr[0];
 
	//将size-1的位置值赋给根节点，size本身又--
	/*相当于
		heap.arr[0] = heap.arr[heap.size-1];
		heap.size--;
	*/
	heap.arr[0] = heap.arr[--heap.size];
	adjustDown(heap, 0);  //向下执行堆调整
	return true;
}
 
 
bool insertHeap(Heap& heap, int value) {
	if (heap.size == heap.capacity) {
		fprintf(stderr, "栈空间耗尽!\n");
		return false;
	}
 
	int index = heap.size;
	heap.arr[heap.size++] = value;//先赋值value，再size++
	adjustUp(heap, index);
}
 
void adjustUp(Heap& heap, int index) {
	if (index < 0 || index >= heap.size) {
		//如果只有一个结点（插入的结点）inedx<0，或者大于堆的最大值，return掉
		return;
	}
	int temp = heap.arr[index];//temp为插入的值
	while (index > 0) {
		
		int parent = (index - 1) / 2;
		if (parent >= 0) {   //如果索引没有出界，就执行想要操作
			if (heap.arr[parent] < temp) {
				heap.arr[index] = heap.arr[parent];
				heap.arr[parent] = temp;
				index = parent;
			}
			else break;    //如果没有比父结点大，则跳出
		}
		else break;  //越界，结束循环
	}
}
 
 
 
int main() {
 
	Heap hp;
	int orignArry[] = { 1,2,3,87,93,82,92,86,95 };
 
	if (!initHeap(hp, orignArry, sizeof(orignArry) / sizeof(orignArry[0]))) {
		fprintf(stderr, "初始化堆失败！\n"); //输出到控制台
		exit(-1);
	}
 
	for (int i = 0; i < hp.size; i++) {
		cout << "第"<<i<<"个数为："<<hp.arr[i] << endl;
	}
 
	//向堆中插入元素
	insertHeap(hp, 99);
	printf("在堆中插入新的元素99，插入结果：\n");
	for (int i = 0; i < hp.size; i++) {
		cout << "第" << i << "个数为：" << hp.arr[i] << endl;
	}
 
	int value;
	while (popMax(hp, value)) {
		cout << "依次出列最大元素：" << value << endl;
	}	
	
	system("pause");
	return 0;
}

    image

    当然,部分资料是我搜集整理的,看完请点个赞👍

    • 1
      @ 2023-5-24 1:48:47

      我应该是最短代码，用C++14提交

      #include <bits/stdc++.h>
using namespace std;
int n;
vector<int>a;
int main()
{
    cin>>n;
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        a.insert(upper_bound(a.begin(),a.end(),x),x);
        if(i%2==1)
        {
        	printf("%d\n",a[(i-1)/2]);
        }
    }
    return 0;
}
      • @ 2023-7-11 20:18:52

        额~~

        #include <bits/stdc++.h>
using namespace std;
vector<int>a;
int main(){
    int n = cin.get()-'0'; for(int i=1, x; i<=n; i++){cin >> x; a.insert(upper_bound(a.begin(),a.end(),x),x);if(i&1) cout<<a[(i-1)/2]<<endl;}}
    • 0
      @ 2023-5-26 11:26:33 
      #include<bits/stdc++.h>
using namespace std;
#define N 500100
int n,m,k,s,t,logn,a[N],b[N],c[N];
void add(int x,int k){
	for (;x<=m;x+=x&(-x)) c[x]+=k;
}
int query(int k){
	int xx=0;
	for (int i=k;i;i-=i&(-i)) xx+=c[i];
	return xx;
}
int find(int x){
	int l=1,r=m;
	while (l<=r){
		int mid=(l+r>>1);
		if (query(mid)>=x) r=mid-1;
		else l=mid+1;
	}
	return l;
}
int main()
{
	//freopen("in.txt","r",stdin);
	cin>>n;
	for (int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
	sort(b+1,b+1+n);
	m=unique(b+1,b+1+n)-b-1;
	logn=log2(m);
	for (int i=1;i<=n;++i){
		k=lower_bound(b+1,b+1+m,a[i])-b;
		add(k,1);
		if (i&1) cout<<b[find(i/2+1)]<<"\n";
	}
}
      • 0
        @ 2023-5-23 18:57:58

        权值树状数组+二分查找+离散化

        C++

        1.部分分的想法，就是用类似通排的方法，用一个数组k，每次在k[a[i]]和k[a[i-1]]加1，然后从下标1开始往后扫，当扫到的数的个数是序列的“中位数”就输出。（当然因为a[i]太大而且最多100000个数所以我们要离散一下）

        2.这种想法可以改一下，就是用一个前缀和+二分查找（前缀和数组sum），sum[i]表式小于等于i的数有多少个。二分时当sum[mid]大于等于(想一想为什么要等于）“中位数”，上界缩小。反之，下界缩小。因为k[a[i]]不是一次性加完（就是在线），所以前缀和数组每次都要更改，很费时间。

        3.诶！！前缀和数组要更改！不就是线段树或树状数组吗！我们可以将前缀和数组更改的部分换成树状数组（这里只需要单点修改和区间查询，所以树状数组就够了）。

        于是我们就十分愉快地得出了正解！！！

        如果不是很理解“中位数”可以看一下代码

        #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=100005;
struct asd
{
	int id,val;
}z[N];
bool cmp(asd a,asd b)
{
	return a.val<b.val;
}
int a[N],b[N],c[N],n;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int val)//单点修改 
{
	while(x<=n)
	{
		c[x]+=val;
		x+=lowbit(x);
	}
}
int getsum(int x)//区间查询 
{
	int s=0;
	while(x)
	{
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}
int Find(int x)//二分查找
{
	int l=1,r=n,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;//这个写法等价于mid=(l+r)/2，老师说用位运算比较有逼格 :D
		int s=getsum(mid);//小于等于mid的数的个数 
		if(s>=x/2+1)r=mid-1;//个数大于等于“中位数”，上界缩小（x是要求中位数的序列的长度） 
		else l=mid+1;//反之，下界缩小 
	}
	return b[l];
}
void Disc()//离散化 
{
	sort(z+1,z+n+1,cmp);//按照值的大小排序，相等也无所谓 
	for(int i=1;i<=n;i++)
	{
		a[z[i].id]=i;//z[i].id是这个数在未排序的序列中的编号，用i替换原来的值 
		b[i]=z[i].val;//b[i]表示的是离散后的数值为i的数的真实值 
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&z[i].val);
		z[i].id=i;
	}
	Disc(); //离散化 
	cout<<b[a[1]]<<endl;
	add(a[1],1);
	for(int i=3;i<=n;i+=2)
	{
		add(a[i],1);//在a[i]位加一 
		add(a[i-1],1);//在a[i-1]位加一
		printf("%d\n",Find(i));//二分查找 
	}
	return 0;
}
        • @ 2023-5-23 21:54:12

          我有个问题,代码里第四行的math头文件是什么鬼,不应该是<math.h>吗,还是我没听说过

        • @ 2023-5-26 11:22:45

          @ 已修改

      • 1

      中位数

      信息

      ID
      113
      时间
      1000ms
      内存
      128MiB
      难度
      3
      标签
      递交数
      99
      已通过
      53
      上传者
      1. 关于
      2. 联系我们
      3. 隐私
      4. 服务条款
      5. 版权申诉
      6. Language
      7. 兼容模式
      8. 主题
      3. Worker 0, 14ms
      4. Powered by Hydro v4.9.24 Community, Modified by hetao