優先キューの基本データ構造(2)

要旨:今回提供する他の優先キューの基本操作【1】二叉スタックをフィルタリングすることは、ある要素を二叉スタックの優先構造に適合するノードに下げることである.

void PerLocateDown(Heap H,int i)
    //        
{
    int child;
    int FirstElement = H->Element[i];
    for(;i*2<= H->heapsize; i = child )
    {
        //for               
       //      
        child = i*2;
    if (child != H->heapsize && H->Element[child+1]<H->Element[child] )
        child++;
    if(FirstElement > H->Element[child])
    {
        //     ，    
        H->Element[i] = H->Element[child];
    }
    else
        break;//    
    }
    H->Element[i] = FirstElement;
}

【2】2つのフォークスタックを、スタック順序に適合する位置まで上昇させるようにフィルタリングする.

void PerLocateUp(Heap H,int i )
{
    //     【i】  
    int LastElement = H->Element[i];
    for(; LastElement < H->Element[i/2]; i /=2)
    {
        H->Element[i] = H->Element[i/2];
    }
    H->Element[i] = LastElement;
}

多くの場合、ノード要素の値を下げたり増やしたりする必要があるが、値を下げた後、フィルタリングを行うべきである.切り上げた後、濾過を行うべきだ.

void DecreaseKey(int P,int delta,Heap H)
{
    if (delta < 0 )
        delta =  -1*delta;
    if(P<=H->heapsize)
    {
        H->Element[P] -= delta;
        PerLocateUp(H,P);
    }
    else
    {
        puts("the Position is too large");
        exit(1);
    }
}

最後に、スタックを作成する操作である.最も容易に考えることができる方法は、連続的にN回の挿入操作(このような操作にはNlognの時間境界がある)を行うことである.しかし、時間界をO(N)にする方法はあるのだろうか.実はあります.{1}まずすべての所望のデータを直接挿入し,これにはO(N)の時間がかかる.次に、最後から2番目の層から始まるすべてのノード(N/2)をフィルタリングし、すべての比較回数もO(N)であることが証明される.

Heap BuildHeap(int *A,int N)// N      H 
{
    Heap H = Initialize(N);
    H->heapsize = N;
    for(int i = 1;i <= N;i++)
        H->Element[i] = A[i-1];
    for(int j = N/2;j>=1; j --)
        PerLocateDown(H,j);
    return H;
}

[5]最後の操作は、最小のノードではなく固定ノードを削除することである.そこで、まずDecreasekeyで操作を最小にする、その後DeleteMin操作で削除する.

void Delete(int P,Heap H)
{
    int delta = H->Element[P] - H->Element[1] + 1;//delta  key H->Element[1] 
    DecreaseKey(P,delta,H);
    DeleteMin(H);
}