99클럽 코테 스터디 27일차 TIL + Heap(1)

학습 키워드

- Heap

 

공부한 내용

Heap (max / min)

• 힙은 완전 이진트리 형태로 최대, 최솟값을 빠르게 찾아내는데 유용한 자료구조이다.
• 힙은 중복값을 허용한다.
• Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을  Primary Queue를 활용하여 구현할 수 있다.
• 부모 - 자식 간 (레벨 별) 정렬은 보장하고, 형제간의 정렬은 보장하지 않아서 반 정렬 상태라고 볼 수 있다.

힙**(Heap)**의 특징

• 완전 이진 트리(Complete Binary Tree) : Heap은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다.
• 부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가집니다. 이러한 특성은 최대 힙(max heap)에서는 부모 노드가 항상 자식 노드보다 큰 값을 가지며, 최소 힙(min heap)에서는 부모 노드가 항상 자식 노드보다 작은 값을 가지는 것을 의미한다.
• 힙 속성 : Heap의 모든 부모-자식 쌍에 대해 특정한 조건을 만족해야 한다. 최대 힙에서는 모든 부모 노드가 자식 노드보다 크거나 같은 값을 가져야 하며, 최소 힙에서는 모든 부모 노드가 자식 노드보다 작거나 같은 값을 가져야 한다.

힙(Heap)의 장점 및 단점

장점

빠른 삽입 및 삭제  

- Heap은 특정한 순서에 따라 정렬된 상태를 유지하므로 삽입과 삭제 연산이 상수 시간(O(log n))에 이루어진다.
- 이는 요소들의 우선순위에 따라 빠르게 작업을 처리할 수 있다는 것을 의미한다.

우선순위 기반 작업 처리 

- Heap은 우선순위 큐와 같은 다른 추상 자료형을 구현하는 데 사용된다.
- 최대 힙인 경우에는 가장 큰 우선순위를 가진 요소에 빠르게 접근할 수 있고, 최소 힙인 경우에는 가장 작은 우선순위를 가진 요소에 빠르게 접근할 수 있다.


단점

임의 접근의 어려움 

- Heap은 일반적으로 완전 이진 트리의 형태를 가지며, 배열 또는 연결 리스트를 사용하여 구현된다.
- 이러한 구조는 임의 접근을 지원하지 않고, 요소에 접근하기 위해 순차적인 탐색을 수행해야 한다.
- 따라서 특정한 요소를 찾는 데에는 O(n)의 시간이 걸린다.

정렬 유지의 오버헤드 

- Heap은 정렬된 상태를 유지하기 위해 삽입과 삭제 연산 시에 정렬을 조정해야 한다.
- 이는 일정한 오버헤드를 발생시킬 수 있다.
- 따라서 요소들의 정렬 상태가 항상 필요하지 않은 경우에는 다른 자료구조를 고려하는 것이 좋다.

배열로 구현 시 추가적인 공간 요구 

- Heap은 일반적으로 배열 또는 연결 리스트를 사용해 구현된다.
- 배열 기반의 Heap에서는 공간을 미리 할당해야 하므로 요소의 개수에 따라 적절한 크기를 선택해야 하며, 요소의 개수에 따라 추가적인 공간을 필요로 한다.

 

⇒ 힙(Heap)은 삽입 및 삭제 연산에 있어서 뛰어난 성능을 보이지만, 임의 접근과 정렬 유지에 관련된 한계가 있다.

 

회고

발생한 문제

- 자료구조에 대한 공부가 필요하다는 생각이 들었다.

 

해결 방법

- 자료구조 힙에 대해 공부했다. 

 

알게된 내용

- 힙이 삽입, 삭제 속도가 빠르다는 사실과 힙의 장단점에 대해 알게 되었다. 

 

 

참고 자료

- https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

- https://velog.io/@dawonseo/Java-%ED%9E%99-%EC%B5%9C%EB%8C%80-%EC%B5%9C%EC%86%8C-%ED%9E%99-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0