Java 힙의 애플리케이션 시나리오 및 구현 방법 소개
- PHPz앞으로
- 2023-04-24 08:28:141676검색
1. 힙 생성
1. 아래쪽으로 조정(예: 작은 힙)
부모가 조정이 필요한 노드를 표시하고 자식이 부모의 왼쪽 자식을 표시하도록 합니다(참고: 부모가 자식, 먼저 왼쪽 자식이 있어야 함)
부모의 왼쪽 자식이 존재하는 경우, 즉 child
부모의 오른쪽 자식이 존재하는지 여부 , 왼쪽과 오른쪽 자식 중에서 가장 작은 자식을 찾아 자식이 표시하게 합니다.
부모와 작은 자식을 비교합니다. 다음과 같은 경우:
부모가 작은 자식보다 작으면 조정이 종료됩니다. 부모를 더 작은 자식과 교체합니다. 교체가 완료된 후 부모의 더 큰 요소 아래로 이동하면 하위 트리가 힙의 속성을 충족하지 못할 수 있으므로 아래쪽으로 계속 조정해야 합니다. 즉, 부모 = 자식입니다. child = parent*2+1; 그런 다음 2단계를 계속합니다.
public void shiftDown(int[] elem,int parent,int len){
int cur=parent*2+1;
while(cur<len){
if(cur+1<len){
if(elem[cur+1]<elem[cur]){
cur++;
}
}
if(this.elem[cur]<this.elem[parent]) {
swap(cur, parent);
}
parent=cur;
cur=parent*2+1;
}
}2. 힙 만들기
일반적인 시퀀스의 경우 전체 트리가 힙의 속성을 충족할 때까지 첫 번째 상위 노드부터 왼쪽 노드로 조정을 시작해야 합니다.
3. 힙 생성의 시간 복잡도
힙은 완전한 이진 트리여야 하며, 전체 이진 트리도 완전한 이진 트리입니다. 다음 계산에서 힙 생성의 시간 복잡도는 O(n)입니다.
2. 힙 삽입 및 삭제
1. 힙 삽입
삽입할 요소를 맨 마지막에 넣습니다. 힙을 해제할 수 없으면 용량을 확장하세요
새로 삽입된 노드를 힙의 속성에 맞을 때까지 위쪽으로 조정하세요
【상향 조정】
public void shiftUp(int elem[],int child){
int parent=(child-1)/2;
while(parent>=0){
if(elem[child]>elem[parent]){
swap(child,parent);
child=parent;
parent=(child-1)/2;
}else{
break;
}
}
}2.
힙의 속성에 따라 삭제되는 것은 힙의 최상위 요소여야 합니다. 단계는 다음과 같습니다.- 힙의 최상위 요소를 마지막 요소로 교환
- 힙의 요소 수를 1씩 줄입니다.
- 힙의 최상위 요소를 아래쪽으로 조정
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] array=new int[k];
if(arr==null||arr.length<=k||k==0){
return array;
}
PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
int i=0;
for(;i<k;++i){
queue.offer(arr[i]);
}
while(i<arr.length){
if(arr[i]<queue.peek()){
queue.poll();
queue.offer(arr[i]);
}
i++;
}
int size=queue.size();
for(int j=0;j<size;++j){
array[j]=queue.poll();
}
return array;
}
} IV. 공통 인터페이스 소개 1. PriorityQueue의 특징 Java 컬렉션 프레임워크는 PriorityQueue와 PriorityBlockingQueue라는 두 가지 유형의 우선순위 큐를 제공합니다. PriorityQueue는 스레드에 안전하지 않으며 PriorityBlockingQueue는 스레드에 안전합니다. 이 기사에서는 주로 PriorityQueue를 소개합니다. [PriorityQueue] 사용에 대한 참고 사항:
- PeioriryQueue 패키지를 가져와야 합니다.
- 배치된 요소는 크기가 비슷해야 합니다. 그렇지 않으면 ClassCastException이 발생합니다. 그렇지 않으면 null 요소를 배치할 수 없습니다. , NullPointerException이 발생합니다.
- 원하는 만큼 요소를 삽입할 수 있으며 내부 용량은 자동으로 확장됩니다.
- 하단 레이어는 힙 데이터 구조를 사용하며 기본값은 작은 힙입니다. 큰 힙을 구축하려면 비교기를 제공해야 합니다.
- PriorityQueue 확장 방법:
- 용량이 64보다 크거나 같으면 1.5배로 확장됩니다. oldCapacity
- 용량이 MAX_ARRAY_SIZE를 초과하는 경우 MAX_ARRAY_SIZE에 맞게 확장하세요.
int newCapacity = oldCapacity + ((oldCapacity
(oldCapacity + 2) :
(oldCapacity >> 1));2. 사용자는 비교기 개체를 사용하도록 선택할 수도 있습니다. user 사용자 정의 유형 객체를 삽입할 때 Comparator 인터페이스를 구현하고 비교 메서드를 재정의하는 비교기 클래스를 제공해야 합니다
PriorityQueue는 Comparble과 Comparator의 두 가지 메서드를 사용합니다.
1. Comparble은 기본 내부 비교 방법입니다. 사용자가 사용자 정의 유형 개체를 삽입하는 경우 개체는 Comparble 인터페이스를 구현하고 CompareTo 메서드를 재정의해야 합니다.
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
2、优先级队列的构造
| 构造器 | 功能介绍 |
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) |
创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常 |
| PriorityQueue(Collection extends E> c) |
用一个集合来创建优先级队列 |
위 내용은 Java 힙의 애플리케이션 시나리오 및 구현 방법 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!