A heap:

• Stores elements, and can find the smallest (min-heap) or largest (max-heap) element stored in O(1).
• Can add elements and remove the smallest (min-heap) or largest (max-heap) element in O(log(n)).
• Can perform insertions and removals while always maintaining the first property.

PriorityQueue in Java

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
The head of this queue is the least element with respect to the specified ordering

Opeartions

• void offer()
• Object poll()
• int size()
• boolean isEmpty()

TreeSet in Java

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

Opeartions

• void add()
• E lower(E e)
• E floor(E e)
• E ceiling(E e)
• E higher(E e)

用法

1. 直接，当作排序数组
2. Dijkstra，求单源最短路径
3. 一边压入，比较另一边

刷题

• 215. Kth Largest Element in an Array
• 23. Merge k Sorted Lists
• 347. Top K Frequent Elements
• 1488. Avoid Flood in The City（treeset）
• 1337. The K Weakest Rows in a Matrix（Easy, inituitive，但是用二分查找更快）
• 703. Kth Largest Element in a Stream（Easy, 不能更简单粗暴的heap）
• 506. Relative Ranks（Easy, 任意排序）
• 1046. Last Stone Weight（Easy, heap直接上）
• 2099. Find Subsequence of Length K With the Largest Sum（Easy, 有点意思，理解了，好像又不太理解）
• 451. Sort Characters By Frequency
• 767. Reorganize String（这题没做出来，着实伤心了！！）
• 743. Network Delay Time
• 264. Ugly Number II（做到这里，还是没有总结出技巧，要继续努力QwQ）
• 313. Super Ugly Number（上一题的升级版）
• 378. Kth Smallest Element in a Sorted Matrix（与前面的同一类型）
• 1094. Car Pooling（和下面235很像）
• 692. Top K Frequent Words（Easy，直接）
• 1792. Maximum Average Pass Ratio（基础操作）
• 355. Design Twitter（简单应用题）
• 1962. Remove Stones to Minimize the Total（算是常规操作）
• 1405. Longest Happy String（贪心算法）
• 1514. Path with Maximum Probability（Dijkstra）
• 1882. Process Tasks Using Servers
• 1801. Number of Orders in the Backlog
• 505. The Maze II（Dijkstra 练到吐）
• 1834. Single-Threaded CPU

三思

• 218. The Skyline Problem
• 787. Cheapest Flights Within K Stops（Graph里的同题，再战，依旧铩羽而归，惭愧惭愧 QwQ，这题可以1. BellBellman-Ford: Map + queue；2. Dijkstra: array + priority queue；升级版1928. Minimum Cost to Reach Destination in Time，我还是不会QwQ）
• 1353. Maximum Number of Events That Can Be Attended（还需修炼！pq的经典用法）
• 373. Find K Pairs with Smallest Sums（这题为啥没做出来？？？？反省！！！！！）
• 1631. Path With Minimum Effort（Dijikstra）
• 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
• 1696. Jump Game VI（很好玩的跳跃游戏，总是能把愚蠢的我打回原型🐟）
• 1786. Number of Restricted Paths From First to Last Node（需要每天复习一遍的Dijkstra）
• 295. Find Median from Data Stream（经典的两队配合）

其他

• 621. Task Scheduler（是很tricky的一题，知道怎么做了，但不知道为啥和怎么想出来的）
• 253. Meeting Rooms II（被shuxian剧透了，生气）

参考

• Heap Wikipedia