二叉堆

实现了二叉堆的基本算法：adjust_heap(下沉)，pop_heap，push_heap，make_heap，和sort_heap。

二叉堆的实现

• 二叉堆是完全二叉树
• 一个高度为h的堆里，元素最多为$2^{(h+1)} - 1$个， 最少为$2^h$个.

SGI STL的heap类算法并未使用哨兵，因为如果要用一个vector来初始化priority_queue，则需要把vector中所有元素右移1位，增加了建堆隐含的常数时间。

• 根节点下标为0。
• i节点的左孩子为$2i + 1$，右孩子为$2i + 2$
• i节点的父亲节点为(i - 1) / 2
  注意：需要处理i == 0的情况，否则对于size_t ,会溢出。
• 叶子节点开始的下标为len - 2 / 2
  注意：需要处理len < 2的情况，否则对于size_t ,会溢出。

下沉(sink, percolate down)

实现1(GNU C++ STL采用的实现)

假设一个节点：

• 左右子树都满足二叉堆的性质
• 该节点小于其左孩子和（或）右孩子
  此时需要调整该节点使得以该节点为根的树满足二叉堆的性质，进行的操作叫做下沉。

思路

• 把这个节点的值先保存下来，将这个节点看作一个洞。
• 比较这个洞的左孩子和右孩子的值，用有较大值的孩子节点的值填补这个洞。
• 洞转移当前面有较大值的孩子节点。

实现时因为可能一个节点没有右孩子，只有左孩子，所以我们先计算右孩子的值，并以右孩子不存在作为循环结束的条件。循环结束后，如果恰好右孩子是size，那么此时的洞就是只有左孩子的节点。我们用洞的左孩子填这个洞，洞变为他的左孩子。最后，再用一开始记录的value来填补这个洞。

最重要的实现细节：此时这这洞被填完了不算完成。我们还必须对这个刚被填好的洞做一次上浮swim。因为我们在下沉这个洞的时候，没有考虑和最开始节点的值的关系。

STL这样实现的原因：TODO(为什么不看着value的值来决定还下不下沉呢？而是沉到底在浮上来，很神秘。)

最后的swim使用了限制上浮位置的swim，还不知道为什么这样做。不得不说STL里的有些实现真的是奇怪。

GNU STL 中的实现

template<typename It, typename Compare>
void sink(It first, It hole, It last, const Compare& comp){
    auto hole_copy = hole;
    auto value = *hole;
    auto secondChild = hole + distance(first, hole) + 2;
    
    while(secondChild < last){
        if( comp(*secondChild, *(secondChild - 1) ) ) --secondChild;
        *hole = *secondChild;
        hole = secondChild;
        secondChild = hole + distance(first, hole) + 2; 
    }
    
    if(secondChild == last){
        *hole = *(--secondChild);
        hole = secondChild;
    }
    
    *hole = value;
    
    swim_with_top(first, hole, hole_copy, last, comp);
}

限制了上浮位置的swim，供下沉的实现1使用，还不知道为什么要这样做。

template<typename It, typename Compare>
void swim_with_top(It first, It hole, It top, It last, const Compare& comp){
    //if hole == first, distance(size_t) will underflow
    if(first == hole || first == last) return;
    auto value  = *hole;
    auto parent = first + (distance(first, hole) - 1) / 2;
    while(hole > top && comp(*parent, value)){
        *hole = *parent;
        hole = parent;
        parent = first + (distance(first, hole) - 1) / 2;
    }
    *hole = value;
}

实现2(CLRS采用的实现，推荐)

大体思路同STL中的实现。在循环里判断是否还需要下沉，不需要就break循环。之后在对于没有右孩子的特殊处理处，要加一个需要继续下沉的判断comp(value, *(secondChild- 1))。

code

template<typename It, typename Compare>
void sink_with_care(It first, It hole, It last, const Compare& comp){
    auto value = *hole;
    auto secondChild = hole + distance(first, hole) + 2;
    
    while(secondChild < last ){
        
        if( comp(*secondChild, *(secondChild - 1) ) ) --secondChild;
        //检查是否value已经比两个孩子里最大的大了，是的话退出循环。
        if( comp(*secondChild, value) ) break; 
        *hole = *secondChild;
        hole = secondChild;
        secondChild = hole + distance(first, hole) + 2; 
    }
    //检查是不是还需要继续下沉，退出循环有两种情况：没有右孩子/比两个孩子都大。
    if(secondChild == last && comp(value, *(secondChild- 1))){
        *hole = *(--secondChild);
        hole = secondChild;
    }
    
    *hole = value;
}

Feb/19/2019新实现（即__adjust_heap）

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void adjust_heap(It first, 
                typename iterator_traits<It>::difference_type hole_idx, 
                It last, 
                const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    // get the value of the hole
    auto hole = first + hole_idx;
    auto val = *hole;
    // get the secondChild It
    auto secondChild = hole + (hole - first) + 2;

    while(secondChild < last)
    {
        // compare second child with first child
        if(comp(*secondChild, *(secondChild - 1))) --secondChild;
        // check if val is greater than both children
        if(comp(*secondChild, val)) break;
        *hole = *secondChild;
        hole = secondChild;
        secondChild = hole + (hole - first) + 2;
    }

    // if it escape the loop because it does not 
    // have a secondChild, we have to check if it
    // still needs to sink
    if(secondChild == last && comp(val, *(--secondChild)))
    {
        *hole = *secondChild;
        hole =secondChild;
    }

    *hole = val;
}

删除堆顶元素(pop_heap)

删除堆顶元素后仍要维护二叉堆的性质。我们只需将二叉堆最后一个元素放到堆顶，之后对堆顶进行下沉sink()即可。

C++ STL中的pop_heap()实现并不是删除堆顶元素，而是将堆顶元素放置到区间的末尾。

pop_heap的实现

template<typename It, typename Comp = less<typename iterator_traits<It>::value_type> >
void pop_heap(It first, It last, const Comp& comp = less<typename iterator_traits<It>::value_type>{})
{
    iter_swap(first, last - 1);
    adjust_heap(first, 0, last - 1);
}

由于C++ STL中容器的元素删除必须通过容器的成员函数，所以下面的例子代码需要传入该容器的引用。

code

template<typename Container, typename Compare>
inline void pop(Container& cont, const Compare& comp){
    auto first = cont.begin();
    auto last  = cont.end();
    *first = *(last - 1);
    sink(first, first, last, comp);
    cont.pop_back();  
}

上浮(swim, percolate up)

• 将要上浮的节点的值储存在value中，并把该节点看作一个洞。
• 如果洞的父亲节点比value小，就把父亲节点的值复制到洞里，让父亲节点成为新的洞。
• 注意洞不能是first节点。
• 最后将洞用value填上。

code

template<typename It, typename Compare>
void swim(It first, It hole, It last, const Compare& comp){
    //if hole == first, distance(size_t) will underflow
    if(first == hole || first == last) return;
    auto value  = *hole;
    auto parent = first + (distance(first, hole) - 1) / 2;
    while(hole > first && comp(*parent, value) ){
        *hole = *parent;
        hole = parent;
        //if hole == first, distance(size_t) will underflow
        parent = first + (distance(first, hole) - 1) / 2;
    }
    *hole = value;
}

加入新元素(push_heap)

要求加入的新元素已经放在堆的最后面，对堆的最后面的元素做上浮即可。

template<typename It, typename Compare>
void push(It first, It last, const Compare& comp){
    swim(first, (last - 1), last, comp);
}

建堆(make_heap)

Williams建堆

一个一个元素加入，每次加入都push_heap一下。需要额外空间。（不推荐）。时间复杂度$\Theta(N\log N)$

Floyd建堆

自底向上，从第一个叶子节点到根节点，做下沉。时间复杂度为$O(N)$

template<typename It, typename Compare = less<typename It::value_type> >
void make_heap_floyd(It first, It last, Compare comp = less<typename It::value_type>{}){
    auto len = distance(first, last);
    if(len < 3){
        sort(first, last, [&comp](const auto& lhs, const auto& rhs){return comp(rhs, lhs);});
        return;
    }
    for(auto it = first + (distance(first, last) - 2)/2; 
    	it >= first; --it) sink(first, it, last, comp);
}

堆排序(sort_heap)

首先在给定的要排序的数组上建堆，之后不断将最大元素用pop_heap从堆中移出，放在最后。最大堆得到的是从小到大的排序。最小堆得到的是从大到小的排序。

优先级队列(priority_queue)

一般在数组上建堆实现。C++ STL的priority_queue默认使用vector作为底层容器。仅提供
top，pop，push等接口。作为一个容器适配器，priority_queue不提供迭代器，因此不能访问除了最大值以外的内容。

priority_queue注意，它的第二个模版参数是Container，第三个才是Comapre。但是构造函数里，是先传Compare，再传Container。

如果需要更灵活的建堆和访问操作，可以使用algorithm算法库中提供的仅支持随机访问迭代器的算法：

- `make_heap`
- `push_heap`（需保证想要放入堆中的元素已经放在末尾）
- `pop_heap`
- `sort_heap`
- `is_heap`
- `is_heap_until` 

使用哨兵实现的二叉堆

• 一个有n个节点的二叉堆
  • 叶子节点为$\lfloor n/2 \rfloor + 1,\,\lfloor n/2 \rfloor + 2, \cdots ,n$
  • 非叶子节点为$\lfloor n/2 \rfloor,\,\lfloor n/2 \rfloor - 1, \cdots , 1$
• 下标为0的位置留做哨兵(sentinel)，根节点下标为1。
• i节点的左孩子为$2i$,i << 1，右孩子为$2i + 1$,(i << 1) + 1
• i节点的父亲节点为$\lfloor i/2 \rfloor$, i / 2
  具体实现可参考：
• C++实现： Github - xiexiexx - xPriority_Queue
• C实现： The Algorithm Design Manual, Second Edition, S.Skiena, Chapter 4.

K路归并

[CLRS]6.5-9, Merge k Sorted Lists
见链表#链表排序##合并k个排序的链表

矩阵上的第k小元素

LC378 有序矩阵中第K小的元素
见顺序统计量#TopK问题##矩阵上的TopK