Amortized analysis

  1. Aggregate method：isn’t very useful need first obtain a good bound，if we can obtain this better bound through other techniques, we can omit dividing the bound by n to obtain the amortized cost.
  2. Accounting method:Credits keep track of potential.Each stack entry has a credit used to pay for the time it is
    popped. many accounts
  3. Potential function method：P(i)=P(i-1)+amortizedcost(i)-actualcost(i), Potential consists of credits.The pop cost is paid by potential.only one account,shared by everyone

Succinct data structure

Arbitrary ordered trees
use parenthesis notation

binary tree
Heap-like natation堆式表示法
label internal nodes with a 1,and external nodes with a 0
n node binary tree can be represented in 2n+1 bits
operations:O(n)时间内
left child(x)=[2x]
right child(x)=[2x+1]
parent(x)=[]

bit vector B
rank1(i):i之前1的个数
select1(i):B中第i个1的位置
rank0(i)
select0(i)

操作实现：
leftchild(k)=2rank1(k)
rightchild(k)=2rank1(k)+1
ordered tree
level-order degree sequence
write the degree sequence in level order and then write them in unary
2n-1bits
parent(k):位置k之前有几个0，父节点就是几
child(k):第k个0后面的结点

External sorting

based on a fast internal sort method
Average run time：quick sort
worst-case run time:merge sort

3 buffers input small large
fill middle group from disk
if next record <=middle_min send to small
if next record >=middle_max send to large
else remove middle_min or middle_max form middle and add new record to the middle group
fill input buffer when it gers empty
Write small/large buffer when full 小/大缓冲区满时写入磁盘
write middle group in sorted when done 中间组处理完成后写入磁盘，中间组一般通过双端优先队列double ended priority queue维护，可以在O(1)时间内获取当前中间组的边界值、

归并的外排
fill Input0 from R1 and Input1 from R2
merge Input0 and Input1 into Output buffer
write whenever output buffer full
read whenever input buffer empty

improve run generation
reduce number of merge passes

Double-ended priority queue

primary operations:insert, remove max,remove min

general methods
1.dual min and max single-ended priority queues
each element is both in a min and a max single-ended priority queue
single-ended priority queue must support an arbitrary remove
each node in a priority queue has a pointer to the node in the other priority queue that has the same element

2n nodes
2.correspondence based min and max single-ended priority queues
use a min and a max single-ended priority queue
no element is in both the min and max single-ended priority queue
at most 1 element is in a buffer
remaining elements are in the single-ended priority queues,which may be
of different size
establish a correspondence between the min and max single-ended priority queues:total correspondence or leaf correspondence
single-ended priority queue must support an arbitrary remove

specialized methods

  1. min-max heaps
    完全二叉树 层级交替 最小层节点小于其父节点大于其祖父节点，最大层节点大于其父节点小于其祖父节点
    树根存储最小元素 最大元素位于根节点的两个子节点之一
    以最小层节点为根的子树保持最小堆性质，以最大层节点为根的子树保持最大堆性质
    插入操作：
    需要维护堆的性质
    将元素添加到完全二叉树下一个空闲位置
    计算新节点所在层级
    若在最小层，判断，若新元素小于祖父节点，与祖父节点交互并递归向上，若在最大层，判断若新元素大于祖父节点，则与祖父交换并递归向上验证
    删除最小元素：
    移除根节点
    将数组最后一个元素移至根位置
    比较该节点与其子节点、孙节点中的最小值，若需要交换，则递归向下调整到合适位置
    删除最大元素：
    比较根节点的两个子节点取较大者，用数组末尾元素替代被删除的最大值
    调整过程类似删除最小元素，但需要比较最大值并维护最大层性质
  2. Deap
    双端堆 一种完全二叉树
    根节点为空
    左子树为最小堆
    右子树为最大堆
    对于左子树中的任意节点i，其在右子树中的对应节点j，满足Deap[i]<=Deap[j]
    通常使用数组表示
    根节点位于数组索引1的位置
    插入操作：
    定位插入位置：新元素x添加到Deap最后一个位置
    确定堆位置：
    如果x位于最小堆中，找到最大堆中的对应节点j，比较x与Deap[j]的大小，若x大，则交换这两个节点，然后在最大堆中调整，否则在最小堆中调整
    如果x位于最大堆中，类似
    堆调整需要满足最小堆/最大堆性质
    删除最小值操作：
    取出最小值（根节点的左子节点）
    临时删除最后一个节点，放到一边temp中
    将空缺位置由其子节点的最小值向上递补，重复子过程直到空缺达到叶子节点，
    将最后删除的节点x插入到空缺位置，并进行必要的调整
  3. interval heaps