天梯题集——关于堆的判断（小顶堆模板题、模拟构造过程）

「爱情、让人受尽委屈。」 2022-12-23 15:24 160阅读 0赞

> 堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。  
> 堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。  
> 注意：堆的左右孩子没有大小的顺序。

### [关于堆的判断][Link 1] ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

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

这道题目完全可以看成一道堆的模板题，只要构建出小顶堆其他都好说。

#### 解题思路 ####

##### ①、构建小顶堆 #####

小顶堆是构成原理：  
（1）插入第一个节点  
![1][]  
（2）插入第二个节点（不符合小顶堆原则，需替换）  
![在这里插入图片描述][20201125171231985.PNG_pic_center]  
（3）节点互换  
![在这里插入图片描述][20201125171530249.PNG_pic_center]  
…  
（4）最终小顶堆结果  
![5][]

//构建小顶堆
    void creat(int w){ 
    	pile[++cnt] = w;
    	int t = cnt;
    	while(t>1&&pile[t/2]>pile[t]){ 
    		pile[t] = pile[t/2];
    		pile[t/2] = w;
    		t /= 2;
    	}
    	return;
    }

##### ②、利用 map 映射出每个键值对应的节点号 #####

利用 map 实现键值反应节点号，能够简单直接地判断出各个键值之间的关系。

map<int, int> p;
    for(int i=1; i<=n; i++){ 
    	p[pile[i]] = i;
    }

##### ③、按照题目判断每一条命题 #####

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

实现代码

#include<bits/stdc++.h>
    using namespace std;
    int cnt=0;
    int pile[1010];
    
    void creat(int w){ 
    	pile[++cnt] = w;
    	int t = cnt;
    	while(t>1&&pile[t/2]>pile[t]){ 
    		pile[t] = pile[t/2];
    		pile[t/2] = w;
    		t /= 2;
    	}
    	return;
    }
    
    int main(){ 
    	int n, m, tmp;
    	map<int, int> p;
    	cin>>n>>m;
    	for(int i=1; i<=n; i++){ 
    		cin>>tmp;
    		creat(tmp);
    	}
    	for(int i=1; i<=n; i++){ 
    		p[pile[i]] = i;
    	}
    	while(m--){ 
    		int flag=0, x, y;
    		string s;
    		cin>>x>>s;
    		if(s[0]=='a'){ 
    			cin>>y;
    			getline(cin, s);
    			if(p[x]/2==p[y]/2)
    				flag=1;
    		}
    		else{ 
    			cin>>s;
    			if(s[0]=='a'){ 
    				cin>>s;
    				cin>>s>>y;
    				if(p[y]==p[x]/2)
    				flag=1;
    			}
    			else{ 
    				cin>>s;
    				if(s[0]=='r'){ 
    					if(p[x]==1)
    						flag=1;
    				}
    				else{ 
    					cin>>s>>y;
    					if(p[x]==p[y]/2)
    					flag=1;
    				}
    			}
    		}
    		if(flag) cout<<"T\n";
    		else cout<<"F\n";
    	}
    	
    	
    	return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805046380707840/problems/994805064676261888
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/307f0ace391b4455a42cdf7085ee0802.png
[1]: /images/20221120/352ee4db36ae41ecbeec8b549abe7310.png
[20201125171231985.PNG_pic_center]: /images/20221120/8842254510284b47b0699743b9d5371d.png
[20201125171530249.PNG_pic_center]: /images/20221120/7d1a779072b84085af2e3614ded3adfe.png
[5]: /images/20221120/871c17a02cdd428ca9cc4b4ec0721d3c.png