Java 우선 순위 대기열 인터페이스 구현

이것은 인터뷰에서 며칠 전 질문을 받았으며 접근 방법에 대해 확신하지 못했습니다. 제안은 매우 높이 평가 될 것입니다 :Java 우선 순위 대기열 인터페이스 구현

O (1)에서 queue() 메소드를 가져오고 O (n)에서 dequeue() 메소드를 가져 오려면 어떻게 PriorityQueue 인터페이스를 구현할 수 있습니까?

O (1)에서 O (n) 및 dequeue() 메소드의 queue() 메소드를 가져 오려면 PriorityQueue 인터페이스를 구현할 수 있습니까?

감사합니다.

출처

2010-07-24 Rachel

는 I 희망 위치가 평판 하나 O 걸린다. – mdma

흠 ... 나는 그렇게 생각했다. – Rachel

@mdma - 농담 하시겠습니까? 아니면 정말로 당신의 의견을 의미합니까? – Rachel

일반적인 PriorityQueue 구현은 "추가"작업에 대해 O (lg n) 성능을 얻기 위해 힙을 사용하므로 O (n) 성능이 훨씬 더 쉬워집니다.

예를 들어 벡터 또는 링크 된 목록을 기본 데이터 구조로 사용할 수 있습니다. O (1)의 경우 "추가"를 클릭하면 끝에 새 값을 간단히 추가 할 수 있으며 O (n)의 경우 "최소값"에 대한 선형 검색을 수행 할 수 있습니다. 반대로 O (n) "add"의 경우 선형 스캔을 수행하여 다음으로 큰 값을 찾은 다음 O (1)을 제거하면 목록의 첫 번째 요소 만 제거 할 수 있습니다.

출처

2010-07-24 00:15:48 maerics

queue() 메소드에 대한 O (1) 접근 방식의 경우 큐의 크기에 관계없이 큐의 마지막 요소를 추적해야 이후에 하나를 쉽게 추가 할 수 있습니다.

대기열의 O (n) 및 dequeue()의 O (1)에 대해 변수의 대기열의 첫 번째 요소를 추적해야하므로 그 안에있는 요소의 수에 관계없이 항상 일련의 명령어 세트 (반복 없음)로 목록에서 첫 번째 명령어를 제거 할 수 있습니다.

두 경우 모두 하나의 추가 변수를 클래스에 추가하기 만하면됩니다. 난 당신이 데이터 구조, 목록,지도, 등등에 대한 기본적인 이해가 가정 P

: 모든 좋은 프로그래머가 좋은 코드를 복사

http://www.docjar.com/html/api/java/util/PriorityQueue.java.html

가 기억

출처

2010-07-24 00:15:57

동일한 코드 예제를 제공 할 수 있습니까? 그것의 여기에서 이해하기 어렵다. – Rachel

글쎄, 지금 당장은별로 없지만, Nodes를 사용하여 직접 만든 Java PriorityQueue를 구현하면 쉽게 만들 수 있습니다. 노드 클래스를 만듭니다. 여기서 노드는 객체가있는 엔티티이고 다음 노드에 대한 참조입니다. 그런 다음 첫 번째 노드/마지막 노드에 대한 참조를 가진 목록을 만드십시오. [O (1)을 대기열에 넣거나 대기열에서 풀거나 둘 중 하나를 선택하는 경우에 따라 다름] 완료되면 완료됩니다. 핵심 Java의 PriorityQueue 클래스가 어떻게 구현되는지는 모르겠지만 이런 식으로 구현 될 수도 있습니다. 출처를 확인하는 것이 하나의 예가 될 수 있습니다. –

그냥 좀 봐 당신이하지 않으면,이 작품이 더 의미가되지 않는 방법을 이해하고 대신 주제에 대해 조사하십시오. O에서

출처

2010-07-24 00:16:18

큐() 메소드는 (1)과 (N) O의 대기열에서 제외() 메소드 :

링크 된 목록을 사용하여 단순히 큐리스트의 머리에 직접 모든 새로운 항목을 추가(). dequeue()에서 목록을 반복하고 우선 순위가 가장 높은 항목을 제거한 다음 반환합니다. 연결리스트 다시

사용 : O O에서의

큐() 메소드 (N)와 디큐() 메소드 (1). 그러나 이번에 queue()에서 엔트리를 반복하여 새로운 엔트리를 우선 순위 정렬 된 위치에 놓습니다 (이것은 실제로 삽입 정렬의 한 단계입니다). dequeue()에서 이제 항상 목록의 첫 번째 요소를 제거하고 반환 할 수 있습니다.

출처

2010-07-24 00:20:05 x4u