ヒップホップ

★お尻

HIPは完全なバイナリツリーに基づくデータ構造で、最低価格と最高価格を迅速に検索することを目的としています.
お尻には最大お尻(max heap)と最小お尻(minheap)があります.親ノードが子ノードより大きい場合は最大ヒップ、逆に最小ヒップです.最大の数字をルートディレクトリに表示するには、最大のお尻からでも、最小のお尻からでもかまいません.

種類

parent > children ⇒ MAX HEAP

parent < children ⇒ MIN HEAP

高さの計算

log 2(n+1)−1 log 2(n+1)−1 log 2(n+1)−1はheightと一致するため、ツリーにどれだけの要素があるかを知ることでツリーの高さを計算することができる.

追加と削除

お尻に新しいデータを追加または削除する場合は、お尻のルールを守らなければなりません.最大ヒップは、親ノードが子ノードより大きくなければならないことを示し、最小ヒップは子ノードが親ノードより大きくなければならないことを示します.

ノード

を追加

の下部にノードを追加します.

数値が

の親ノードより大きいことを確認し、そうであれば2つのノードを置き換えます.

ノード

を削除

のディレクトリを削除します.

ツリーの最後の要素

をルートディレクトリに入れます.

本から、ヒップホップ規則を満たすために、2つのサブノードの大きなノードを置き換えます.

何かを削除する場合は、お尻は常にルートディレクトリを削除する必要があります.

インプリメンテーション

// 힙 배열
E[] array = (E[]) new Object[size];
// 마지막 요소 위치 기록
int lastposition; 
// 힙 원소 추가
public void add(E obj) {
	array[++lastposition] = obj; // 1. 노드 추가
	trickleup(lastposition); // 2. trickle up
}
// 힙 원소 교환
public void swap(int f, int t) {
	E tmp = array[f];
	array[f] = array[t];
	array[t] = tmp;
}
// 힙 자식과 부모 크기 비교해서 정렬
public void trickleup(int position) {
	if (position == 0)
		return;
	int parent = (int) Math.floor((position-1)/2)
	if (((Comparable<E>) array[position]).compareTo(array[parent])>0) {
		swap(position, parent);
		trickleup(parent);
	}
}
// 힙 원소 삭제
public E remove() {
	E tmp = array[0];
    	// 마지막 인덱스를 줄여주어 실제 삭제한 값은 존재하지만 힙의 일부로 생각 안한다.
	swap(0, lastposition--); 
   	trickleDown(0);
	return tmp;
}
public void trickleDown(int parent) {
	int left = 2 * parent + 1;
	int right = 2 * parent + 2;
	// 마지막에 왼쪽 자식이 클 때
	if (left == lastposition && array[parent] < array[left]) {
		swap(parent, left)
		return;
	}
	// 마지막에 오른쪽 자식이 클 때
	if (right == lastposition && array[parent] < array[right]) {
		swap(parent, right)
		return;
	}
	// 마지막에 부모가 클 때
	if (left >= lastposition || right >= lastposition)
		return;
	// 왼쪽 자식이 클 때 혹은 오른쪽 자식이 클 때
	if (array[left] > array[right] && array[parent] < array[left]) {
		swap(parent, left);
		trickleDown(left);
	} else if (array[parent] < array[right]) { 
		swap(parent, right);
		trickleDown(right);
	}
}

ノードの位置には、次の性質があります.
children:(2∗parent)+1children: (2 * parent) + 1children:(2∗parent)+1 or (2∗parent)+2(2 * parent) + 2(2∗parent)+2
parent:floor((child−1)/2)parent: floor((child-1)/2)parent:floor((child−1)/2)

お尻の位置合わせ

hip規則に従って数字を並べ替えるプロセスをhip並べ替えアルゴリズムと呼ぶ.ランダムな順番の数字をお尻にしてお尻から1つ抜いてください最大値または最小値の順に減少するため、自動的にソートされます.
時間的複雑度は,データを入れる際の性能がO(logn)O(logn)O(logn)であり,減算する際の性能がO(logn)O(logn)O(logn)であることを示す.すべてのN個のデータを除いて並べ替えを行うため、臀部並べ替えの時間的複雑度はO(N87 logn)O(N*logn)O(N87 logn)である.