23.09.17 힙 더 알고 가자

 전에 힙을 알아봤을 때는 내가 이해한 것을 기반으로 정리가 되어있지 않아서 가독성도 많이 떨어졌는데 이번에 다시 정리하면서 한 번 더 보려고 한다. 

 

힙

 특정한 속성을 가진 완전 이진 트리의 일종이다. 

1. 최대 힙 (Max Heap)
   • 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같습니다.
   • 즉, 루트 노드는 힙 내의 최댓값을 가집니다.
2. 최소 힙 (Min Heap)
   • 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같습니다.
   • 즉, 루트 노드는 힙 내의 최솟값을 가집니다.

주요  기능

삽입 (Insertion)

힙에 새로운 요소를 추가한다. 추가 후에는 힙 속성을 유지하기 위해 재정렬을 하는데, 이 과정은 통상적으로 O(log n) 시간 복잡도를 가진다.

 

1. 새로운 값을 가진 노드를 힙의 가장 마지막 노드로 추가한다.
2. 부모 노드와 비교하여 힙 속성을 위배하는 경우 부모 노드와 값을 바꾼다.
3. 힙 속성이 유지될 때까지 2번 작업을 반복합니다.

삭제 (Deletion)

주로 루트 노드를 삭제하는 연산을 의미한다. 삭제 후에도 힙 속성을 유지하기 위해 재정렬하는데  이 과정은 O(log n) 시간 복잡도를 가진다.

1. 루트 노드의 값을 삭제한다.
2. 가장 마지막 노드를 루트 노드 위치로 이동한다.
3. 이동한 노드와 그 노드의 자식 중 가장 큰 값의 자식과 비교한다.
4. 만약 현재 노드의 값이 해당 자식보다 작다면, 두 노드의 위치를 교환한다.
5. 이 과정을 현재 노드의 값이 모든 자식보다 크거나, 리프 노드에 도달할 때까지 계속 반복 한다.

 

조회 (Peek)

루트 노드의 값을 조회한다. 이 연산은 O(1) 시간 복잡도를 가진다.

 

 

 

힙을 사용하는 이유

1. 우선순위 큐 구현: 힙은 루트에 항상 최대값(최대 힙의 경우) 또는 최소값(최소 힙의 경우)을 가지므로, 우선순위에 따라 데이터를 빠르게 검색하거나 제거할 필요가 있는 경우에 적합하다.
2. 정렬: 힙 정렬과 같은 특정 알고리즘에서 힙을 활용하면 효율적인 정렬이 가능하다.
3. 탐색 최적화: 힙은 최대값 또는 최소값에 빠르게 접근할 수 있다.

장점:

1. 효율성: 힙 연산에서 삽입 및 삭제 연산이 O(log n) 시간 복잡도를 가진다.
2. 메모리 효율: 힙은 배열로 구현될 수 있으므로, 추가적인 메모리를 요구하지 않고, *포인터 기반의 구조보다 메모리 효율이 높다.
3. 가장 크거나 작은 요소에 빠른 접근: 루트에 직접 접근하므로 O(1)의 시간 복잡도로 최대값 또는 최소값에 접근할 수 있다.

*포인터 기반 구조 : 메모리의 주소값을 참조하는 포인터를 사용하여 데이터 구조를 연결하거나 관리하는 방식을 의미한다. 이러한 구조에서는 데이터 요소 간의 관계를 메모리 주소 참조를 통해 맺는다.

대표적으로 연결리스트, 이진트리, 그래프
-  힙은 기본적으로 이진 트리의 한 형태이지만, 일반적인 구현에서는 배열을 기반으로 한다.

 

단점:

1. 정렬된 구조가 아님: 힙은 부분적으로 정렬된 구조이지만, 완전히 정렬된 구조는 아니다. 따라서 순차적인 접근이 필요한 경우에는 상대적으로 비효율적일 수 있다.
2. 복잡성: 힙의 연산을 구현하고 유지하는 데는 복잡성이 있을 수 있다.

 

이렇게 정리하면 나중에도 내가 블로그에서 바로 힙 검색해서 아 이거였지 하면서 알겠지

 

참고