힙(Heap) cf.이진탐색트리

🟩 힙 = 퇴적물

바닷속 퇴적물처럼 아래에 큰 바위, 중간 정도의 돌, 그 위에 작은 모래 순으로 쌓여있다.

 

🟩 그래프의 트리 구조 중 하나(완전 이진트리)

각 노드의 키 값이 그 자식의 키 값보다 작지 않거나(최대힙), 크지 않은(최소힙) 완전 이진트리

완전 이진트리는 중복을 허용하지 않지만 힙은 허용한다.

 

🟩 정렬을 효율적으로 수행하는 트리

'우선순위 큐'를 구현할 때 사용

최댓값과 최솟값을 빠르게 찾기 위해 고안됨

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

 

🟩 힙에서의 부모-자식 관계

오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1

왼쪽 자식의 인덱스 = (부모의 인덱스)  * 2

부모의 인덱스 = (자식의 인덱스) / 2

 

🌟 우선순위 큐

대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조

데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있다. 반면 데이터를 추출할 때는 최솟값부터 순서대로 선택

 

힙을 표현하는 트리 구조에서 각 정점을 '노드(node)'라 한다.

노드는 최대 2개의 자식을 갖는다. 위에서부터 채워지며, 같은 층에서는 왼쪽부터 채워진다.

또한, 트리 모양은 데이터의 개수에 의해 정해진다.

 

 

 

🌟 이진탐색트리(BST, Binary Search Tree)

🟩 이진 탐색 + 연결리스트

이진 탐색의 효율적인 탐색 능력은 유지 + 빈번한 자료의 입력과 삭제를 가능하도록 한다.

 

🟩 각 노드에서 왼쪽의 자식 노드는 해당 노드보다 작은 값으로, 오른쪽의 자식 노드는 해당 노드보다 큰 값으로 이루어져 있다.

 

 

🌟 힙과 이진탐색트리

🟩 공통점

모두 완전 이진트리

 

🟩 차이점

최대힙 : 각 노드의 값이 자식 노드보다 크거나 같다.

이진 탐색 트리 : 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져있다.

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

힙은 왼/오른쪽 노드의 값의 크기는 상관없다.

 

힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조

 

 

🟩 삽입

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

부모와 크기 비교하면서 위치 변경 및 삽입한다.

 

🟩 삭제

힙 자료구조의 목표는 최댓값이나 최솟값을 알아내는 것

때문에 데이터가 삭제된다면 가장 큰 값인 부모 노드의 값이 삭제된다.

 

 

부모 노드가 비어있으므로, 가장 최하단부 노드를 루트로 옮긴다.

부모 노드인 8보다 값이 큰 자식 노드가 있는지 비교한다.

 

👉 왼쪽/오른쪽 자식 노드 모두 부모 노드보다 클 경우,

왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여, 더 큰 자식 노드와 부모 노드의 위치를 바꾼다.

 

👉 왼쪽/오른쪽 자식 노드 중 하나만 부모 노드보다 클 경우,

둘 중에 부모 노드보다 큰 자식 노드와 부모 노드의 위치를 바꾼다.