약 힙 (최대 힙 및 최소 힙)

Question

힙 데이터 구조에서 왼쪽 자식이 자체 수준에서 올바른 자식 이상일 수 있다는이 질문이 있습니까? 내 말은이 세 개의 숫자 9,5,8을 고려해야하며 최대 힙 데이터 구조를 만들어 뿌리가 9가되고 8이 왼쪽 자식이고 5가 올바른 자식이라는 사실입니까? 제발 도와주세요

Answer 1

그건 중요하지 않습니다. max-heap의 노드에는 하위 노드가 있어야하고 min-heap의 노드에는 하위 노드가 있어야합니다. 그것들은 유일한 요구 사항입니다.

Answer 2

최대 - 힙 속성 :

1. 루트는 최대 요소입니다. O (1) 최대 요소 검색 시간.
2. 아이들은 하위 트리의 루트보다 항상 작다.
3. 최소 요소가 잎 요소 어딘가에있다 (왼쪽 및 오른쪽 아이들 사이에 조건이 없음), 즉 O (N/2) == O (n) 최소 요소를 찾는 데 필요한 시간.

최소 힙 성질 :

1. 루트 최소 요소이다. O (1) mim 요소를 검색하는 시간.
2. 아이들은 하위 트리의 루트보다 항상 크다.
3. 최대 요소가 잎 요소 어딘가에있다 (왼쪽 및 오른쪽 아이들 사이에 조건이 없음), 즉 O (N/2) == O (n) 최대 요소를 찾으려면 시간이 필요합니다.

따라서 힙은 검색에 적합하지 않지만 검색은 선형 O (n) 시간이 걸리기 때문에 요소 배열을 정렬하는 데 사용됩니다.

검색을 위해 O (h) 시간에 동일한 작업을 수행하는 이진 검색 트리 (BST)를 사용할 수 있습니다. 그리고 최상의 경우 BS 트리가 균형 잡혀 있으면 O (logn)에서 검색을 수행합니다.