힙에서 요소를 제거
무언가를 제거할 때 힙에서는 항상 루트에 있는 요소를 제거해야 한다
트리의 마지막 요소를 루트에 넣는다
-> 최대 힙 규칙에 어긋남
-> 적절한 위치를 찾을 때까지 계속 두 노드의 위치를 바꾼다
->두 자식 중 큰 노드와 교환하는 것이 포인트이다 (중요)
힙에서 제거할 수 있는 요소는 루트뿐이다
루트에 있는 요소를 지우면 구멍이 생기고, 이를 메워야 한다
-> 힙에있는 마지막 요소를 넣는다
->자식 노드보다 작은지 확인 후 위치를 바꿔야 한다
자식 노드중에서 큰 수와 위치를 변경해야 한다
이러한 과정을 "trickle down"이라고 한다
trickle down 과정이 끝나는 경우
- lastposition 변수보다 큰 경우
-> 현재 위치에서 자식 노드가 하나만 있을 수도 있다는 점을 고려해야 한다
코드로 구현
public E remove() {
E temp = array[0]; //루트에 있는 요소 remove 함수가 끝나면 반환
//바꾸는 과정
swap(0, lastposition--);
trickleDown(0);
return tmp;
}
/*
swap(0, lastposition--);
add함수는 먼저 증가시킨 후 사용했지만
이 경우 lastposition을 먼저 사용 후 감소했다
*/
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 &&
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);
}
}
힙 정렬 알고리즘
힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 말한다
임의의 노드 두 개를 골라 순서를 교환한 후 큰 수의 노드를 삭제한다
-> 임의의 숫자를 나열하고 힙 규칙에 맞게 TrickleDown을 반복하면 정렬된다
시간 복잡도 : O(n log n) //n개의 숫자를 log n개의 숫자와 비교
-> 두 수를 비교해서 하나를 고르는 방식으로 숫자를 골라낸다
데이터의 복사본을 만들필요가 없다는 장점이 있다
-> 배열에서 시작해서 배열에서 끝난다
완전트리와 정트리
- 완전트리
마지막 줄을 제외하고 잎 모든 노드가 두 개의 자식 노드를 가지고 있고
마지막 줄이 왼쪽에서 오른쪽 순서로 채워져 있는 트리를 말한다 - 정트리
모든 잎 노드가 두 개의 자식 노드를 가지고 있고
모든 잎이 같은 레벨에 있는 트리를 말한다
트리를 순회하는 법
트리의 어떤 노드로 가서 일을 해야하는 지를 가정한다
트리의 노드를 돌아보는 방법
1. 전위 순회 (Pre order traversal)
루트 노드에 간 다음 왼쪽 자식 노드로 간 후 오른쪽 자식 노드로 간다
루트 -> 왼쪽 노드 -> 오른쪽 노드
2. 중위 순회 (In order traversal)
왼쪽 자식을 먼저 방문한 후 루트를 방문하고 오른쪽 자식 노드로 간다
왼쪽 노드 -> 루트 -> 오른쪽 노드
3. 후위 순회 (Post order traversal)
왼쪽 자식 노드에 갔다가 오른쪽 노드로 간 다음 루트로 간다
왼쪽 노드 -> 오른쪽 노드 -> 루트
4. 너비 우선 순회 / 레벨 우선 순회
가장 위에 있는 노드에서 시작하여 레벨에 따른 순회 순서를 거친다
레벨 : 트리의 노드를 가로로 순회한다
대부분의 경우 전위, 중위, 후위 순회를 사용하며
현재 정리한 강의의 순회 방식은 재귀 방식을 사용한다
**재귀 방식 : 왼쪽 자식 노드에 대해서 어떤 일을 수행한 다음,
오른쪽 자식 노드에 대해서 일을 수행하고, 마지막으로 현재 노드에서 일을 수행한다는 의미이다