본문 바로가기

# Foundation/자료구조

힙 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

힙 ADT

최대/최소를 효율적으로 찾기위한 완전 K진트리 기반 ADT.  (Based Complete K-ary-Tree  ADT)

힙 ADT를 구현화하면 자료구조로 간주하며,  보통 이진트리로 구현 함.


최댓값을 찾기위한 힙은 Max Heap 이라고 하며,

최솟값을 찾기위한 힙은 Min Heap 이라고 부른다. 





Complete 트리를 기반으로 하면,  

배열로 구현했을 때 삽입의 성능을 향상시킬 수 있다.  

데이터를 삽입할 위치의 인덱스가 size와 동일해지기 때문.



힙의 특징

Max Heap
  • 힙의 루트는 항상 최댓값을 갖는다.
  • 부모는 항상 자식보다 크다.
  • 형제는 신경쓰지 않는다.  

Min Heap
  • 힙의 루트는 항상 최솟값을 갖는다.
  • 부모는 항상 자식보다 작다.
  • 형제는 신경쓰지 않는다. 



힙의 연산

  • 추출  (Extract Max/Min)
루트 노드의 값을 얻고,  트리에서 제거하는 연산.
새로운 루트 노드는 항상 최댓값/최솟값을 가르켜야 한다.

  • 삽입  (Insert)
트리에 새로운 값을 넣는 연산.
이때도 루트 노드는 항상 최댓값/최솟값을 가르켜야 한다.


추출연산 알고리즘 (in Max-Heap)

  • 루트 노드를 트리에서 빼낸다.
  • 맨 마지막 노드를 루트로 옮긴다.
  • 자신보다 더 큰 자식이 있다면 더 큰 자식과 스왑한다.




삽입연산 알고리즘 (in Max-Heap)

  • 데이터를 맨 마지막 위치에 넣는다.
  • 자신이 부모보다 크다면 스왑한다.




힙의 구현방식과 성능

배열  (General  Implementation )

  • 고정적인 사이즈
  • 랜덤 액세스 가능
  • 비어있는 첫번째 리프 노드를 찾으려면 현재 사이즈만 알면 됨.


연결 리스트

  • 유동적인 사이즈
  • 랜덤 액세스 불가능
  • 비어있는 첫번째 리프 노드를 찾기 까다로움.




힙 정렬

힙의 루트는 항상 최대/최소를 가르킨다는 성질을 이용.

배열을 힙으로 변환한 뒤, 힙에서 하나씩 꺼낸다.



배열을 힙으로 변환  (in Max-Heap)

비어있는 힙에 하나씩 넣기  O(n log n)

  • 빈 힙을 생성한다.
  • 배열의 데이터를 하나씩 힙에 전부 넣는다. 
  • 힙의 데이터를 하나씩 전부 뺀다.


규칙을 맞춰나가기  O(n) ~ O(n log n)

  • 먼저 힙 저장공간에 무작정 데이터를 때려박는다.
  • 레벨이 낮은 노드부터 탐색하면서,  자신보다 큰 자식이 있다면 가장 큰 자식과 스왑한다.  
만약 스왑했다면,  스왑한 자리에서 다시 더 큰 자식이 있는지 검사한다.  



참고문헌

http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html


'# Foundation > 자료구조' 카테고리의 다른 글

우선순위 큐 ADT  (0) 2019.02.09
이진트리 ADT  (0) 2019.02.06
트리 ADT  (0) 2019.02.06
그래프 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04