어떻게 효율적으로 궤도의 가장 작은 요소 컬렉션에서?

Question

정맥에서의 프로그래밍 질문:가 있다고 가정할 수 있는 개체의 컬렉션을 비교하고 분류되어 있습니다.What's 하는 가장 효율적인 방법을 추적의 가장 작은 요소에서 컬렉션으로 객체 추가하고 현재 가장 작은 때때로 제거됩니까?

Answer 1

를 사용하여 min-힙 최선의 방법입니다.

http://en.wikipedia.org/wiki/Heap_(data_structure)

그것은 맞춤는 경우에는 제한이 적용됩니다.

Answer 2

해야 하는 경우 임의의 삽입 및 제거,가장 좋은 방법은 아마 정 배열입니다.삽입 및 제거해야 O(로그(n)).

Answer 3

@Harpreet
는 최적화되지 않았습니다.할 때는 객체를 제거,에릭슨가 검사 전체 컬렉션을 찾아 새로운 가장 작은 수 있습니다.

당신이 원하는 읽기에 검색 나무's.MS 는 좋 트 을 시작합니다.하지만 당신은 수 있습을 얻고 싶은 책이 좋아 소개하는 알고리즘(Cormen,Leiserson,Rivest,스타) 하려면 깊은 곳이었습니다.

Answer 4

가끔 제거합니다 피보나치 힙 도보다 더 빠르게 min-힙.삽입 O(1),그리고 찾는 분은 또한 O(1).제거 O(로그(n))

Answer 5

해야 하는 경우 임의의 삽입 및 제거 가장 좋은 방법은 아마 정렬 배열입니다.삽입 및 제거해야 O(로그(n)).

그렇습니다,그러나 당신이 필요하여 다시 정렬에서 각각 삽입과(아마도)각 삭제는,당신이 언급,O(로그(n)).

와 솔루션을 제안하여 Harpreet:

• 당신이 하나 O(n)에서 통과 시작을 찾기 위해 가장 작은 요소
• 삽입 O(1)이후(1 비교하는 데 필요한 이미 알려진 가장 작은 원소)
• 삭제하는 것입 O(n)당신이 필요하기 때문에 다시 찾은 가장 작은 요소(염두에 두 큰 O 표기는 최악의 경우).수도 있습을 확인하여 최적화하시는 경우 요소를 삭제할 것입니다()가장 작은하지 않는 경우,다만 하지 않는 모든 다시 확인을 찾기 위해 가장 작은 요소입니다.

그래서,그것은 다릅니다.이들 중 하나는 알고리즘에 대한 더 나은 삽입 무거운 사용 사례와 함께 몇 가지를 삭제하지만,다른 하나는 전반적으로 일치한다.나는 것이라고 생각 기본적으로 Harpreet 의 메커니즘하지 않는 한 나는 가장 작은 수를 제거할 수시로,때문에 노출시키는 약점에서는 알고리즘이 있습니다.

Answer 6

Harpreet:

에 삽입되는 것 linear 있기 때문에 이동하는 항목을 삽입합니다.

지 않는 것에 따라 구현의 컬렉션?는 경우 그와 같은 역할을 연결 목록,삽입될 것입 O(1),안 경우 구현 같은 배열 될 것으로,선형을 언급했다.

Answer 7

에 따라 필요한 작업의 컨테이너을 지원합니다.A min-힙 최고의 경우에 당신을 제거할 필요가 있을 수 있습 min 요소는 주어진 시간에,하지만 몇 가지 작업이 있는 사소(청산 로그(n)시간에 어떤 경우).

그러나만 필요한 경우 밀어/pop 에서 전/후,당신은 당신을 사용할 수 있 mindeque 을 달성하는 상각에 일정한 시간을 위해 모든 작업을 포함하여(findmin).당신이 할 수 있는 a scholar.google.com 검색 이에 대한 자세한 내용은 구조입니다.친구와 나는 최근에 협력에 도달하는 훨씬 쉽게 이해하고 구현하 버전의 mindeque,뿐만 아니라.이것이 무엇을 찾고 있는 대한 정보를 게시한 당신.