1106
1. 힙(Heap) 이란?
힙: 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)
힙은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 구성하여 정렬해나가는 방법입니다. 이 때, 최대 힙이란 모든 부모가 자식보다 큰 힙을 말합니다.
2. 힙의 구성 요소
이진 힙(이진트리를 기반으로 한 힙)은 부모 노드, 자식 노드로 이루어져 있습니다.
- 만약 최대 힙을 구성한다면 부모 노드는 모든 자식 노드보다 값이 커야 하며
- 최소 힙을 구성한다면 부모 노드는 모든 자식 노드보다 값이 작아야 합니다.
3. 힙의 기본 동작
힙에서 최대 힙 또는 최소 힙을 구성하기 위해서는 가장 높은 값과 가장 낮은 값을 찾아야 합니다. 이를 위해 조회, 삭제, 삽입과 같은 기본적인 힙 작업이 들어갑니다.
조회: 노드 중에서 가장 높은 값 또는 가장 낮은 값을 찾는다추가: 새로운 하위 항목을 힙에 추가한다삽입: 힙에서 노드를 삭제한다
힙에서 새로운 노드를 추가할 때는 부모 노드와 자식 노드간의 연관성을 봅니다.
힙은 기본이 최대 힙 구성이기 때문에 만약 자식 노드가 하나 있는 부모 노드가 5인데 추가하는 노드의 값이 6이라면 규칙이 붕괴되며 5와 6을 바꿔주어야 하는 것이죠.
이 때 자식 노드간의 대소는 비교하지 않습니다.
4. 힙의 여러가지 알고리즘
힙 데이터 구조에는 힙 데이터 구조의 요소 삽입을 처리하고 제거하기 위한 다양한 알고리즘이 있습니다. 참고로 알아두시면 좋습니다.
-
우선순위 대기열: 우선순위가 지정된 객체를 포함하는 추상 데이터 구조입니다. 각 개체나 항목에는 미리 정해진 우선순위가 있습니다. 따라서 더 높은 우선순위가 할당된 객체나 항목이 나머지보다 먼저 서비스를 받습니다. -
바이너리 힙: 바이너리 힙은 삭제 및 삽입과 같은 간단한 힙 작업에 적합합니다. -
이항 힙: 이항 힙은 힙을 구성하는 일련의 이항 트리 컬렉션으로 구성됩니다. 이항 힙 트리는 엄격하게 정의되어 있으므로 일반적인 트리가 아닙니다. 이항 트리의 총 요소 수는 항상 2를 갖습니다.n 노드. -
힙 정렬: 대부분의 정렬 알고리즘과 달리 힙 정렬은 정렬 작업에 O(1) 공간을 사용합니다. 먼저 최대 힙으로 변환하여 오름차순으로 정렬이 발생하는 비교 기반 정렬 알고리즘입니다. Heapsort를 업그레이드된 품질의 이진 검색 트리로 볼 수 있습니다.
5. 힙 활용문제 풀어보기 (OX문제)
Q1. 힙은 완전이진트리를 기본으로 한 자료구조이다.
Q2. 힙의 기본 세팅은 최소힙이다.
Q3. 최대 힙은 부모 노드는 모든 자식 노드보다 값이 작아야한다.
Q4. 최대 힙 또는 최소 힙을 구성하는 과정에서 부모 노드와 자식 노드간의 대소와 자식 노드와 자식 노드간의 대소를 비교해야 한다.
