Java-자료구조 4주차 Heap 4 - 4 ~ 6

김메로·2022년 8월 23일

Java로 배우는 자료구조

목록 보기

13/24

4주차. 힙
4-4.TrickleUp 함수

완전이진트리로 노드의 위치는
-children: (2 x parent) + 1, (2 x parent) + 2
-parent: floor((child - 1) / 2)
로 모든 노드가 level 순서 정렬로 위치가 잡힌다.
ex)

<코드>

int lastposition; // 어디까지 요소를 넣었는지 위치를 알려줌
E[] array = (E[]) new Object[size];// 원하는 만큼 크기의 객체인 배열 생성
public void add(E obj){
	array[++lastposition] = obj; // 노드 추가
	trickleup(lastposition); //  trickle up
}

public void swap(int from, int to){
	// 보통 from이 child, to가 parent
	E tmp = array[from]; // 
	array[from] = array[to]; // to가 from이 있는 곳으로 이동
	array[to] = tmp; // from이 to가 있는 곳으로 이동
}

public void trickleup(int position){
	if (position == 0) // root: position = 0
		return;
	int parent = (int) Math.floor((position-1)/2) // parent 위치 
	if(((Comparable<E>)array[position]).compareTo(array.parent)>0) {
    // 부모와 현재 노드의 값을 비교(child > parent)한 뒤 실행 
		swap(position, parent);
		trickleup(parent);
	}
}

생각해보기)-위 코드에서 lastposition 변수를 사용하는 이유는 무엇인가요?

답: 완전이진트리로 2개씩 꽉 찬 트리 구조이기 때문에 노드가 추가된다면 마지막 위치에 추가해서 사용한다

4-5.TrickleDown 함수

노드의 위치는 tickle up일 때와 동일.
-children: (2 x parent) + 1, (2 x parent) + 2
-parent: floor((child - 1) / 2)

<코드>

public E remove(){
	E tmp = array[0];
	swap(0, lastposition--); // 루트(0)와 마지막 노드를 바꿔주고 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);
	}
}

생각해보기)-루트의 정보를 없애는 대신 swap 함수를 이용하여 제거하면 어떤 점이 좋나요?

답: 루트를 제거한 뒤, 마지막 위치에 놓인 수를 루트와 바꿔 연결하기 때문에 완전 이진 트리 구조가 유지된다

4-6.정렬

heap 정렬 알고리즘이란?
-정렬 전에 heap 생성 알고리즘(MAXHEAP)을 한다
-힙 규칙에 맞게 숫자의 순서를 맞추는 과정
-임의의 숫자들을 나열하고서 규칙에 맞게 Tickledown을 반복한다
-루트와 마지막 노드가 교체된 순간, 마지막 노드는 힙의 일부로 생각되지 않아 연결선을 끊는다
이유: 교체되는 순간, 마지막 요소를 나타내는 카운터가 감소
힙 정렬 알고리즘(설명 참고)
:https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%ED%9E%99%EC%A0%95%EB%A0%ACHeap-Sort
힙 관련 설명참조2: https://st-lab.tistory.com/225