Heap이란?(1)

힙

힙이란?

데이터에서 최대값과 최솟값을 빠르게 찾기 위한
완전 이진 트리

완전 이진 트리
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
즉, 차례대로 꽉꽉 채워지는 트리!

만약 배열을 이용해서 최대, 최소를 구한다면 배열 전체를 탐색하여야하므로 시간이 많이 걸립니다. (O(n))

이 때, 힙에 데이터를 넣고 최대, 최소를 찾는다면 O(log n)만큼의 시간이 소요됩니다.
-> 우선순위 큐를 사용합니다.

힙 VS 이진 탐색 트리

공통점

모두 이진 트리이고 최대 간선은 2개 갖는다.

차이점

힙	이진 탐색 트리
최대 힙 : 각 노드의 값이 자식 노드보다 크거나 같음 최소 힙 : 각 노드의 값이 자식 노드보다 작거나 같음 즉, 왼쪽 오른쪽 구분없이 그냥 부모가 더 크거나 작으면 됨	각 부모 노드를 기준으로 왼쪽 노드에는 부모보다 작은 값 오른쪽 노드에는 부모보다 큰 값이 저장됨

힙 동작 방법

힙에 데이터 삽입하기

우선 최하단부 왼쪽 노드에 값을 채웁니다.
채워진 노드 위치에서 부모 노드보다 값이 클 경우,
부모 노드와 위치를 바꿔주는 작업을 반복(SWAP)

힙에 데이터 삭제하기

보통 루트 노드(최대값, 최소값)를 제거합니다.

최하단에 가장 우측에 있는 노드(즉, 가장 마지막 노드)를 찾아서
제거된 루트 노드에 삽입해줍니다.

루트 노드에서부터.... (SWIM)
(최대 힙의 경우) : 자식 중 더 큰 값을 골라서 바꿔치기 합니다.
(최소 힙의 경우) : 자식 중 더 작은 값을 골라서 바꿔치기 합니다.