algo-aha

涉及到优先选择时用到堆，比如贪心法、k路归并、类dijkstra算法

堆的数组实现

数组x[1..n]下标从1开始（不使用x[0]），这样节点i的lchild = 2*i, rchild = 2*i+1, parent = i/2

最小堆性质：父节点<=它的子节点

关键函数siftup(n)用于在x[n]不满足堆性质时进行调整，调整只发生在i和它的父节点间，i不断向上；关键函数siftdown(n)用于在x[1]不满足堆性质时进行调整，调整只发生在i和它的较小子节点间，i不断向下。

void siftup(n) {
    int i = n;
    while (true) {
        if (i == 1) break;
        int p = i / 2;
        if (x[p] <= x[i]) break;
        swap(i, p);
        i = p;
    }
}

void siftdown(n) {
    int i = 1;
    while (true) {
      int c = 2 * i;
      if (c > n) break;
      if (c + 1 <= n && x[c+1] < x[c])
          c++;
      if (x[i] <= x[c]) break;
      swap(i, c);
      i = c;
    }
}

堆排序

用最大堆，将堆顶调换到数组尾、然后在去掉数组尾的堆上"整堆”

for i = [2,n]
    siftup(i)
for i = [n,2]
    swap(1, i)
    siftdown(i-1)

siftdown(l,u)这种实现就是将siftdown()中的i=1变成i=l、跟n的比较变成跟u的比较

for i = [n/2, 1]
    siftdown(i, n)
for i = [n,2]
    swap(1, i)
    siftdown(1, i-1)