基本数据结构--堆(Heap)-蒲公英云

基本数据结构--堆(Heap)

堆：是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

性质：

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

把堆当做数组存储，堆里的元素有上浮，下沉操作，(上浮，下沉过程尽量满足最小堆或最大堆的性质，最小堆元素下沉的的过程往较大的儿子方向沉)

1、初始化堆，相当于建立一个完全二叉树，但在末尾每次添加元素后都要进行比较，上浮。

2、添加元素，往数组的最后面添加，然后进行上浮操作。

3、删除堆顶，堆顶元素与最后一个元素交换，删除最后一个元素，然后进行下沉操作。

Shift_down( i , n )    //n表示当前有n个节点
{
    while( i * 2 <= n)
    {
        T = i * 2 ;
        if( T + 1 <= n && 堆数组名[ T + 1 ] < 堆数组名[ T ])
            T++;
        if( 堆数组名[ i ] < 堆数组名[ T ] )
        {
           swap( 堆数组名[ i ] , 堆数组名[ T ] );
            i = T;
        }
        else break;
}
Shift_up( i )
{
    while( i / 2 >= 1)
    {
        if( 堆数组名[ i ] < 堆数组名[ i/2 ] )
        {
            swap( 堆数组名[ i ] , 堆数组名[ i/2 ]) ;
            i = i / 2;
        }
        else break;
｝