[자료구조] 엉덩이 아니고요. Heap입니다. 힙에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

 

(01) :: Define a Concept

힙은 항상 완전 이진 트리를 띄고 있는 자료구조입니다.

부모의 값이 항상 자식들의 값보다 크거나 작아야 하는 자료구조로 일종의 반정렬 상태를 유지하고 있습니다.

           ----10-------
           |           |
        --15--      --30-- 
        |    |      |    |
       40    50    100   40

 

(02) :: Property

힙은 두 가지 종류로 구분할 수 있습니다.

부모의 값이 항상 자식들의 값보다 큰 최대 힙(Max Heap), 부모의 값이 항상 자식들의 값보다 작은 최소 힙(Min Heap) 입니다.

힙은 이런 특성 덕분에 반정렬 상태(느슨한 정렬 상태)를 유지하고 있습니다. 

여기서 말하는 반정렬이란, 최대 힙을 기준으로 큰 값이 상위에 있고 작은 값이 무조건 하위에 있는 수준의 정렬을 말합니다.

 

# Max Heap
           ----100------
           |           |
        --40--      --50-- 
        |    |      |    |
       10    15     50   40
       
# Min Heap
           ----10-------
           |           |
        --15--      --30-- 
        |    |      |    |
       40    50    100   40

#1 최소 힙의 경우 최솟값을, 최대 힙의 경우 최댓값을 O(1)의 시간으로 찾을 수 있습니다.
#2 데이터의 삽입과 삭제는 O(logN)이 소요됩니다.

따라서, 최솟값을 기준으로 하는 문제나 최댓값을 기준으로 하는 문제에 직면했을 때는 힙 자료구조 활용하면 효율적입니다.

 

(03) :: Heap, How it works?

힙의 특성 부분에서 다룬 힙의 2가지 기능에 대해서 알아봅시다.

#1 최소 힙의 경우 최솟값을, 최대 힙의 경우 최댓값 찾는 경우 = O(1)
#2 데이터 추가하거나 삭제하는 경우 = O(logN)

#1의 경우, 최소 힙과 최대 힙의 루트 노드를 꺼내오면 되기 때문에 O(1) 밖에 소요되지 않습니다.

 

#2의 경우, 힙의 구조를 계속 유지하기 위해 추가 및 삭제 이후에 heapify 과정을 거치게 됩니다.

#2-1. 힙 자료구조에서 데이터를 추가하는 경우
1. 새로운 노드가 들어오면 새로운 노드를 힙의 마지막 노드에 이어서 추가한다.
2. 새로운 노드를 부모 노드와 교환해서 힙의 성질을 만족 시키는 과정을 반복한다.

#2-2. 힙 자료구조에서 삭제하는 경우
1. 루트 노드가 삭제된다.
2. 삭제된 루트 노드 자리에 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

#2-1 최대 힙의 데이터 추가 프로세스

#2-2 최대 힙의 데이터 삭제 프로세스

(04) :: Heap, How to use in Java?

- 자바 API 활용한 사용 방법

- 실제 구현

 

(FF) :: Reference

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 devowen.com
#2 www.tutorialspoint.com