存储结构

堆是一种具有特殊规则的树，而且是完全二叉树，存储完全二叉树，常见的方式就是数组。

  • 左孩子与父节点在数组索引的关系
    $i{parent}=(i{left}-1)/2$

  • 右孩子与父节点在数组索引的关系
    $i{parent}=(i{right}-2)/2$

  • 孩子节点为主
    $i{left}=2*i{parent}+1$
    $i{right}=2*i{parent}+2$

最大堆实现

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class MaxHeap{
    private ArrayList<Integer> data;
    private int size;
    public MaxHeap(){
        data = new ArrayList();
    }
    public MaxHeap(int[] arr){

    }
    public int size(){
        return this.data.getSize();
    }
    public boolean isEmpty(){
        return this.data.isEmpty();
    }
    public int getLeftChild(int idx){
        return idx*2+1;
    }
    public int getRightChild(int idx){
        return idx*2+2;
    }
    public int getParentBy(int idx){
        return (idx-1)/2;
    }    
}

添加操作

首先将添加元素置于数组尾部(二叉树尾部),然后进行上浮操作，如果父节点<添加元素值则交换位置，一直重复该操作直到到达根节点(k>0)

1
2
3
4
5
6
7
8
9
10
public void siftUp(int k){
    while(k>0&&data.get(k)>data.get(getParent(k))){
        swap(getParent(k),k);
        k=getParent(k);
    }
}
public void add(int element){
    data.add(element);
    siftUp(data.size()-1);
}

删除操作

首先取得数组首部的元素(二叉树根节点),储存，然后使用数组尾部元素覆盖它，然后删除尾部元素。对首部元素，进行下沉操作，首先判断是否存在子树(左子树),不存在结束，否则判断是否存在右子树，如果存在则取两者较大者，与其交换。直到不存在子树(到达叶子结点)或者在以其为根节点的子树已经满足堆的特性时停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void siftDown(int k){
    while(getLeftChild(k)< data.size()){//还有子树吗
        int j=getLeftChild(k);
        if(getRightChild(k)<data.size()){//若右子树存在，两者比较最大
            if(data.get(getRightChild(k))> data.get(j)){
                j=getRightChild(k);
            }
        }
        if(data.get(j)>data.get(k)){
            swap(j,k);
            k=j;
        }
        else{
            break;
        }
    }
}
public Integer poll(){
    if (isEmpty()){
        return null;
    }
    int res = data.get(0);
    data.set(0, data.get(data.size()-1));
    data.remove(data.size()-1);
    siftDown(0);
    return res;
}

堆化

两种操作方法，一种是上浮，一种是下沉，但是它们的时间复杂度有些不同，我们以根节点第0层进行讨论。

上浮方式

第0层:至多交换0次
第1层:每个结点至多交换1次，一共2个结点所以交换次数至多$1\times 2$次
第2层:每个结点至多交换2次，一共4个结点所以交换次数至多$2\times 4$次
第3层:每个结点至多交换3次，一共8个结点所以交换次数至多$3\times 8$次
…

第k层:每个结点至多交换k次，一共$2^k$个结点所以交换次数至多$k\times 2^k$次
因此，假设有n个结点，则层数为$\log n$交换次数为:

所以复杂度是$O(n\log n)$

下沉方式

假设有$n$个结点,需要证明以下问题:

  • 证明二叉树$n_0=n_2+1$

    $proof:$

    我们考虑引入二叉树的边的总数为$sum_{edge}$

    除了根节点外，每个结点都是由一条边引出来的，可以得:

    我们关注每个结点引出的边，可得:

    联立两个式子得:

  • 证明完全二叉树底层叶子结点数为$[\frac{n+1}{2}]$

    $proof:$

    首先根据完全二叉树的的特性，$n_1$只能为$1$或者$0$.

    • 当$n_1=0$时:

      此时结点数$n$为奇数，因为除了根节点都是成对出现。由$n_0=n_2+1$,$n=n_0+n_1+n_2$,$n_1=0$得：

    • 当$n_1=1$时:

      此时结点数$n$为偶数，由$n_0=n_2+1$,$n=n_0+n_1+n_2$,$n_1=1$得：

所以可得:

因此完全二叉树的底部结点数为$(n+1)/2$，它们无需下沉，因为没有子树,（倒数第0层）。

倒数第一层结点数有$2^{[\log n]-1}$，它们最多交换$1$次，因此总次数为$2^{[\log n]-1}\times 1$。

倒数第二层结点数有$2^{[\log n]-2}$，它们最多交换2次，因此总次数为$2^{[\log n]-2}\times 2$

倒数第三层结点数有$2^{[\log n]-3}$，它们最多交换$3$次，因此总次数为$2^{[\log n]-3}\times 3$

…

倒数第k层结点数有$2^{[\log n]-k}$,它们最多交换$k$次，因此总次数为$2^{[\log n]-k}\times k$

所以总次数

所以时间复杂度是$O(n)$

实现

1
2
3
4
5
6
7
8
9
10
public MaxHeap(int[] arr){
    data = new ArrayList<>();
    for(int i:arr){
        data.add(i);
    }
    int lastParent  = getParent(data.size()-1);
    for (int i=lastParent;i>=0;i--){
        siftDown(i);
    }
}

练习

数组中的第K个最大元素

一运行超过16%的用户破防了