부스트 binomial_heap에 노드가 있는지 확인

Question

부울 :: 힙 :: binomial_heap에 요소가 있는지 확인하려는 경우 update() (노드가 이미있는 경우)를 호출해야하는지 알 필요가 있거나 push() (노드가 존재하지 않는 경우) 일부 큐는 정확히이 용도로 push_or_update() 함수를 제공합니다. 내가 할 수있는 유일한 일은 대기열의 노드와 동일한 인덱스 유형 및 value_type 'handle_t'을 갖는 속성 맵을 유지하는 것입니다. 그런 다음지도에서 항목을 유효한 핸들이 있으면 조회 할 수 있으므로 그렇지 않으면 밀어 넣을 수도 있고 그렇지 않으면 업데이트 할 수도 있습니다.

더 좋은 방법이 있나요?

Here is the doc for reference.

Answer 1

이것은 이진 힙 (heap)이해야하는 것이 아닙니다.

일반적으로 문제를 해결하는 방법은 해시지도 (또는 원하는 다른 데이터 구조)를 사용하여 값과 handle 사이의 매핑을 저장하는 것입니다. 그런 다음 핸들에 대한 해시 맵을 쿼리 할 수 ​​있습니다. 이 핸들이 있으면이 핸들을 사용하여 힙의 값을 수정할 수 있습니다. 존재하지 않는다면 힙에 새로운 값을 추가 할 수 있습니다 (물론 해시 맵에 새로운 매핑을 추가 할 수 있습니다)

또 다른 방법은 트리 집합/맵을 사용하는 것입니다. 실제 사용 사례에 따라 위에서 설명한 솔루션보다 쉽고 효율적일 수 있습니다.