怎么做一个企业网站/发布外链

堆其结构为完全二叉树，物理存储采取数组，一个点I 其孩子节点为 2i+1 2i+2 堆的操作包含top() pop() push()
并且这些操作都是基于堆的顶部进行，其通常调用down下沉操作和up上浮操作。

堆不支持任意节点的删除（意味着节点之间顺序打乱）。通常可以基于双堆实现逻辑删除。

class my_heap
{private:priority_queue<int> q1;   //最大堆priority_queue<int> q2;  //存放待删除元素public:void push(int _v) {q1.push(_v);}void erase(int _v) //任意节点删除{q2.push(_v);//在待删除堆中插入该值即可}int top()  //获取最大值{//首先判断当前最大堆的堆顶是否为已删除元素（如果是，那么一定在逻辑删除堆堆顶（堆顶最大））while(q1.empty()==false &&q2.empty()==false && q1.top()==q2.top()){q1.pop();q2.pop();}//将待删除全部删除后  q1堆顶即为真正的最大值if(q1.empty())return 0;elsereturn q1.top();}bool empty()   //当前堆是否为空{return q1.size()==0 || q1.size()==q2.size();}
};

当需要删除任意元素val时，将val压入q2。下一次的实际堆q1的top() pop()操作时：
将q1堆顶和q2堆顶相等的元素删除（pop） 同时由于两边堆顶总是存放最大值=》确保删除的正确性

题目描述
给定一个N \times 3N×3的矩阵matrix，对于每一个长度为3的小数组arr，都表示一个大楼的三个数据。arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度(一定大于0)。每座大楼的地基都在X轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组
[要求]
时间复杂度为O(n log n)

输入：
8
2 5 6
1 7 4
4 6 7
3 6 5
10 13 2
9 11 3
12 14 4
10 12 5

输出：
1 2 4
2 4 6
4 6 7
6 7 4
9 10 3
10 12 5
12 14 4

直观思路

1. 初始化一个x轴，大小为arr[50000] 其中50000所有楼分布最大范围
2. 每遇到一个楼 left=>right 开始遍历x轴上left=>right的区间
3. 研究： height>x.height 如果是，更新x.height 即更新对应位置最高点

该思路复杂度很高为 O（N*N） 即每一栋楼需要一次遍历，而且最关键是每一个坐标的遍历

优化思路

不再研究每一个坐标点，而是研究关键点：

每一栋楼包含两个关键点：即左边点、右边点

初始化：

1. 将所有大楼的关键点，按照下标x排序。
2. 维护一个最大堆，堆顶存放高度最高的关键点。
3. 采取index、height标记当前研究区间的起点和高度。

从左往右扫描过程：

①每遇到一个左关键点，加入heap，分析heap.top()>height? 即当前大楼加入使得天际线变高：
如果变高，那么输出前一段区间和高度。

②每遇到一个右关键点，意味者一栋大楼结束，那么需要从heap中删除该左关键点的高度，删除后，研究
heap.top()<height? 即当前大楼删除使得天际线变低，如果变低，输出前一段区间和高度。

由此可以得出，扫描过程的几个特点，其类似于人真实的记录楼层高度的过程：

• 最大堆中存放者当前已存在大楼的高度，堆顶即为最高楼高度。
• 每次遇到大楼的加入或者删除，研究当前最高楼是否变化。
• 如果发生变化，那么输出前一段最高楼的区间。

struct node
{int x;  //所在x下标int y;  //所在高度int left_or_right;//是一个长方形的 左边=0  右边=1node(int _x,int _y,int which){x=_x;y=_y;left_or_right=which;}
};
bool static cmp1(node a,node b)
{return a.x<b.x;  //关键点left=>right 按照下标排序
}
int main()
{int n;cin>>n;int l,r,h;vector<node> node_arr;//存放关键点for(int i=0;i<n;i++){cin>>l>>r>>h;node_arr.push_back(node(l,h,0));node_arr.push_back(node(r,h,1));   //每个大楼都有两个关键节点}sort(node_arr.begin(),node_arr.end(),cmp1);//初始化两个最大堆  以支持任意节点的删除my_heap skyline;int len=node_arr.size();int height=0;//当前楼最大高度int index=0;//当前最大高度的左起点for(int i=0;i<len;i++)  //开始从左往右扫描关键点{if(node_arr[i].left_or_right==0)  //左边节点{skyline.push(node_arr[i].y);  //放入最大堆中int now_height=skyline.top();//当前的最大高度if(now_height>height) //新加入楼更高了{if(height>0 && node_arr[i].x>index)cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;//输出前一部分高度//同时更新新的区间起点信息index=node_arr[i].x;height=node_arr[i].y;}}else  //遇到右边关键点{skyline.erase(node_arr[i].y);//删除该节点if(skyline.top()<height)  //若删除之后 天际线变低了{if(node_arr[i].x>index)cout<<index<<" "<<node_arr[i].x<<" "<<height<<endl;//更新区间的起点信息index=node_arr[i].x;height=skyline.top();}}} 
}

易错点：

输出前一段区间，需要前一段区间的长度大于0（解决：上一个右关键点，和下一个左关键点重合）