힙(Heap)이란?

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

부모 노드의 인덱스는 1로, 왼쪽 자식 노드부터 2, 3 순서이다.

• (부모 노드의 인덱스) = (자식 노드 인덱스) / 2
• (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2
• (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1

배열로 구현할 때 인덱스 번호 1부터 시작하면 편함..
0부터 할거라면 계산할 때 -1하는 거 잊지 말기..

💡 힙은 왜 사용하나요?

최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.
하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.

정리하자면, 힙은 다음 조건을 만족하는 자료구조이다.

1. 힙은 최대힙(Max heap)과 최소힙(Min heap)으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 작다.
2. 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가진다.
3. 중복을 허용한다.

💡 완전 이진 트리(Complete Binary Tree)란?

이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다.
위 그림과 같이 나타내며, 왼쪽이 비어있고 오른쪽이 채워져 있는 형태는 완전 이진 트리라고 할 수 없다.

(출처: https://heytech.tistory.com/105)

힙 vs 이진 탐색 트리

💡 이진 탐색 트리(Binary Search Tree)란?

이진 탐색과 연결리스트(linked-list)를 결합한 자료구조의 일종이다.
이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료의 입력과 삭제를 가능하도록 한다.
각 노드에서 왼쪽의 자식 노드는 해당 노드보다 작은 값으로, 오른쪽의 자식 노드는 해당 노드보다 큰 값으로 이루어져 있다.

공통점

• 모두 완전 이진 트리이다.

차이점

• (최대힙의 경우) 힙은 각 노드의 값이 자식 노드보다 크거나 같다.
• 이진 탐색 트리는 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져있다.
  왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 힙은 왼쪽 노드의 값이 크든 오른쪽 노드의 값이 크든 상관 없다.
• 힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조이다.

힙의 동작

최대 힙(Max heap)으로 예를 들어 힙의 삽입, 삭제 동작을 알아보자.

데이터 삽입

힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

1. 15를 왼쪽 최하단 노드에 삽입한다.
2. 10을 왼쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.
3. 왼쪽 최하단 노드가 이미 있으므로 8을 오른쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

4. 3을 왼쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.
5. 왼쪽 최하단 노드가 이미 있으므로 4를 오른쪽 최하단 노드에 삽입한 뒤, 부모와 비교한다. 부모보다 작으므로 그 자리에 위치한다.

데이터 삽입 (힙의 데이터보다 클 경우)

기본적으로 앞에서 설명한대로, 완전 이진 트리의 구조에 맞춰 최하단부 노드부터 채워진다.
채워진 노드의 위치에서, 부모 노드의 값보다 클 경우에는 부모 노드와 위치를 바꾸며 이를 반복한다.

1. 20을 왼쪽 최하단부 노드에 삽입한다.
2. 20의 부모 노드인 8과 비교한다. 20이 더 크므로 8과 위치를 바꾼다. (swap)

3. 20의 부모 노드인 15와 비교한다. 20이 더 크므로 15와 위치를 바꾼다. (swap)

데이터 삭제

힙 자료구조의 목표는 바로 최대값이나 최소값을 알아내는 것이다.
때문에 데이터가 삭제 된다면 가장 큰 값인 부모 노드의 값이 삭제된다.

1. 최대값을 갖는 부모 노드를 삭제한다.

2. 부모 노드가 비었으므로, 가장 최하단부 노드를 루트로 옮긴다.
3. 부모 노드인 8보다 값이 큰 자식 노드가 있는지 비교한다.
   1) 왼쪽, 오른쪽 자식 노드 모두 부모 노드보다 클 경우
   • 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여, 더 큰 자식 노드와 부모 노드의 위치를 바꾼다. (swap)
   2) 왼쪽, 오른쪽 자식 노드 중 하나만 부모 노드보다 클 경우
   • 둘 중에 부모 노드보다 큰 자식 노드와 부모 노드의 위치를 바꾼다. (swap)

---

파이썬으로 힙(Heap) 구현 및 모듈 사용 예제

https://velog.io/@gnwjd309/python-heap