Java教程

本文主要是介绍堆,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

堆简介

堆是一棵完全二叉树,其每个节点都有一个键值,且每个节点的键值都大于等于/小于等于其父亲的键值。

每个节点的键值都大于等于其父亲键值的堆叫做小根堆,否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

(小根)堆主要支持的操作有:插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

用数组模拟小根堆

小根堆的特点:每个点都小于等于左右儿子,因此堆顶是最小值。

存储:
堆顶:1
x的左儿子:2x,右儿子:2x+1.

两个核心操作:
up(x)和down(x).
其中,down(u)使h[u]处的点往下沉到形成堆,up(u)使u处的点往上走至形成堆为止。

以上的操作组合可以完成下列操作:
(1)插入一个数:heap[++cnt]=x;up(cnt);
(2)求集合中的最小值:heap[1]
(3)删除最小值:heap[1]=heap[cnt];down(1);cnt--;
(4)删除任意元素:heap[k]=heap[cnt];cnt--;down(k);up(k);
(5)修改任意元素:heap[k]=x;up(k);down(k);

代码模板

朴素版堆

//down(x)
void down(int u){
    int t=u;
    if(2*u<=cnt&&h[2*u]<h[t]) t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t]) t=2*u+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
//up(x)
void up(int u){
    while(u/2&&h[u/2]>h[u]){
        swap(h[u],h[u/2]);
        u=u>>1;
    }
}
//o(n)建堆
 for(int i=n/2;i;i--) down(i);

带映射版

int h[N],ph[N],hp[N],cnt;
//hp[],ph[]存储的是映射关系
//带映射版swap
void heap_swap(int u,int t){
    swap(ph[hp[u]],ph[hp[t]]);
    swap(hp[u],hp[t]);
    swap(h[u],h[t]);
}
//down(x)
void down(int u){
    int t=u;
    if(2*u<=cnt&&h[2*u]<h[t]) t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t]) t=2*u+1;
    if(u!=t){
        heap_swap(u,t);
        down(t);
    }
}
//up(x)
void up(int u){
    while(u/2&&h[u/2]>h[u]){
        heap_swap(u,u/2);
        u=u>>1;
    }
}
这篇关于堆的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!