CH 9-2ヒップホップの実施と優先順位キューの完了

この書き込みは、ユン・スンウ先生の資料構造講座を聞いた後、内容を整理したものだ.
自分の復習のために書いた文章なので、深く勉強するために本を買ったり聞いたりすることをお勧めします.
序曲
優先順位はお尻です.お尻は優先キューです.すべてX
優先キューで使用するツールはhipです.
お尻の特性が優先順位キューを表しているからです.
これからは、お尻を利用して優先順位キューを実現する方法について説明します.
(1)HIPにおけるデータ格納プロセス

仮定値が低いほど優先度が高くなります
親ノードの優先度はいずれもサブノード以上であり、完全なバイナリツリーであるため、図左上隅のバイナリツリーはhipである.
データの格納が困難なのは,完全に異性のツリー構造が破壊されず,規則も破壊されないためである.
したがって、データをランダムに受信し、完全なバイナリツリーの次のノードとして格納することは不可能である.
したがって、画像と同じ記憶プロセスが経験される.
仮に3が入ってきたとします.

3を完全なバイナリツリーの最後のノード位置

に保存する.

親ノードと子ノードのサイズ比較

親ノードが子ノードより大きい場合、親ノードと子ノードの位置が変更されます.

親ノードが子ノード2より小さいまで.わあ.繰り返し

(2)HIPからデータを削除するプロセス

優先度Qの角度から削除したと言うべきです.
お尻からデータを削除するだけで、あなたの観点が分からない場合は、最後のノードから逆順に削除します.
hipという資料構造が維持されるからです.
そこで、優先順位キューを実現するためのデータ消去プロセスを見てみましょう.

は、まずルートノード上のデータを返し、

を削除する.

完全バイナリツリーの最後のノードをルートノード

とする.

挿入プロセスのように、ルートノードは自分の位置

を見つける.
この場合、2つのサブノードの優先度の高いデータを比較するだけでアクセスできます.
この2つのノードでは、優先度の低いデータと場所を変更すると、優先度の低いノードが親ノードになる可能性があります.
(この部分に慣れていないと実現してしまい、結局大きな鼻を傷つけてしまいましたハハ…)
このとき,ルートノードに来る無条件が最も優先度の高いノードとなる.
お尻のルールを満たすとしたら
ルートノードの左側のノードは、左側のサブツリーの中で最も優先度の高いノードです.
ルートノードのrightノードは、右側のサブツリーで最も優先度の高いノードです.
この2つより優先度が高い場合、優先度が最も高いことが保証されるからです.
(3)挿入と削除のパフォーマンスの評価
ツリーはlog 2 nと呼ぶこともできるし、汎用とも言える.log 2 nはツリーの中でツリーの性能を表し、log 2 nは通常非常に満足できる性能である.
今他の資料構造と比較してみます.
配列に基づくデータ挿入の時間的複雑さはO(n)である.n個のデータを比較または移動するためです.
接続リストに基づくデータ挿入の時間的複雑さもO(n)である.ウォースターはn個を比較する必要があるからだ.
では、hipベースのデータを挿入する時間の複雑さはどのくらいですか?
2のn次方-1がデータの総数の場合、levelはn
したがって,最悪の場合,データ挿入の時間的複雑さはlog 2 nに比例する.
(定数部分を削除)
//より正確には、データ個数が2の(n-1)平方または2のn平方-1以下の場合、演算回数が最大nとなるため、log 2(n+1)の「アップグレード」が最大演算回数となり、big-Oはlog 2 nといえる.
また,配列とリストのデータ削除はいずれもO(1)であり,先頭のデータを削除するだけでよいからである.
HIPベースのデータ削除後、HIP条件を満たすために完全バイナリツリーを再生成する必要があります.
削除する場合,時間的複雑度はO(log 2 n)である.
しかし,データ数の増加に伴って増加する演算回数を考えると,2*log 2 nは当然nよりずっとよい.
(4)アレイに基づくHIP実装に必要な知識
通常、HIPを実装する場合、すなわちバイナリツリーを実装する場合、接続リストは通常使用される.
直観的に見ると、もっと適切だからです.
しかし配列を利用して実現するのもそれほど難しくない.
実際、hipの大部分は配列を利用して実現されている.
接続リストに基づいてhipを実装する場合、新しいノードをhipの最後の位置に追加する必要があるが、この最後の位置を知るのは難しいからである.
(言い換えれば、データ個数を考慮した空きデータの個数をバイナリ数に変換し、初期の1万本のノードに入ると見なし、残りのビット数は1,左0,右にシフトする.)
親ノードのインデックス値はkです.
サブノードのインデックス値はそれぞれ2 k,2 k+1である
//levelnの一番左のインデックスの値はxです.
level n+1の一番左のインデックスの値が2 xの場合
x+1左側のサブノードのインデックスは当然2 x+2であり,当然2(x+1)である.
x+kの左側のサブノードのインデックスは当然2 x+2 kである.
level 0の要素数は1です.バイナリツリーであるためです.
そして2...
等比級数の和により,総数2の(n+1)平方−1
従って、level nの次のレベル、すなわちlevel(n+1)の最初のインデックスは2の(n+1)平方−1+1であるため、2の(n+1)平方である
したがって,level n+1の最左インデックスの値もlevel nの最左インデックス値*2の仮定を成り立たせる.
最初のローの最初のインデックスは1です.
次の行の最初のインデックスは2であるため、成立します.
従って、上図に示すように、配列においてバイナリツリーを実現することができる.
そしてこの原理に基づいて.
サブノードのインデックス値はkです.
親ノードのインデックス値をk/2に設定するだけです.(除算は整数除算)
(5)ヒップホップ実装ヘッダファイル
#ifndef SIMPLE_HEAP_H
#define SIMPLE_HEAP_H
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 128
typedef char HData;
typedef int Priority;
typedef struct _heapElem
{
Priority pr;//値が小さいほど優先度が高くなり、通常hipはmin heapです.
HData data;
} HeapElem;//データと優先度情報を分離する->これは唯一正しいものではありません.
typedef struct _heap
{
int numOfData;//データの数
HeapElem heapArr[HEAP_LEN];//アレイベースの実装
} Heap;
/*Heapに関する演算**/
void HeapInit(Heap ph);//hip初期化
int HIsEmpty(Heap ph);
void HInsert(Heap ph, HData data, Priority pr);//お尻にデータを挿入
HData HDelete(Heap ph);//データ消去をHIPから削除し、最も優先度の高いデータを削除するように定義します.
#endif
//テーマはhipの実装ですが、優先順位キューを完了することを目的としているので、hipの実装というより、hipを利用して優先順位キューを実現します.
(6)hip実現の内容を熟知する

ヒップは完全バイナリツリーです.

HIPの実装は配列に基づいており、インデックスが0の要素は空である.

ノードの固有番号は、ノードストレージアレイのインデックス値となる.

hipに格納されているノードの数は、最後のノードの固有番号と一致します.

の優先度を表す整数値が小さいほど、優先度が高いと仮定する.
△義務ではありません.

(7)私が実現したヒップホップ

#include <stdio.h>
#include "SimpleHeap.h"

void HeapInit(Heap* ph)
{
	ph->numOfData = 0;
}

int HIsEmpty(Heap* ph)
{
	if (ph->numOfData == 0) return TRUE;
	else return FALSE;
}

void HInsert(Heap* ph, HData data, Priority pr)
{
	HeapElem new;
	HeapElem temp;
	int cur;
	new.data = data;
	new.pr = pr;
	ph->numOfData++;
	ph->heapArr[ph->numOfData] = new;
	cur = ph->numOfData;
	while (cur != 1)
	{
		if (ph->heapArr[cur / 2].pr <= pr) break;
		else
		{
			temp = ph->heapArr[cur / 2];
			ph->heapArr[cur / 2] = new;
			ph->heapArr[cur] = temp;
			cur /= 2;
		}
	}
}

HData HDelete(Heap* ph)//중요한건 자식노드 중 우선순위가 높은 노드와 우선순위를 비교해서 자리바꿈해야한다는 것이다. 안 그러면 우선 순위가 낮은 노드가 부모 노드가 될 수 있기 때문.
{
	if (ph->numOfData == 0)
	{
		return -1;
	}
	HData DData;
	int cur = 1;
	HeapElem temp;
	DData = ph->heapArr[1].data;
	ph->heapArr[1] = ph->heapArr[ph->numOfData];
	int pr = ph->heapArr[1].pr;
	ph->numOfData--;
	while (2 * cur <= ph->numOfData)// 이 부분을 잘못 건드려 디버깅을 수없이 했다.
    //numOfData가 2*cur이하이면 heapArray[2*cur]에 비교가능한 데이터가 있다는 것이므로 반복문에 진입하여야 한다. 2*cur + 1이 numOfData에 포함되지 않으므로 어차피 비교대상 자기자신이므로 2*num에 저장된 데이터보다 우선순위가 높으면 자기자신과 자리를 바꾸므로 변경되지 않을거고 낮으면 어차피 비교대상이 되지 않는다.
	{
		if (ph->heapArr[2 * cur].pr <= ph->heapArr[2 * cur + 1].pr)
		{
			if (pr > ph->heapArr[2 * cur].pr)
			{
				temp = ph->heapArr[2 * cur];
				ph->heapArr[2 * cur] = ph->heapArr[cur];
				ph->heapArr[cur] = temp;
				cur = 2 * cur;
			}
			else break;
		}
		else
		{
			if (pr > ph->heapArr[2 * cur + 1].pr)
			{
				temp = ph->heapArr[2 * cur + 1];
				ph->heapArr[2 * cur + 1] = ph->heapArr[cur];
				ph->heapArr[cur] = temp;
				cur = 2 * cur + 1;
			}
			else break;
		}
	}
	return DData;
}

HDelete関数の途中でheapArray[numOfData]の優先度をINT MAXに変更し、上記のデータとの変更を回避しました.
どうせ比較対象は自分なので、入れなくても大丈夫です.
もう1つの教訓->簡単に表示できるテストケースを作成してデバッグすることに慣れています.