힙 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