Heap

1.Heap Definition

Heap using STL

#include <queue>
//Max heap using priority queue
std::priority_queue<int> pq(nums.begin(),nums.end());
//Min heap using priority queue
std::priority_queue<int, std::vector<int>, std::greater<int>> pq(nums.begin(),nums.end());

If you have an array of size n and you want to build a heap from all items at once, Floyd’s algorithm can do it with O(n) complexity.
If you have an empty priority queue to which you want to add n items, one at a time, then the complexity is O(n*log(n)).

Functions

//push
template <typename T>
pq.push(T t)
//top, return top of heap
pq.top()
//pop, remove top of heap
pq.pop()
//size, return size of heap
pq.size()

Heap & Sort & Hash Table

Intuition: count->hash table->sort hash table->heap

• 253 Meeting Rooms II(Q:A)

• 347 Top K Frequent Elements(Q:A)

• 451 Sort Characters By Frequency(Q:A)

• 355 Design Twitter(Q:A)