Bittiger CS106 lesson2

cs data structure

Treemap

• Red-black tree implementation
• O(logn): put, containsKey, remove
• Iteration sorted key

In-order iteration( mid-order iteration)

Heap

• Almost complete tree (complete tree: 每个node有两个孩子
  
  • Each level must have maximum number of nodes
  • Bottom level could be an exception
  • Filled from left to right on each level（从左到右连续）
• Largest/smallest data is the root
• Children always smaller/greater than parent

Heap的Remove和Add： 先保持型不便，再一个一个换

data stucture:

Priority Queue (Heap)

public class priorityQueue<E> extends AbstractQueue<e> ...

Priority Queue in Java

public boolean offer (E e) {
  if（e == null)
    throw new NullPointerException();
  modeCount++;
  int i = size;
  if (i >= queue ...

Sorting

Bubble Sort

Selection Sort

Insertion Sort

worst case: 需要从小到大排列 但给的原始是从大到小

best case: 需要从小到大排列 给的原始就是从小到大

j = ++i(先i自加，再赋值给j)
j = i++ (先把i赋值给j, i再自加）

Quick Sort

Merge Sort

int mid = low + (high - low)/2
这种方法一般不会overflow，因为这里面的中间值不可能超过high.

Mergesort算法的核心是merge
Extra memory: 但object无所谓，因为只需要暂时存储object的reference,而且又stable.所以一般object用mergesort;
而primitive一般用quicksort.

Utility classes and methods