優先キューの二叉スタックとdスタック

6246 ワード
データ構造(C)
フォークスタックの概要
普段言っている山は、何の修飾もしていないと、一般的に二叉の山を指します.二叉木と同様に,スタックにも二つの性質,すなわち構造性とスタック順序性がある.AVLツリーのように、スタックに対するこの操作は、両方の性質のうちの1つを破壊する可能性があるため、スタックの操作は、スタックのすべての性質が満たされるまで終了しなければならない.
こうぞうせい
スタックは完全に満たされた二叉木で、完全な二叉木は規則的であるため、ポインタを必要とせずに配列で表すことができます.下図に示すように、図2の配列は、図1のスタックに対応する.
                            
図1:フォークスタック図2:フォークスタックの配列格納
任意の位置i上の要素について、その左の息子は位置2 iにあり、右の息子は位置2 i+1にあり、その父はi/2にある.したがって,ポインタはここでは不要であるだけでなく,そのツリーを巡回するのに必要な操作も簡単である.この表現の唯一の問題は、最大のスタックサイズは事前に推定する必要があるが、典型的な場合には問題なく、図2のスタックサイズは13要素である.この配列には位置0があり、哨兵として用いられ、後述する.
したがって、スタックのデータ構造は、最大値を表す整数と現在のスタックのサイズの配列から構成されます.コードは次のとおりです.
struct HeapStruct
{
	int Capacity;
	int Size;
	ElementType *Elements;
};

スタックの性質
操作を迅速に実行できる性質はスタックシーケンス性である.1つのスタックでは、各ノードXについて、Xの親のキーワードはXのキーワードよりも小さく(または等しい)、ルートノードは除外される(ルートノードには父親がいない).図3において、左側はスタックであり、右側は(破線はスタックの性質が破壊されたことを示す).
図3:2本の完全な二叉木
きほんそうさ
Insert(挿入):
1つの要素Xをスタックに挿入するには、次の空き位置に正孔を作成します.そうしないと、スタックは完全なツリーではありません.この正孔にXを入れることができれば、挿入は完了する.そうでなければ、正孔の親ノード上の要素を正孔に移動し、正孔は根の方向に一歩進みます.このプロセスは、Xが正孔に入れられるまで続けられる.図4は、14を挿入するために、14を挿入することによってスタックの次の利用可能な位置に正孔を確立し、14を挿入することによってスタックシーケンス特性が破壊されるため、31を正孔に移動し、図5は、14の正確な位置が見つかるまで、この戦略を継続することを示す.
               
図4:正孔を作成し、正孔を図5:14を前のスタックに挿入する残りの2つのステップ
この戦略を上考と呼ぶ.新しい要素は正しい位置を見つけるまでスタックの中で考慮します.次のコードを使用すると、簡単に実現できます.
void Insert( ElementType X, PriorityQueue H )
{
	if (IsFull(H)){
		printf("Priority queue is full!");
		return;
	}
	int i;
	for (i = ++H->Size; H->Elements[i/2] > X; i /= 2){
		H->Elements[i] = H->Elements[i/2];
	}
	H->Elements[i] = X;
}

挿入するエレメント・師団の新しい最小値は、常に先頭に押され、ある時点でiが1になるように、プログラムをwhileループから飛び出す必要があります.もちろん、明確なテストでこれを行うことができます.しかし、ここではwhileサイクルを終了させるために小さな値を位置0に置くことを採用しています.この値はスタック内の任意の値より小さくなければなりません.マークや哨兵と呼ばれています.これはチェーンテーブルのヘッダノードの使用に似ています.このタグを追加することで、ループのたびにテストを実行することを回避します.これは簡単な空間交換ポリシーです.
DeleteMin(最小要素を削除):
最小元を見つけるのは簡単です.難しい部分は削除です.最小要素を削除すると、ルートノードに正孔が生成されます.スタックに1つの要素が少なくなったため、ペアの最後の要素Xはスタックのどこかに移動する必要があります.Xを正孔に入れることができれば,DeleteMinは完成する.しかし、これは一般的に不可能なので、正孔の2人の息子のうちの小さい人を正孔に移し、正孔を下に押して、Xが正孔に入れられることを知っています.したがって,我々のやり方は,根から末っ子を含む経路に沿った正しい位置にXを置くことである.
図6はDeleteMin以前のスタックを示しており、13を削除した後、私たちは正確に31をスタックに入れなければならない.31は正孔に入れられない.これはスタック順序の性質を破壊するため、私たちは小さい息子14を正孔に入れ、同時に正孔を1層下に下げ、この過程を繰り返し、19を正孔に入れ、より次の層に新しい正孔を建て、26を正孔に入れなければならない.底層にまた新しい正孔を確立し,最後に31を正孔に入れることができた.この戦略を下慮と呼ぶ.
                    
図6ルートに正孔図7を作成する:正孔を1層スライドさせる
 
図8:正孔が底層に移動し、31を挿入する
コード実装
ヘッダファイル:binheap.h 
typedef int ElementType;

#ifndef _BINHEAP_H
#define _BINHEAP_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize( int MaxElements );
void Destroy( PriorityQueue H );
void MakeEmpty( PriorityQueue H );
void Insert( ElementType X, PriorityQueue H );
ElementType DeleteMin( PriorityQueue H );
ElementType FindMin( PriorityQueue H );
int IsEmpty( PriorityQueue H );
int IsFull( PriorityQueue H );

#endif

実装ファイル:binheap.c 
#include "binheap.h"
#include 
#include 

#define MinPQSize 10
#define MinData -32767	

struct HeapStruct
{
	int Capacity;
	int Size;
	ElementType *Elements;
};

PriorityQueue Initialize( int MaxElements )
{
	if (MaxElements < MinPQSize){
		printf("Priority queue is too small!
");
		return NULL;
	}
	PriorityQueue H;
	H = malloc(sizeof(struct HeapStruct));	//        ，      12  
	if (H == NULL){                         //  int 8   ，    4   
		printf("Out of space!");
		return NULL;
	}
	H->Elements = malloc(sizeof(ElementType) * (MaxElements + 1));   //             
	if (H->Elements == NULL){
		printf("Out of space!");
		return NULL;
	}
	H->Capacity = MaxElements;
	H->Size = 0;
	H->Elements[0] = MinData;	//      ，    ;
	return H;
}

void MakeEmpty( PriorityQueue H )
{
	H->Size = 0;
}

void Insert( ElementType X, PriorityQueue H )
{
	if (IsFull(H)){
		printf("Priority queue is full!");
		return;
	}
	int i;	//   0      ，  for          ：H->Elements[i/2] > X && i != 0
	for (i = ++H->Size; H->Elements[i/2] > X; i /= 2){	//         （   i/2 ），      X   
		H->Elements[i] = H->Elements[i/2];              // X   ，  X         ，  ，     
	}
	H->Elements[i] = X;
}

ElementType DeleteMin( PriorityQueue H )
{
	if (IsEmpty(H)){
		printf("Priority queue is full!");
		return H->Elements[0];
	}
	int i, child;
	ElementType MinElement, LastElement;
	MinElement = H->Elements[1];
	LastElement = H->Elements[H->Size--];

	for (i = 1; i * 2 < H->Size; i = child){		//            
		child = i * 2;
		if (child != H->Size && H->Elements[child] > H->Elements[child+1])
			++child;								//           
		if (LastElement > H->Elements[child])       //                ，          ，
			H->Elements[i] = H->Elements[child];    //            ，    ，      
		else                                        //          ，    
			break;
	}
	H->Elements[i] = LastElement;
	return MinElement;
}

ElementType FindMin( PriorityQueue H )
{
	if (!IsEmpty(H)){
		return H->Elements[1];	//  0      ，  -32767
	}
	printf("Priority queue is Empty!");
	return H->Elements[0];
}

int IsFull( PriorityQueue H )
{
	return H->Size == H->Capacity;
}

int IsEmpty( PriorityQueue H )
{
	return H->Size == 0;
}

void Destroy( PriorityQueue H )
{
	free(H->Elements);
	free(H);
}

d-スタック
二叉スタックは実現が簡単であるため,優先キューが必要な場合にはほとんどいつも二叉スタックを用いる.d-スタックは二叉スタックの簡単な普及であり、二叉スタックのように見えます.すべてのノードにd人の息子がいるだけだ(したがって、2-ヒープとも呼ばれる).下図は、3-ヒープを示しています.注意:d-ヒープは、2-ヒープよりもはるかに浅いため、Insert操作の実行時間を向上させます.ただし、大きいdについては、DeleteMin操作に時間がかかります.木は浅いですが、d人の息子のうちの最小は必ず見つけなければならないので、標準アルゴリズムを使用すると、d-1回比較するので、この操作の時間はに向上しました.dが定数であれば、当然、両方の動作の実行時間はO(logn)である.配列を1つ使用することもできますが、息子と父の乗算と除算には因子dがあり、dが2のべき乗でない限り、実行時間が大幅に増加します.これは、バイナリシフトによって除算と乗算を実現できないためです.Dスタックは理論的に興味深いが、削除回数よりも挿入回数が多く、優先キューが大きすぎてメモリを完全にロードできない場合にもdスタックが有用であり、この場合、dスタックはBツリーとほぼ同じ方法で機能する.
Find操作が実行できないことを除いて(対数で実行することを指す)、スタックの実現の最も明らかな2つの欠点は、2つのスタックを1つのスタックに統合することが困難であることである.この付加的な操作をMergeと呼ぶ.Merge操作の実行時間をO(logn)とする実装スタックの方法が多く存在し、以下の左式スタックで説明する.
PHPで初めてのWebアプリケーション開発　備忘録1
POJ 2044 Weather Forecast