[자료구조] 자바 힙 소개 및 구현

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

 

이번 포스팅에서는 이진 트리 자료구조로 구현하는 힙에 대해 알아본다. 트리를 간단하게 소개하고, 힙에 노드를 추가하고 제거하는 과정에 대해 알아보고 trickle up과 trickle down을 구현한다.

---

트리 소개

트리는 나무 형태로 노드를 연결해서 데이터를 저장하는 자료구조이다. 특정 요소를 찾는데 시간복잡도가 O(log n)이기 때문에 탐색이 목적일 때 데이터를 트리 형태로 저장하는 것이 효율적이다. 예시로 디렉터리 구조, 검색 엔진, DBMS, 라우터 알고리즘이 있다.

 

Root : 트리의 시작, Linked List를 Head로 접근하는 것처럼 트리는 Root로 접근한다.

Leaf : 자식 노드가 없는 노드

Edge : 두 노드를 연결하는 선. 뿌리로부터 간선의 수로 Level을 정한다.

Level : log(n+1) -1

 

완전이진트리, 완전정트리

 

완전트리와 정트리

이진 트리는 자식 노드가 최대 두 개인 노드로 구성된 트리이다. 이진트리에는 위처럼 Complete tree, Full tree가 있다.

 

Complete tree : leaf가 아닌 모든 노드가 2개의 자식노드를 가지고 있다. 마지막 row는 왼쪽에서 오른쪽 순서로 채운다.

Full Tree : leaf가 아닌 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리이다.

---

힙 소개, 추가와 제거

완전이진트리를 기반으로 한 자료구조이다. 최대값 및 최소값을 빠르게 연산하기 위해 고안된 자료구조이다.

 

최대 힙 : Root에 최대값을 저장한다. 부모 노드가 자식 노드보다 커야한다.

최소 힙 : Root에 최소값을 저장한다. 부모 노드가 자식 노드보다 작아야한다.

 

노드 추가

1. 비어 있는 공간에 노드를 추가한다.

2. Trickle Up : 부모 노드보다 큰 숫자인지 확인하고, 크다면 두 노드를 바꾼다.

 

 

노드 제거

항상 루트부터 제거한다.

1. 루트를 제거한다.

2. 트리의 마지막 요소를 루트에 넣는다.

3. Trickle Down : 루트에서 시작해서 두 자식 중 큰 노드와 바꿔 힙의 규칙을 만족한다.

 

트리의 마지막 요소를 루트 자리에 넣어주는 이유는, 트리의 마지막 요소를 루트에 넣지 않고 자식 노드를 하나씩 올려주는 과정을 반복하면, 최악의 결과로 완전이진트리를 만족하지 못해서 트리를 재구성해야하는 상황이 생길 수도 있다.

---

Trickle Up, Trickle Down

완전이진트리의 경우 부모노드와 자식노드는 다음의 관계를 갖는다.

children = 2 * parent + 1, 2 * parent * 2

parent = float((child-1)/2)

 

Trickle Up

int lastposition
E[] array = (E[]) new Object[size];

public void add(E obj) {
    array[++lastposition] = obj;
    trickleUp(lastposition);
}
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 (array.((comparable<E>array[position]).compareTo(array[parent]) > 0)
        swap(position, parent);
        trickleUp(parent);
    }
}

 

Trickle Down

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 
        && ((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)
    if (left >= lastposition || right >= lastpositin)
        return;
    if (array[left] > array[right] && array[parent] < array[left]) {
        swap(parent, left);
        trickleDown(left);
    elif (array[parent] < array[right]) {
        swap(parent, right);
        trickleDown(right);
    }
}

 

힙에서 값을 삭제할 때, 기존 root 노드를 없앤다고 했다. 루트 노드를 array에서 삭제하지 않고 swap 함수를 이용해서 배열의 마지막 위치로 보내고 lastPosition을 줄인다. 정보를 없애는 대신 remove를 반복하면 오름차순으로 정렬할 수 있다는 장점도 있다.

 

힙 정렬의 시간복잡도는 O(nlogn)인데, 모든 숫자(n개)를 trickle down을 반복(logn개와 비교)하기 때문이다. 숫자들의 순서를 바꿔 정렬하기 때문에 복사본을 만들 필요 없다는 장점도 있다.