> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/heap-priorityqueue.md).

# Heap (PriorityQueue)

## 经典题目

[*218 The Skyline Problem* ](https://leetcode.com/problems/the-skyline-problem/description/)

几何题，考虑用**扫描线**方法（与Y轴平行）解决。

首先看几个特征。每个building有2个点，左边界和右边界。当扫描线扫到**左边界**时，如果当前左边界为**最高**（对谁而言？）的点，那么该点必然为skyline之一；当扫描线扫到**右边界**时，如果该点为**第二高**（对谁而言？）的点，那么该点也为skyline之一。

这里最高，第二高是指当前有效的building高度，即同一区块。也就是说，当扫描线扫到别的区块时，之前的区块的点都不应该考虑。这里我们想到用**maxHeap**的方式，**左边界时入堆，右边界时出堆**。

同时，有几种特殊情况需要考虑。第一种，**两building左右相接**，此时，相接处的点应首先考虑最高点（如考虑最低点，则会多出一个错误的点）。第二种，**两building重合，左边界应首先考虑最高点，右边界应首先考虑最低点**。所以这也是为什么我们把右边界的高度改为-h的原因。

```java
class Point {
    int x;
    int h;
    public Point(int x, int h) {
        this.x = x;
        this.h = h;
    }
}

class MyComparator implements Comparator<Point> {
    @Override
    public int compare(Point p1, Point p2) {
        if (p1.x == p2.x) {
            return p2.h - p1.h;
        }
        return p1.x - p2.x;
    }
}

public List<int[]> getSkyline(int[][] buildings) {
    List<int[]> res = new ArrayList<>();
    List<Point> list = getSortedList(buildings);
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    maxHeap.offer(0);
    for (Point p : list) {
        int h = p.h;
        int x = p.x;
        if (h > 0) {
            if (h > maxHeap.peek()) {
                res.add(new int[] {x, h});
            }
            maxHeap.offer(h);
        } else {
            h = -h;
            maxHeap.remove(h);
            if (h > maxHeap.peek()) {
                res.add(new int[] {x, maxHeap.peek()});
            }
        }
    }
    return res;
}

private List<Point> getSortedList(int[][] buildings) {
    List<Point> list = new ArrayList<>();
    for (int[] b : buildings) {
        Point leftBoundary = new Point(b[0], b[2]);
        Point rightBoundary = new Point(b[1], -b[2]);
        list.add(leftBoundary);
        list.add(rightBoundary);
    }
    Collections.sort(list, new MyComparator());
    return list;
}
```