min-heap이란

이벤트루프에 대해 알아보던 중, setTimeout과 같은 함수들은 Timer phase의 min-heap에 타이머를 저장했다가, 이벤트루프가 Timer phase에 진입하게 되면 min-heap을 탐색하면서 시간이 경과된 타이머의 콜백을 실행한다는 것을 보게 되었습니다. 

 

min-heap이란?

완전이진트리(complete binary tree)의 일종으로, 최솟값을 빠르게 찾아내기 위한 자료구조입니다. min-heap은 부모노드의 키 값이 자식 노드의 키 값보다 작습니다. 반대로 부모노드의 값이 더 큰 max-heap도 있습니다.

min-heap

 

max-heap

힙에 무언가를 삽입할 땐, 다음의 과정을 거칩니다.

1. 맨 마지막 노드에 데이터를 추가

min-heap의 데이터 삽입(1)

2. 부모 노드와 값을 비교하여, 부모가 더 크다면 부모 노드와 자식 노드의 위치를 교환

min-heap의 데이터 삽입(2)

3. 2의 반복

min-heap의 데이터 삽입(3)

 

힙에서 무언가를 삭제할 땐, 다음의 과정을 거칩니다.

1. 루트 노드를 삭제

min-heap의 데이터 삭제(1)

2. 맨 마지막 노드를 루트 노드의 위치로 올림

min-heap의 데이터 삭제(2)

3. 양쪽 자식 노드의 값을 비교하여 더 작은 자식 노드와 위치를 변경

min-heap의 데이터 삭제(3)

4. 3 반복

min-heap의 데이터 삭제(4)

5. 자식 노드가 없거나, 자식 노드가 작지 않은 경우 종료.

 

heap은 배열을 통해 쉽게 구현할 수 있습니다. heap은 완전 이진 트리로, 왼쪽부터 오른쪽으로 차곡차곡 노드가 저장되기 때문입니다. 

// 구현 예정

 

 

 

 

 

출처

https://ddmix.blogspot.com/2016/03/binary-tree-errata.html

이진트리의 종류에 대하여 (오류 수정)

https://code-lab1.tistory.com/12

[자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현

https://blog.devgenius.io/how-to-implement-a-binary-heap-javascript-d3a0c54112fa

How to Implement a Binary Heap (Javascript)