힙에있는 요소 검색

힙은 O (logN) 시간 복잡도로 요소가 있는지 여부를 검색하는 데 사용할 수 있다는 것을 기억했습니다. 그러나 갑자기 나는 세부 사항을 알 수 없다. 나는 getmin delete add 만 찾는다.힙에있는 요소 검색

아무도 힌트를 줄 수 있습니까?

출처

2010-03-03 skydoor

요소가 내부에 있는지 확인하려면 힙의 모든 요소를 검색해야합니다.

하나의 최적화가 가능하지만 여기서는 최대 힙이라고 가정합니다. 검색하는 요소보다 낮은 값의 노드에 도달 한 경우 해당 노드에서 더 이상 검색 할 필요가 없습니다. 그러나이 최적화를 사용하더라도 검색은 여전히 O (N)입니다 (평균 N/2 노드를 확인해야 함).

출처

2010-03-03 18:08:11

이것이 사실입니까? 다음 힙을 예로 취하십시오. '[5, 4, 1, 3]'이 힙 (배열 형태로)을 3으로 검색하면 1을 치고 알고리즘에 따라 여기에서 멈 춥니 다 사실 그것이 힙에 없다고 결론 내릴 수 있습니까? 내가 여기서 뭔가를 놓치고 있니? –

최적화를 사용하면 루트 1이있는 하위 트리가 3을 포함 할 수 없기 때문에 더 이상 검색되지 않습니다. 3이 다른 하위 트리에 있습니다. 선형 검색 (재귀 적 검색과 반대)이 잘못된 대답을 줄 수 있다는 것에 동의합니다. –

@JamesSanders 선형 검색의 경우에도 마찬가지입니다. 전체 이진 트리는 4의 왼쪽 자식으로 값 3을 가지며 1은 4와 동일한 높이가됩니다. 선형 검색을 수행하는 경우에도 최적화에 따르면 4> 3이므로 최소한 , 4와 동일한 높이에있는 다른 모든 요소 이외에 4의 자녀를 비교하십시오. – lee

나는 당신이 찾고있는 것이 BST (binary search tree)라고 생각한다.

출처

2010-03-03 16:29:19 zarkon

+13

이미 우선 순위 큐가 있고 해당 큐에 지정된 요소가 들어 있는지 확인하려는 경우 유용하지 않습니다. – finnw

힙에있는 요소 검색

답변

관련 문제