私はこの前李金樹とその種類について議論した.概念を知っている以上、運用を学ぶべきだ.
それを利用したHip-Tree Heap Treeを見てみましょう.

ヒップホップって何?

配列内の要素をソートする構造と見なすことができます.これは、優先度Q Priority Queueを実施するための重要な概念である.
優先度キューは、キューQueueと同じ先頭のデータ構造であり、優先度が最も高い(昇順であれば最小)データを最初に削除する.
このため、キューの配列をhipツリーに構成する必要があります.まずはお尻をご紹介しますが、

完全バイナリツリーCBT

ノードの親ノードの優先度は、その子ノードよりも高くなければなりません.

お尻のタイプ

大きく分けて、最大HIP-Max Heapと最小HIP-Min Heapの2種類があります.

最大ヒップ

親ノードのキー値が子ノードのキー値以上である完全バイナリツリー

最小ヒップ

完全バイナリツリー、親ノードのキー値が子ノードのキー値以下または等しい

インプリメンテーション

臀部を貯蔵する標準的な資料構造はArray配列である.

ノード関係

0-base

左サブアイテム:(親インデックス)x 2+1
右子:(親インデックス)x 2+2
親:(子索引)/2-1
実装を容易にするために、0アレイも使用しません.それでは、関係は以下の通りです.

1-base

左サブアイテム:(親インデックス)x 2
右子アイテム:(親インデックス)x 2+1
親:(子索引)/2

挿入

ヒップホップに新しい要素が追加されると、最後に新しいノードが挿入されます.

新しいノードは、親ノードと優先度を比較し、アップグレードします.

Hip Sot Heap Sortは、最大Hipを使用してソートされる典型的なソートロジックの1つである.だから私は降順に論理を書きます.
参考までに0-base

void insert(T x)
{
	m_heap[m_heapSize] = x;
	for(int i = m_heapSize; i > 0; i /= 2)
	{
		if(m_heap[i] > m_heap[i / 2])
		{
			swap(m_heap[i], m_heap[i / 2]);
		}
		else
		{
			break;
		}
	}
	++m_heapSize;
}

削除

hip(ここでは最大hip)では、最大値がルートノードなので、ルートノードを削除します(結果を表示するには、削除する前に変数に保存してから返します).

削除されたルートノード

に最後のノードをインポートします.

ヒップホップを再構成します.

T pop()
{
	T ret = m_heap[0];
	m_heap[0] = m_heap[m_heapSize];
	for(int i = 0; i * 2 < m_heapSize;)
	{
		// 두 자식들보다 큰 경우
		if(m_heap[i] > m_heap[i * 2 + 1] && m_heap[i] > m_heap[i * 2 + 2])	
			break;
		// 좌측이 더 큰 경우
		else if(m_heap[i * 2 + 1] >= m_heap[i * 2 + 2])
		{
			swap(m_heap[i], m_heap[i * 2 + 1]);
			i = i * 2 + 1;
		}
		// 우측이 더 큰 경우
		else
		{
			swap(m_heap[i], m_heap[i * 2 + 2]);
			i = i * 2 + 2;
		}
	}
	--m_heapSize;
	return ret;
}

Heapify

hipを構成するメソッド名をパラメータとして標準インデックスを入力し、このときからhipを構成する論理と見なすことができます.n変数があり、해당 인덱스 - 1のみを構成すればよい.このように論理を展開するのは,臀部ソートに適用できるためである.
hipソートの基本論理は:

アレイ、最大臀部を構成します.

最大臀部の

本のノードと最後のノードを置き換えます.
2-1. これは、最後の値が整列していることを示します.
2-2. したがって、整列したノードに加えて、ヒップを組織し、1,2を繰り返して整列した配列を得ることもできる.

Heapify、HeapifyからなるInsert及びPopは以下の通りである.

void insertByHeapify(T x)
{
	m_heap[m_heapSize++] = x;

	for(int i = m_heapSize / 2 - 1; i >= 0; --i){
		heapify(m_heapSize, i);
	}
}

T popByHeapify()
{
	T ret = m_heap[0];
	m_heap[0] = m_heap[m_heapSize - 1];
	m_heap[m_heapSize--] = 0;
	
	heapify(m_heapSize, 0);

	return ret;
}

void heapify(int n, int i)
{
	int parent = i;
	int lChild = i * 2 + 1;
	int rChild = i * 2 + 2;

	if(lChild < n && m_heap[parent] < m_heap[lChild])
		parent = lChild;
	if(rChild < n && m_heap[parent] < m_heap[rChild])
		parent = rChild;

	if(i != parent)
	{
		swap(m_heap[parent], m_heap[i]);
		heapify(n, parent);
	}
}

使用例は次のとおりです.
ヒップホップの例