[자료구조] Heap

Aug 18, 2023

Contents

힙의 삽입 연산 힙의 최소값 삭제 연산 힙의 구현

💡

힙 순서 속성를 만족하는 완전 이진 트리 ”힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다”

힙의 삽입 연산

힙의 최고 깊이 가장 우측 노드에 새 노드를 추가 ( 이때 힙은 완전 이진 트리 유지)

2. 삽입한 노드와 부모 노드를 비교 - 삽입한 노드가 부모 노드보다 크면 종료 , 작다면 다음단계를 진행

삽입한 노드가 부모 노드보다 작다면 부모노드와 위치를 서로 바꿈 → 2단계를 다시 진행

힙의 최소값 삭제 연산

뿌리 노드를 삭제하는 것과 같음

뿌리 노드를 삭제한 후 힙 순서 속성을 유지해야 함 → 루트노드 삭제 한 후 뒤처리 과정

힙의 최고 깊이에 있던 노드를 루트 노드로 옮겨야 한다 ( 이때 힙 순서 속성이 파괴 , 이를 복원하는 과정 진행)

옮겨온 노드의 양쪽 자식을 비교하여 작은 쪽 자식과 위치를 교환 → 힙 순서 속성을 지키려면 부모 노드 양쪽 자식보다 작은 값을 가져야 하기 때문

옮겨온 노드가 더 이상의 자식이 없는 리프 노드로 되거나 양쪽 자식보다 작은 값을 갖는 경우 삭제 연산을 종료 , 그렇지 않다면 다시 2단계를 반복

힙의 구현

💡

힙은 링크드 리스트보다 배열을 이용하는게 더 적합하다.

깊이 0의 노드는 배열의 0인덱스

깊이 1의 노드는 배열의 1~2인덱스

깊이 2의 노드는 배열의 3~6인덱스

깊이 n의 노드는 배열의 2^n-1 ~ 2^(n+1)-2 요소 인덱스에 저장된다

k번 인덱스에 위치한 노드의 양쪽 자식의 인덱스

왼쪽 자식 노드 : 2k+1

오른쪽 자식 노드 : 2k+2

부모 노드는 : 2k-1 / 2

자료구조