자바 에서 Priority Queue 는 최소 더미 와 최대 더미 의 용법 을 실현 합 니 다.

기본 소개
 1.소개
많은 알고리즘 지식 을 배우 고 최선 을 다 하 는 학습 과정 에서 Priority Queue(우선 대기 열)를 만 날 때 가 많 습 니 다.우선 순위 더 미 를 기반 으로 한 무한 우선 순위 대기 열우선 순위 대기 열의 요 소 는 자연 순서에 따라 정렬 하거나 구조 대기 열 에서 제공 하 는 Comparator 에 따라 정렬 하 며 구체 적 으로 사용 하 는 구조 방법 에 달 려 있다.우선 순위 대기 열 에 서 는 null 요 소 를 사용 할 수 없습니다.자연 순서에 의존 하 는 우선 순위 대기 열 은 비교 할 수 없 는 대상 을 삽입 할 수 없습니다.이렇게 하면 ClassCastException 을 초래 할 수 있 습 니 다.
이 대기 열의 머리 는 지정 한 정렬 방식 에 따라 최소 요소 입 니 다.만약 여러 원소 가 모두 최소 치 라면 머리 는 그 중의 한 원소 인 선택 방법 은 임의의 것 이다.대기 열 에서 작업 poll,remove,peek,element 가 대기 열 헤더 에 있 는 요 소 를 가 져 옵 니 다.우선 순위 대기 열 은 무한 하지만 내부 용량 이 있어 대기 열 요 소 를 저장 하 는 배열 크기 를 제어 합 니 다.그것 은 보통 적어도 대열 의 크기 와 같다.우선 순위 대기 열 에 요 소 를 계속 추가 하면 서 용량 이 자동 으로 증가 합 니 다.용량 증가 정책 의 세부 사항 을 지정 할 필요 가 없습니다.
이러한 교체 기 는 Collection 과 Iterator 인터페이스의 모든 선택 방법 을 실현 합 니 다.방법 iterator()에서 제공 하 는 교체 기 는 우선 순위 대기 열 에 있 는 요 소 를 특정한 순서 로 옮 겨 다 니 는 것 을 보장 하지 않 습 니 다.순서대로 옮 겨 다 닐 필요 가 있다 면 Arrays.sort(pq.toArray()를 사용 하 는 것 을 고려 하 십시오.이 구현 은 동기 화 되 지 않 습 니 다.여러 스 레 드 의 임의의 스 레 드 가 대기 열 을 수정 하면 이 스 레 드 는 Priority Queue 인 스 턴 스 를 동시에 방문 해 서 는 안 됩 니 다.반면 스 레 드 가 안전 한 Priority BlockingQueue 류 를 사용 하 십시오.
Priority Queue 는 우선 대기 열 로 번역 되 었 습 니 다.'우선'은 요소 가 대기 열 에 일정한 순서(우선 순위)로 저장 되 는 것 을 말 합 니 다.'대기 열'은 선진 적 인 데이터 구 조 를 말 합 니 다.따라서 Priority Queue 는 일정한 우선 순위 에 따라 요 소 를 액세스 할 수 있 습 니 다.

2.용법
소스 코드 로 볼 때 Priority Queue 의 구조 방법:

//      11
private static final int DEFAULT_INITIAL_CAPACITY = 11;

//1、    ，           
public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
//2、    
public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }
//3、      
public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }
//4、         
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

위 에서 알 수 있 듯 이 Priority Queue 를 구성 할 때 초기 용량 과 요소 가 대기 열 에 있 는 정렬 방법 을 지정 할 수 있 습 니 다.지정 하지 않 으 면 기본 초기 용량 은 11 이 고 기본 정렬 방법 은 요 소 를 작은 것 에서 큰 것 으로 정렬 하 는 것 입 니 다.
3.최소 더미
구조 최소 더미:

PriorityQueue<Integer> minheap = new PriorityQueue<>();

무 참 구 조 를 사용 합 니 다.요 소 는 대기 열 에서 기본적으로 작은 순서 로 배열 되 어 있 으 며,매번 대기 열 에서 나 오 는 요 소 를 대기 열 에서 가장 작은 요소 로 보장 할 수 있 습 니 다.
4.최대 더미

PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());

정렬 방법 을 역순 으로 지정 합 니 다.즉,요 소 를 큰 것 에서 작은 것 으로 배열 하면 매번 대기 열 에 나 오 는 요 소 를 대기 열 에서 가장 큰 요소 로 보장 할 수 있 습 니 다.
5,기타 우선 순위
다른 우선 순위 규칙 에 따라 정렬 하려 면 Comparable 인 터 페 이 스 를 실현 하고 compare To()방법 을 다시 써 야 합 니 다.

Comparable<Integer> comparable = new Comparable<Integer>() {
            @Override
            public int compareTo(Integer o) {
                return 0;
            }
        };

상용 방법
Integer 형식 을 예 로 들 면:

3.관련 연습 문제
【 검지 Offer 40.최소 k 개수 】
정수 배열 arr 를 입력 하여 가장 작은 k 개 수 를 찾 아 보 세 요.예 를 들 어 4,5,1,6,2,7,3,8 이라는 8 개의 숫자 를 입력 하면 가장 작은 4 개의 숫자 는 1,2,3,4 이다.
예시 1:
입력:arr=[3,2,1],k=2
출력:[1,2]또는[2,1]
예시 2:
입력:arr=[0,1,2,1],k=1
출력:[0]
제한:
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
[문제 풀이 사상]
먼저 k 개 수 를 최대 더미 에 넣 은 다음 에 k+1 개 수 를 비교 합 니 다.만약 에 큰 지붕 보다 작 으 면 더 미 를 넣 고 더 미 를 쌓 아 대열 을 만 들 고 더 크 면 아무것도 하지 않 습 니 다.
【코드】

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int res[] = new int[k];
        int len = arr.length;
        if(len == 0 || k == 0)
            return res;

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < k; i++){
            maxHeap.add(arr[i]);
        }
        for(int i = k; i < len; i++){
            if(arr[i] < maxHeap.peek()){
                maxHeap.add(arr[i]);
                maxHeap.poll();
            }
        }
        
        for(int i = 0; i < k; i++){
            res[i] = maxHeap.poll();
        }
        return res;
    }
    
}

시간 복잡 도:O(nlogn)
자바 에서 Priority Queue 가 최소 더미 와 최대 무 더 기 를 실현 하 는 용법 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 Priority Queue 에 관 한 최소 최대 무 더 기 는 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 저 희 를 많이 사랑 해 주세요!