[TIL] 자료구조 - TrickleDown

※ TrickleDown 함수

- 루트 제거 과정을 코드로 작성하면 다음과 같습니다.

public E remove(){
	E tmp = array[0];
    swap(0, lastposition--); // 루트와 마지막 노드를 바꿔주고 lastposition 을 줄여 배열에서 제거한다.
    trickleDown(0);
    return tmp;
}

public void trickleDown(int parent){
	int left = 2*parent + 1;
    int right = 2*parent + 2;
    // 마지막에 왼쪽 자식이 클 때
    if (left == lastposition && (((Comparable<E>)array[parent]).compareTo(array[left])<0){
    	swap(parent, left)
        return;
    }
    // 마지막에 오른쪽 자식이 클 때
    if(right == lastpostion && (((Comparable<E>)array[parent]).compareTo(array[right])<0){
    	swap(parent, right)
        return;
    }
    // 마지막에 부모가 클 때
    if(left >= lastposition || right >= lastpositon)
    	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);
    }
}