堆

Posted on 2008-07-29 | In DataStructure

堆是完全二叉树的一种表现形式。以最小堆为例，它要求的每个父节点的值大于两个子节点的值，两个兄弟节点之间的值的大小关系没有限制。由于完全二叉树可以用数组表示，上述性质也可以表述为：

$K_1<=K_{2i+1}$
$K_1<=K_{2i+2}$

因此使用最小堆可以找出这组节点的最小值。推而广之，对于一组无序的数，可以将他们构建成堆来快速得到最大值或最小值，当有新元素进来时，堆也依然可以保持这种特性

堆的核心操作有如下三种

建堆，将一组无序的数组织成堆的形式
- 思路1：将n数组成的无序数组进行原地建堆操作
- 思路2：将n个无序的数一个一个进行插入操作
新元素入堆后如何调整堆
- 将其放到数组最右边的位置
- 递归进行SiftUp调整
堆顶元素出堆后如何调整
- 将数组最后一个节点的值付给堆顶元素
- 删除最后一个元素
- 堆顶节点递归进行SiftDown调整

堆的表示

正如前文所述，由于堆是一种完全二叉树，我们可以用数组表示，如上图中的小顶堆可用数组[4,16,28,31,44,59]表示。对于数组中的任意元素，下标为i的节点的左孩子节点的下标为i*2+1，右孩子节点的下标为2*i+2，父节点的坐标为(i-1)/2。

class Heap{
    vector<int> heap;
    int n; //堆大小
    int count; //堆中元素个数

public:
    Heap(int capicity){
        heap = vector<int>(capacity, 0);
        n = capacity;
        count = 0;
    }
    Heap(vector<int>& arr){
        capacity = arr.size();
        count = capacity;
        heap = arr;
        buildHeap(heap);
    }
    void buildHeap(vector<int>& arr);
    void push(int data);
    int top(){ return heap[0]; };
    void pop();
private:
    int left_child_index(int pos){
        int index = pos*2+1;
        return index >= n?-1:index;
    }
    int right_child_index(int pos){
        int index = pos*2+2;
        return index?=n?-1:index;
    }
    int parent_index(int pos){
        return (pos-1)/2;
    }
    void sift_up(size_t pos);
    void sift_down(size_t pos);
};

`SiftDown`调整

所谓SiftDown调整，即将一个不合适的父节点下降到合适的位置。以小顶堆为例，我们需要考虑四种情况：

//递归调整
void sift_down(vector<int>& heap, size_t position){
    //找到左右节点的index
    size_t l = left_child_index(position);
    size_t r = right_child_index(position);
    
    //待删除节点为叶子节点
    if(l == -1 && r == -1){
        return;
    }
    //待删除节点左子节点为空，说明当前已经是叶子节点
    else if(l == -1 ){
        return;
    }
    //待删除节点的右子节点为空，比较左节点
    else if(r == -1 ){
        if(heap[i] > heap[l]){
            swap(heap[i], heap[l]);
            sift_down(l);
        }
    }else{
        //待删除节点的左右子节点都不空，找到最小的
        size_t index = heap[l] < heap[r] ? l:r;
        if(heap[i] > heap[index]){
            swap(heap[i],heap[index]);
            sift_down(index);
        }
    }
}

`SiftUp`调整

和SiftDown类似，SiftUp调整是将一个不合适的子节点上升到合适的位置，例如新元素进入堆之后，该元素要进行SiftUp调整

void sift_up(vector<int>& heap, size_t pos){
    if(pos == 0){
        return;
    }
    int p = parent_index(pos);
    if(heap[pos]<heap[p]){
        //交换父子节点
        swap(heap[pos], [p]);
        //递归调整
        sift_up(p);
    }
}

建堆

了解了堆调整的两个算法后，我们可以用上面的方法来建堆。如上文所述，建堆有两种思路，其中第二种思路较为简单，可以退化为入堆操作，第一种思路需要按下面步骤操作：

将n个关键码放到一维数组中，整体不是最小堆
由完全二叉树的特性，有一半的节点⌊n/2⌋是叶子节点，它们不参与建堆的过程
- i≥⌊n/2⌋ 时，以关键码Ki为根的子树已经是堆
从倒数第二层最右边的非叶子节点开始（完全二叉树数组i=⌊n/2-1⌋的元素），依次向前，进行递归SiftDown调整。

例如上图中，我们有一组8个数的无序序列{72,73,71,23,94,16,05,68}，建堆步骤为

按照完全二叉树排布，形成树形结构，如上图
成树后，可以看到有4个节点(⌊4/2⌋)已经是叶子节点，它们不需要参与建堆的过程
从23开始（数组第i=⌊4/2-1⌋=3项）依次进行sift_down调整，顺序依次是:23,71 ,73 ,72

void buildHeap(vector<int>& heap){
  for (int i=count/2-1; i>=0; i--)
        sift_down(heap,i);
    } 
}

分析一下建堆的效率:

$n$个节点的堆，高度为$d=⌊\log_2^{n}+1⌋$，设根为第$0$层，第$i$层节点数为$2^i$
考虑一个元素在队中向下移动的距离
- 大约一半的节点深度为$d-1$，不移动（叶）。
- 四分之一的节点深度为$d-2$，而它们至多能向下移动一层。
- 树中每向上一层，节点的数目为前一层的一半，而子树高度加一。
- 因此元素移动的最大距离的总数为：

插入元素

对于插入操作，我们首先将待插入元素放到数组末尾，然后利用前面提到的sift_up算法，让新插入的节点与父节点对比大小，如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。

void push(vector<>int data){
    if(count >= n){
        return ; //堆满了
    }
    ++count;
    heap[count] = data;
    //递归调整
    sift_up(heap,count);
}

删除元素

对于堆来说，由于不支持随机访问，删除元素指的就是删除堆顶元素。以小顶堆为例，当我们删除堆顶元素之后，就需要把第二小的元素放到堆顶，而第二小元素肯定会出现在左右子节点中，于是我们可以将堆顶元素和第二小的个元素进行交换，然后我们再递归删除交换后的这个节点，以此类推，直到叶子节点被删除。

而实的删除算法并不会按照上面思路执行，而是会用到一个小技巧，即我们先将数组中最后一个元素的值和堆顶互换，然后删除数组中最后一个元素（即删除了堆顶元素）。接下来，对于新的堆顶元素，进行上面提到的sift_down操作，直到找到合适位置。

void pop(){
    if(count == 0){
        return ; //堆中没有数据
    }
    heap[0] = heap[count]; //交换堆顶和末尾元素
    heap.pop_back(); //删除末尾元素
    --count ;
    //堆顶元素sift_down
    sift_down(heap,1);
}

堆操作时间复杂度分析

建堆的效率前面已经分析过了为O(n)，对于插入和删除操作来说，它们的主要操作是sift_down和sift_up操作，这两种操作每次均是向上或者向下跨越一层，因此时间复杂度和树的高度成正比，也就是O(logn)。

堆的其它实现

上面介绍的建堆的方式是最基本的二叉堆（Binary Heap），除了这种方式以外还有很多种其它建堆的方式，比如使用BST，红黑树等。不同的建堆方式其性能也不尽相同，这里附上一张对比图

堆排序

我们可以利用堆顶每次返回最优解这个特性来对数组进行原地排序，也就是所谓的堆排序。假设我们要从小到大排序，这时候我们需要建一个大顶堆，按照大顶堆的特性，堆顶元素为数组最大元素，我们把它跟最后一个元素交换，那最大元素就放到了下标为n的位置。接下来为了保持堆的特性，我们需要对新的堆顶进行sift down操作，这样剩下的n-1个元素又构成了新的大顶堆。我们再取堆顶的元素放到n-1的位置，重复这个过程，直到堆中只剩一个元素，排序工作就完成了。

void heap_sort(vector<int>& a){
    buildHeap(a);
    int k = a.size()-1;
    while(k>=0){
        swap(a[0],a[k]);
        --k;
        sift_down(a,0);
    }
}

上面的堆排序算法包含两个过程，建堆过程和堆调整过程，总的时间复杂度为O(n) + O(n*log(n)) = O(nlog(n))。由于存在元素交换，因此堆排序不是稳定排序。

堆的相关应用

求一个无序数组中第K大的元素

这是一道经典的面试题，如果不熟悉堆这种数据结构，首先想到的应该是排序。将数组排序后，从头开始向后遍历k个元素，得到最终结果。这种方式当数组较大的时候，效率并不高，时间复杂度为O(Nlog(N)) + O(K)，不是一种线性解法。

另一种思路是，当K值较小的情况，比如k=3，此时可以采用遍历k次数组的方式，第一次找到最大值，第二次找到次大值，依次类推…，这种方式的时间复杂度为K*O(N)比前面方法要好一些

这道题比较经典的方法是使用堆来解，扫描一遍数组即可。其思路为，建立一个k大小最小堆，如果数组中的元素比堆顶的大，则pop掉堆顶元素，入堆新元素。依次类推，最后堆中存放的是数组中前k个最大值元素，返回推顶元素即可。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,std::vector<int>,std::greater<int>> pq;
        for(auto x:nums){
            if(pq.size()<k){
                pq.push(x);
            }else{
                if(x>pq.top()){
                    pq.pop();
                    pq.push(x);
                }
            }
        }
        return pq.top();
    }
};

上述算法，遍历数组需要O(n)时间复杂度，一次push或pop操作需要 O(logK) 的时间复杂度，所以最坏情况下，n个元素都入堆一次，所以时间复杂度就是O(nlogK)。

无序数组中位数问题

这也是一道经典的面试题，常规做法还是对数组排序，然后选出中位数。显然这种方式的时间复杂度和上面的例子相同，为O(Nlog(N) + O(N/2))。

如果使用堆，我们则无需排序即可找出中位数，如果做到呢？首先，我们需要维护两个堆，一个堆是小顶堆和一个堆是大顶堆，大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。如果数组的大小为偶数，则大小堆的size均为n/2，中位数为大小堆堆元素中的某一个。如果数组的大小为奇数，则可以令大顶堆的size为n/2+1，则中位数为大顶堆的堆顶元素。

int findMedium(vector<int>& arr){
    priority_queue<int> maxHeap;
    priority_queue<int,std::vector<int>,std::greater<int>> minHeap;

    for(auto x : arr){
        if(maxHeap.empty() || x < maxHeap.top()){
            maxHeap.push(x);
        }else{
            minHeap.push(x);
        }
        //adjust size
        if(minHeap.size() > maxHeap.size()){
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
        if(maxHeap.size() - minHeap.size() > 1){
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }
    return maxHeap.top();
}

堆