- 기본구조
여기서 간단한 한가지 특징 존재한다.
항상 Parent Node 와 Child Node의 대소관계가 분명해야하는 것이다.
그래서, 아래와 같이 두가지 종류의 Heap Tree가 만들어 질수 있다.
- top-heavy tree : Parent Node > Child Node( Left, Right)
- bottom-heavy tree : Parent Node < Child Node( Left, Right)
이곳에서는 Left Node와 Right Node의 대소관계는 중요하지 않으며,
오직 Parent Node와 Child Node의 대소관계만 따진다.
- 기본적인 Heap이 완성된 경우의 구조
- top node는 top-heavy tree의 경우 가장 큰 값
- top node는 bottom-heavy tree의 경우 가장 작은 값
- 위에서 언급했듯이, 그 다음 작은 값은 child 중 한 Node (Left or Right)
- Heap의 기본특성
- Parent node와 Child node의 대소관계가 분명하다.
- Left node와 Right node의 대소관계의 불문명하다.
- 오직 Parent와 Child node의 구성만 알수 있다.
- heap은 기본적으로 왼쪽 평형트리 구조를 가지고 있으며, 이는 중요하다.
- 상위 4번 특성 (왼쪽 평형트리 구조) 로 아래의 추가적인 특성이존재
- Node 추가 할 경우,Child node가 추가되는 방향은 항상 왼쪽에서 오른쪽.
- Node 삭제 or 추가된 경우 Child node가 한개가 될 경우 left node 우선순위가 있음
- Binary 탐색을 한다면 BFS 방식
*BFS(Breadth-first search) 대표적인 이진 트리의 탐색 알고리즘으로 넓이 우선 순위이다.
- Timer complex 설명
시간의 복잡도는 Insert 할 경우는 Worst Case O(LogN)이다.
1.2 Heap 기본구현 (Array 방식)
기본성질 Array Binary Tree 기본 성질 array를 0부터 사용할 경우
- Number Node
Array즉 배열을 이용하여 이진 트리를 구성해야하기 때문에 Array와 binary Tree의 성질
알아야한다.
- Array로 Binary Tree 구현할 경우 기본성질
- Left Node = 2i+1
- Right Node = 2i+2
- Parent Node = (i-1)/2
자세한 내용은 2.2 Data의 정적구현 참조
- top-heavy heap 구현방법
- top-heavy heap는 top node는 가장 큰 값을 소유하고 있다.
- Heap의 Length을 정확히 파악하여 last node의 parent와 child 대소 관계를 비교
- Child가 큰 경우에만 Parent와 Child 교환진행
- 왼쪽 Parent로 이동가며 Top Node까지 진행하며 3번 반복 (방향 오른쪽 -> 왼쪽 )
- Top-heavy heap Example
상위그림 기준으로 보면, Last Node 14이며 , Parent 6 여기서 3 Node를 비교 교환시작.
Parent 6,5,4,3,2,1,0 비교와 교환 진행 하면 Top-heavy heap 구축된다.
Heap 자료구조 관련내용
http://opendatastructures.org/ods-java/10_1_BinaryHeap_Implicit_Bi.html
https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)
https://en.wikipedia.org/wiki/Heap_(data_structure)
2. Heap Sort
기본적으로 상위 Heap 구현이 된 후에, 이를 이용한 Sort 알고리즘이다.
방법은 간단하며, Heap 기본성질이 최대 or 최소 값을 추출하는 방법을 이용한다.
- 구현방법
- n 개의 노드를 가진 top-heavy heap 구조 구축
- top-heavy heap는 top node는 가장 큰 값을 소유
- top-node를 last node와 교환진행 (top-node 추출작업과 동일)
- top-heavy heap를 재구축을 heap size를 1을 줄이고 진행한다.
- top-heavy heap 재구축 및 추출작업
- top-node가 현재 작은값이기때문에 child 중 두번째로 큰 값을 찾아 교환
- 원래 top-node의 값은 child (left or right) 되었기에 관련 Tree는 비교 및 교환진행
- 2번을 반복하며 방향은 아래로 지속적으로 한쪽 방향으로만 비교 및 교환진행 ( O(logN)
https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
https://en.wikipedia.org/wiki/Heapsort
다른 Heapsort 예제들
http://thinkpro.tistory.com/72
http://ehclub.co.kr/1552
3. Priority Queue
기본적으로 상위 Heap 구현이 된 후에, 이를 이용한 우선순위 Queue를 구현이 가능하다.
Heap sort 와 마찬가지로, Heap의 기본성질인 가장 큰 값 or 가장 작은 값을 이용하는 것이다.
Priority Queue 역시 Heap의 기본 성질을 원하는 것이기 때문에, Heap를 이용하여 쉽게
구현이 가능하다.
- array 구현방법 (정적으로 구현방법)
- pqueue_init : n 개의 노드를 가진 상위 top-heavy heap 구성
- pqueue_insert: 기존의 top-heavy heap 의 마지막 노드에 data 를 삽입 후 다시 heap화 한다.
- pqueue_extract: top node를 추출하고 size를 줄이고 다시 heap화 한다.
- 구현함수
- pqueue_init : 상위 heap 구성과 동일
- pqueue_insert : pqueue_init와 동일
- pqueue_extract: top-heavy 재구축과 동일
https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90
https://en.wikipedia.org/wiki/Priority_queue
- Heap and Heap sort and Priority Queue 예제
이해가며, 그냥 내가 다시 구현했다.
댓글 없음 :
댓글 쓰기