힙 자료구조

힙 자료구조 전에 트리 자료구조의 표현법에 대해 좀 더 알아보자.

위와 같은 방식으로 표현

위와 같은 표현법을 사용하면 인덱스가 정해지게 된다.

즉. 왼쪽, 오른쪽 자식노드와 부모노드를 상수시간안에 접근 가능하다.

H[k]

- 왼쪽 자식 노드    : H[2*k+1]

- 오른쪽 자식 노드 : H[2*k+2]

- 부모 노드 : H[(k-1) //2]

힙 (heap) : 힙 성질(heap property)를 만족하는 이진트리

힙 성질

1. 모양이 힙의 형태 (왼쪽부터 채운 형태)

2. 모든 부모 노드 키값은 자식 노드 키값보다 커야 함

 

모양은 만족하나 부모가 자식보다 작은 경우가 있으므로 heap X

 

Heap 성질 만족하므로 heap 자료구조

힙의 루트노드에서는 가장 큰 값이다. A[0]

 

제공연산:

1. insert : O(logn)

2. find-max : return A[0] - O(1)

3. delete-max : O(logn)

 

 

 

 

참조 - https://www.youtube.com/watch?v=8XnPN6IB22Y&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=21