[자료구조] 힙 (Heap)

힙

최대값이나 최솟값을 빠르게 구하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조

최소힙: 작은 값을 부모노드에 있게 하고, 최상단에는 가장 작은 값을 가짐

최대힙: 큰 값을 부모노드에 있게 하고, 최상단에는 가장 큰 값을 가짐

 

 

최소 힙에 노드 삽입하기

완전트리에 맨 끝에 노드 추가

정렬을 위해 자신과 부모노드를 비교해서 자신의 값이 작으면 자리 교환 (노드가 root에 도착했거나 부모노드가 자신보다 작을 때까지 반복)

완전 이진 트리에서 이루어 지므로 O(logN)이 걸린다.

최소 힙에 노드 꺼내오기

root 를 꺼내온 후에 완전 이진트리의 맨 마지막 노드를 가져와서 루트에 채운다.

정렬이 안된 상태 이므로

자신의 자식노드와 비교해서 더 작은 값을 올린다. (자식이 자기보다 크거나 마지막 노드에 갈때 까지 반복한다.)

O(logN)의 시간이 걸린다.

---

source

https://www.youtube.com/watch?v=jfwjyJvbbBI