Heap

Heap

Heap이란 최대값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조

최소힙이란?

작은 값을 항상 위에 있게하여 트리의 루트에는 가장 작은값이 오도록 함.

최소힙

최대힙이란?

큰값을 항상 위에 있게하여 트리의 루트에 가장 큰 값이 오도록 함.

최대힙

최소힙에 노드 삽입하기

완전 이진트리에 값을 추가 하듯이 마지막 leaf에 값을 추가 추가한값과 부모노드를 비교해서 자기보다 값이 작은 경우 자리 변경 루트에 도착하거나 자기보다 값이 작은 부모를 만나기 전까지 반복

최소힙은 부모노드와 비교할때마다 전체 값의 절반이 사라지기 때문에 O(log n)의 시간 복잡도를 가진다

최소힙에서 노드 꺼내오기

최소힙에 최솟값을 요청할때 루트의 값을 빼온 다음에는 마지막 하위 노드의 값을 가져와 루트에 채움 이후 정렬은 자식과 비교하여 자신보다 작은 자식과 자리를 바꾸는데 2개의 값중 더 작은 값과 자리를 바꾼다.

노드 삽입과 동일하게 마지막 자식을 루트에 올린 후 값을 비교할때마다 절반씩 검사해야할 값이 사라지기 때문에

O(log n)의 시간 복잡도를 갖는다.

힙과 배열

배열 heap에서 부모노드와 자식 노드의 관계

- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

왼쪽 자식의 인덱스 = (부모의 인덱스) x 2

오른쪽 자식의 인덱스 = (부모의 인덱스) x 2 + 1

부모의 인덱스 = (자식의 인덱스) / 2

from http://ju-bong.tistory.com/33 by ccl(A) rewrite - 2021-12-18 03:27:02