어떤 값으로 요소를 정렬하는 우선 순위 대기열이 있습니다 (이름을 정할 수 있음). 등급에 따라 대기열에서 요소를 가져와야합니다. 그래서 함수 queue_get (rating)을 구현해야합니다. 이 함수는 또한 우선 순위 힙으로 괜찮은 등급을 증가시킵니다.우선 순위 큐 임의 액세스
하지만 문제는 힙의 각 레벨이 등급에 따라 정렬되지 않는다는 것입니다. 각 레벨의 요소는 힙 특성 만 만족시킵니다. 따라서 N 번째 요소를 등급으로 반환 할 수는 없습니다.
이러한 기능을 가진 우선 순위 대기열의 구현이 있습니까? 다른 데이터 구조를 사용해야합니까?
가장 간단한 해결 방법은 자동 밸런싱하는 이진 검색 트리를 사용하는 것입니다. AVL 트리, 스플레이 트리 또는 레드 - 블랙 트리. O (log n) 시간에 해당 키를 사용하여 요소에 액세스하고 O (log n + k)에서 순서대로 오브젝트를 반복 할 수 있습니다. 여기서 k는 반복되는 요소의 수입니다.
컬렉션 클래스는 일반적으로 java.util.TreeMap 또는 C++ std :: map과 같은 정렬 된 키를 기반으로하는 Map을 제공합니다. 이것을 사용하면 정렬 된 순서로 항목을 검색 할 수 있습니다. 클래스가 항목을 증가하는 순서로 제공하면 순서를 뒤집을 수 있습니다. 너가하고 싶은 모두는 너를 위해 이젠 그만이어야하는 최고 N 품목을 읽는이다.
N 번째 가장 높은 항목에 무작위로 액세스하려면 각 노드 아래에 항목 수가있는 트리 데이터 구조에 주석을 달아 수행 할 수 있지만 널리 사용 가능한 클래스 라이브러리를 알지 못합니다.
N 개의 가장 높은 항목을 순서대로 검색하려면 항목을 읽을 때 해당 항목을 제거 할 준비가되어있는 경우 우선 순위 대기열을 사용하여이 작업을 수행 할 수 있습니다. 나중에 원래 내용을 복원해야하는 경우
등급이 동일 할 수 있습니다. 등급을 변경할 때 같은 등급으로 요소의 맨 위로 이동하려면 요소가 필요합니다. 예를 들어, 다음과 같은 목록이 있습니다. a : 3 b : 2 c : 2 d : 1 등급을 올리면 다음과 같이 표시됩니다. a : 3 d : 2 b : 2 c : 2 그것으로? – sashab
요소를 두 개의 키로 정렬합니다. 먼저 등급 (내림차순)과 두 번째로 등급이 변경된 시간 순서 (내림차순)로 정렬합니다. –