4-2) 힙 - TrickelUp, TrickeDown, 정렬

 

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

 

트리 순회

중위 순회 - 왼쪽, 루트, 오른쪽 순서로 순회

전위 순회 - 루트, 왼쪽, 오른쪽 순서로 순회

후위 순회 - 왼쪽, 오른쪽, 루트 순서로 순회

레벨 순회 - 레벨 순서대로 순회

 

 

TrickelUp

완전이진트리에서 레벨 순회식 노드의 위치는 다음과 같은 성질을  가진다.
children -  2 * parent + 1  // 또는 //   2 * parent + 2
parent - floor(내림)( (child-1) / 2 )  

 

이진 힙을 코드로 구현하기 위해서는 배열(0~..)을 만들어 인덱스를 노드 위치로 하여 이러한 규칙을 사용할 수 있다.

int lastposition; // 배열에서 어디까지 요소를 넣었는지 기록: 힙이 시작점에서 얼마나 떨어져 있는가
E[] array = (E[]) new Object[size];
public void add(E obj){	
	array[++lastposition] = obj; // 1. 사용 가능한 다음 위치에 노드 추가
	trickleup(lastposition); // 2. trickle up
}
public void swap(int from, int to){
	E tmp = array[from];
	array[from] = array[to];
	array[to] = 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);		// 현재 포지션 값이 부모보다 크다면 swap
		trickleup(parent);	//다시 확인
	}
}

 

TrickeDown

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==lastposition && (((Comparable<E>)array[parent]).compareTo(array[right])<0){
		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);
	}
}

 

힙 정렬 알고리즘

힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 한다. 임의의 숫자들을 나열하고 힙 규칙에 맞게 TrickleDown을 반복하면 그 숫자들이 정렬된다.

 

힙 정렬 알고리즘의 시간 복잡도는  O(n log n) 이다.  두 수를 비교해서 하나를 고르는 방식으로 숫자를 골라내기 때문이다. (총 n개의 숫자를 logn개의 숫자와 비교)

 

한 배열 안에서 숫자들의 순서를 바꿔 지우면 정렬이 끝나기 때문에 데이터의 복사본이 필요 없다는 점이 힙 정렬의 장점으로, 힙 정렬은 표준적인 정렬 작업 알고리즘이다.