최소 K 개수 찾기(더미로 구현)
1589 단어 더미 정렬
package ;
public class MaxPQ >{
private Key[] pq;
private int N = 0;
public MaxPQ(int maxN){
// 1-N
pq = (Key[])new Comparable[maxN+1];
}
private boolean less(int i,int j){
// ,i j , true
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i,int j){
//
Key t =pq[i];
pq[i] = pq[j];
pq[j] = t;
}
private void swim(int k){// , ,
while(k > 1 && less(k/2,k)){
exch(k/2,k);
k = k/2;
}
}
private void sink(int k){
// , ,
while(2*k <= N){
int j = 2*k;
if(j < N && less(j,j+1))
j++;
if(!less(k,j)) // k ,
break;
exch(k,j);
k = j;
}
}
public boolean isEmpty(){
return N == 0;
}
public int size()
{
return N;
}
public void insert(Key v){
pq[N++] = v;
swim(N);
}
public Key delMax(){
Key max = pq[1];
exch(1,N--); // ,
pq[N+1] = null;//
sink(1);
return max;
}
}
위의 코드는 비교적 완전하게 최대 무더기에 필요한 방법을 실현하였다.이렇게 하면 우리는 K개의 원소의 최대 더미를 유지하고 n-k개의 원소와 max를 비교한 다음에 작으면 이 원소를 삽입하고 그렇지 않으면 더미가 변하지 않는다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
석 주 - 데이터 구조 - 선택 & 쌓 기 정렬예전 에 내 가 가장 좋아 했 던 것 은 순 서 를 선택 하 는 것 이 었 다. 현재 요소 의 뒤에서 가장 작은 요 소 를 선택 하여 교환 하 는 것 이다. 쌓 기 정렬 은 빠 른 정렬 의 개선 으로 거품 처럼 빠르...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.