힙은 완전이진트리를 기반으로 한 자료구조로

완전이진트리의 장점은 입력,삭제,추가의

시간복잡도가 모두 O(logn)이다


루트, 오른쪽 서브트리, 왼쪽 서브트리, 레벨을 알면 사용할 수 있다


5 3 2 1 4 6 7일때


처음 루트노드에 5가 입력된다

5

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

왼쪽 1레벨 서브트리에 3이 입력된다

부모가 나보다 크면 스왑(업힙)한다

3

5

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

오른쪽 1레벨 서브트리에 2가 입력된다

부모가 나보다 크면 스왑(업힙)한다

2

5 3

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

왼쪽 2레벨 서브트리에 1이 입력된다

부모가 나보다 크면 스왑(업힙)한다

1

3 2

5

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

왼쪽 2레벨 서브트리에 4가 입력된다

부모가 나보다 크면 스왑(업힙)한다

1

2 3

5 4 6 7
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

pop을 하면 1이 빠져나오고(힙팝)

가장 높은 레벨의 맨 오른쪽 노드를

루트노드로 옮긴다


7

2 3

5 4 6

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

왼쪽 자식과 오른쪽 자식중에

나보다 작은 자식을 스왑(다운힙)하면서

말단노드까지 간다

2

4 3

5 7 6

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

최소힙이 완성되었다


여기서 팝하면 다시 6이 올라갈것이다


파이썬의 힙큐는 디폴트가 최소힙이다


꿈★은 이루어진다

내일채움공제 되는 중소기업 가자 화이팅!