힙(Heap) |
자료구조 Heap
프로그래머가 동적으로 할당(malloc/new)한 메모리가 위치하는곳도 힙이라고 부르지만 여기서의 힙은 자료구조 힙이다.
여러 값 중에서 최댓값이나 최솟값을 빠르게 찾을 때 좋다.
그러므로 최대값/최소값을 빠르게 찾기 좋은 자료구조이므로 우선순위큐를 힙으로 구현한다.
힙(Heap)은 완전 이진트리 형태이다.
완전 이진트리란 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으면서,
마지막 레벨의 모든 노드들이 왼쪽부터 채워져 있는 트리를 의미
즉, 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워간 형태
Heap의 두 종류와 특징 |
1. Heap의 두 종류
Heap에는 Min Heap과 Max Heap 두 종류가 있다.
Min Heap : 부모 노드가 자식 노드보다 작거나 같다.(위의 사진처럼)
Max Heap : 부모 노드가 자식 노드보다 크거나 같다.
Min 혹은 Max의 규칙을 유지하며 원소를 추가/제거 하면
Min Heap은 root에 최소값이
Max Heap은 root에 최대값이 위치하게 된다.
2. Heap의 index 특징
index 0은 root노드를 의미하며
i번째 노드의 부모노드는 (i - 1) / 2번째 노드가 되고
i번째 노드의 자식노드는 i * 2 + 1번째 노드와 i * 2 + 2번째 노드가 된다.
3. Heap의 시간복잡도
원소의 추가/제거 : O(logN)
조회 : O(1) // root값만 확인하는 방식이므로
Push & Pop의 작동 방식 |
특징
1) 위아래에서는 크거나 같은/작거나 같은 대소관계가 중요하지만
2) 좌우에서는 대소관계를 신경쓰지 않음
1. Push의 작동 방식
위의 트리 상황에 4를 push한다면?
1) 먼저 트리의 가장 끝 부분에 원소를 추가한다.
2) Heap의 규칙에 맞게 위치를 재설정한다.
만약 Min Heap이라면 4는 부모노드인 6보다 작으므로 서로 위치를 바꾼다.
3) 2번의 과정을 반복하다보면 Heap의 모습이 된다.
2. Pop의 작동 방식
1) Heap에서는 pop()을 하게 되면 root의 값이 제거가 됨
2) 이후 마지막 index의 노드가 root 노드로 옮겨짐
3) 이제 Heap의 조건에 맞게 위치를 정렬해줘야 하는데
push의 경우는 가장 밑에 추가해서 그 노드의 바로 위 부모노드와 비교하면서 올라가는 방식이었다면
pop은 가장 위에서부터 아래로 비교해가면서 내려간다는 차이가 있음
위처럼 Min Heap인 경우 root의 6의 자식노드 3, 4와 비교를 하되 둘 중 더 작은 값과 swap됨
4) 그리고 또 6과 아래쪽을 비교해서 더 작은 값이 있는지 확인하고 작은값인 5가 있으므로 둘이 swap
5) 위와 같은 모습이 최종적으로 완성된 형태
※ push와 pop의 차이
push는 가장 밑에서 추가해서 올라가는 방식이라면
pop은 가장 위에서부터 아래로 비교해가면서 내려간다는 차이가 있음
※ 참고문헌