Tech Life On The Way

Heap Sort 最清新的讲解 https://www.youtube.com/watch?v=t0Cq6tVNRBA Heap sort的数据结构是BS, 为了操作方便，会将BS flattened成一个一维数组。        1    2     3 4  5  6   7 坐标如上， getLeftChildIndex(index) {return 2*index+1;} getRightChildIndex(index) {return 2*index+2;} getParent(index) {return (index-1) / 2} 每一次的insertion 会发生在the end of arrary, which is BS中的第一个available 的叶子节点。然后根据条件选择是否heapifyUp, 因此insertion的复杂度为O(log(n)) 每一次的deletion 是先delete 该node，然后将最后的叶子节点也就是the end of array 摆放到被delete掉的节点的位置。然后根据条件选择是否heapifyDown. 因此，deletion的复杂度也为O(log(n))

vector<T> v v.push_back(a), v.pop_back(), v.back(), v.size(), v.empty(), v.clear() queue<T> q q.push(a), q.pop(), q.front(), q.empty() stack<T> s s.push(a), s.pop(), s.top(), s.empty() unordered_map<TKey, TValue> uMap   (using as hashtable access O(1)) uMap[key] = value, uMap.at(key) uMap.emplace(key, value), uMap.insert(make_pair<TKey, TValue>(key, value)) uMap.find(key), return iterator  uMap.size(), uMap.emtpy() uMap.count(key) == 1 or == 0 NOTE:  access a map by a key which does not exist, can cause a new key insert with a default value. unordered_set<T> uSet, hashset, no duplication, access O(1) uSet.insert(v), uSet.count(v) == 0 or == 1 uSet.erase(v) uSet.empty() map<TKey, TValue> m, BST based. access O(log(n))    m[key] = value, m.at(key) m.emplace(key, value), m.insert(make_pair<TKey, TValue>(key, value)) m.find(key), return iterator  m.size(), m.empty() set<T>