二叉堆

发表于

二叉堆是一种支持插入，删除，查询最值的数据结构

它是一棵满足堆性质的完全二叉树，树上的每一个节点都有权值

如果树上的每一个节点都小于等于其父亲节点的权值，就是大根堆。反之，就是小根堆。

根据完全二叉树的性质，采用层次序列存储方式，直接用一个数组保存二叉堆。

层次序列存储，就是逐层从左到右依次编号，把编号作为该节点的下标。这种存储方式中，父节点的编号等于子节点的编号除以2，左子节点编号为父节点的乘2，右子节点的为左子节点的+1

下面以大根堆的相关操作作为范例

插入

在插入新节点时，先将其直接放在存储二叉堆的数组末尾，再通过不断地交换使其向上调整，直至满足性质。

时间复杂度O(log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int heap[size],n;
void up(int p){
    while(p>1){
        if(heap[p]>heap[p/2]){
            swap(heap[p],heap[p/2]);
            p/=2;
        }
        else break;
    }
}
void insert(int val){
    heap[++n]=val;
    up(n);
}

返回最值

根据性质，堆顶的是最值

1
2
3
int gettop(){
    return heap[1];
}

移除堆顶

把堆顶heap[1]与存储在数组末尾的heap[n]交换，然后令n减1移除数组末尾节点，最后向下调整

时间复杂度为O(log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void down(int p){
    int s=p*2;
    while(s<=n){
        if(s<n&&heap[s]<heap[s+1])++s;
        if(heap[s]>heap[p]){
            swap(heap[s],heap[p]);
            p=s;s=p*2;
        }
        else break;
    }
}
void delete(){
    heap[1]=heap[n--];
    down(1);
}

移除

移除下标为p的位置，与移除堆顶类似，但需要向上和向下调整

1
2
3
4
void remove(int p){
    heap[p]=heap[n--];
    up(p),down(p);
}