堆-1

堆

堆（优先级队列，Priority Queue）是一个完全二叉树另加上一个条件：父节点的值总比两个子节点的值大（或者小，这里用大）。由于是完全二叉树，它和它的层次遍历是完全一一对应的，就可以在物理上直接用线性表保存。希望看成树的时候，数一项在一层，数两项在下一层，再四项八项地数，一层一层堆下去，就可以唯一地还原树的结构。在列表里，下标为i的元素的左、右孩子（若有）分别是2 * i + 1和2 * i + 2， 父亲（0没有）下标是（i - 1） / 2。脑子里想着树，物理上用线性表实现就可以了。

堆维护的是一种“偏序性”，并不需要完全按照次序排序。这一点使它在很多操作上能做到比有序数组或者链表更快。

上滤percolate up，下滤percolate down

堆怎么使用？

• 插入元素：将元素插入队尾位置 len - 1，堆的结构性自然保持，但是堆序性可能被破坏。堆序性破坏的地方只可能是len - 1和它父亲，如果它比父亲大，就把它与父亲交换；如果交换后又比现在的父亲大，就继续交换，最差情况是升至栈顶，而层数只不过是log2(n)，因此时间复杂度是log（n）。这个操作就叫上滤。不过连续交换是很蠢的，每次交换都有三次赋值，可以当做这一系列值的循环移位。

下面用到的宏定义，和上滤操作：

#define parent(i) (((i) - 1) / 2)
#define lc(i) (2 * (i) + 1)
#define rc(i) (2 * (i) + 2)

void percolateUp(int heap[], int idx, int len){
    int temp = heap[idx];
    while(idx > 0 && temp > heap[parent(idx)]){
        heap[idx] = heap[parent(idx)];
        idx = parent(idx);    
    }
    heap[idx] = temp;
}

• 取最大元素：返回堆顶的元素，删除堆顶元素。
• 删除某一元素：取队尾的元素放在堆顶位置上，如果违反了堆序性，就对它进行下滤：违反堆序性的位置只可能是这个元素和两个孩子，如果有孩子大于它，那就选两个孩子中更大的那个与之交换；不断做下去直到不违反堆序性（没孩子了或者孩子比它小）。最大交换次数也不过是层数，因此也是log(n)的复杂度。

下滤操作，用idxMax表示自己以及左右孩子中最大的那个的秩：

void percolateDown(int heap[], int idx, int len){
    int temp = heap[idx], idxMax;
    while(lc(idx) < len){
        if(rc(idx) >= len){
            idxMax = (temp < heap[lc(idx)]? lc(idx): idx);
        }else{
            if(heap[lc(idx)] < heap[rc(idx)]){
                idxMax = (temp < heap[rc(idx)]? rc(idx): idx);
            }else{
                idxMax = (temp < heap[lc(idx)]? lc(idx): idx);
            }
        }
        if(idxMax == idx) break;
        heap[idx] = heap[idxMax];
        idx = idxMax;
    }
    heap[idx] = temp;
}

• 更改元素：如果改大了，就做上滤；改小了就做下滤。

建堆

• 一个很顺的思路是，从空堆开始，每进来一个元素，就理解为一次插入操作，对其做上滤。所以叫“自上而下的上滤”。在复杂度上，考虑最遭情况，每个元素都上滤至堆顶，就是(1 * 2 ^ 1) + (2 * 2 ^ 2) + ... + (h * 2 ^ h)次移位， 只考虑最后一项，就已经是n * log2(n)了。而n * log(n)的复杂度，都能做快排了，而且人家排出来还是全序的，堆就可以哭死在厕所了。

• Floyd算法稍微抽象，它是基于左右两个子堆与父节点合成一个大更大的堆而考虑的。在这种情况下，相当于父节点刚刚从足够大更改成了某值， 那就只要做下滤就可以了。于是，从叶子节点开始，两两与父节点合成一个更大的堆，堆再合成堆……那么这个循环到底该怎么写？我是凌乱了，后来看懂，只要从最后一个父节点（也就是最后一个节点的父亲）开始逐渐向前至根节点，对两个子堆进行合并就行了。这样，循环到倒数第二层的时候，孩子（最后一层）都是叶子，显然可以看做堆；到倒数第三层的时候，孩子（倒数第二层）个个都已经是子堆了。没毛病。

817.png

这个复杂度好在哪里了呢？最坏情况下的操作次数是(1 * 2 ^ （h-1）) + (2 * 2 ^ (h-2) ) + ... + (h * 1)。和刚才刚好反了，节点最多的最后一层，操作最少；节点少的堆顶部分，操作次数多。或者说，前者上滤的操作次数是深度，后者的操作次数是高度。这个式子放缩一下，可以得到复杂度是n。爽。

代码：

void makeHeap_Force(int heap[], int len){ //自上而下的上滤
    for(int i = 0; i < len; i ++){
        percolateUp(heap, i, len);
    }
}

void makeHeap_Floyd(int heap[], int len){ //自下而上的下滤
    //下滤的次序是：从最后一个非叶子节点开始，依次向前
    for(int i = (len - 2) / 2; i >= 0; i --){
        percolateDown(heap, i, len);
    }
}

堆排序

这个思路可以是基于选择法排序来的。选择法排序的时候，可以不断地在前面x[0:i)里面选出最大值，放进x[i]， 然后i --。(虽然我的习惯是选最小值往前放，而不是选最大值往后放， 都一样的)

这里呢，就把遍历前缀然后选出最大值，改成了从堆里拿出最大值。把数组建成堆之后，x[0]就是最大元素，准备放进x[i]，正好，为了维护这个堆，要把x[i]补到堆顶，然后下滤。它俩一交换，下滤，就可以了。

循环每次耗时log(n)，因此复杂度n * log(n)。好像和快排差不多。然而堆排序可以做到就地排序，只需要常数的额外空间。而且据说在实际运行中效率是比计算的要好的。反正我只知道很漂亮的样子……

void HeapSort(int heap[], int len){
    makeHeap_Floyd(heap, len);
    int temp;
    for(int i = len - 1; i > 0; i --){
        temp = heap[i];
        heap[i] = heap[0];
        heap[0] = temp;
        percolateDown(heap, 0, i);
    }
}

怎么又是这么多内容啊天，写得累死我了，下次明白的地方我一定简略点。