더미 03 추출 & 가라앉기

E extractMax() - 추출 더미에서 가장 큰 요소

더미 중 가장 큰 원소:

더미 중에서 가장 큰 원소는 바로 더미 꼭대기의 원소이다

두 갈래 나무의 측면에서 볼 때 무더기에서 가장 큰 원소는 두 갈래 나무의 뿌리 노드이다

수조의 측면에서 볼 때 무더기에서 가장 큰 원소는 수조의 색인이 0인 원소이다

추출 더미에서 가장 큰 원소:

더미에서 가장 큰 원소를 찾아 되돌려주는 것은 간단하지만 추출은 가장 큰 원소를 더미에서 삭제하는 것과 관련된다(즉 논리적으로 두 갈래 나무의 뿌리를 삭제하고 물리적으로 수조 인덱스가 0인 원소를 삭제하는 것), 잉여 원소의 구조를 재구성하여 더미의 정의를 만족시킬 수 있도록 해야 한다

가장 많은 더미 중의 더미 요소를 구체적으로 삭제하는 방법은 다음과 같다.

더미 원소와 더미 중의 마지막 원소가 서로 위치를 바꾸게 한다

더미 중의 마지막 원소, 즉 방금 바뀐 원소의 지붕 원소를 삭제한다

새로운 더미 원소를 가라앉히고 전체 두 갈래 나무가 더미의 정의를 다시 만족시킨다

//  
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

//  
public E extractMax(){
    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

void siftDown(int k) - 새 더미 요소 가라앉히기

가라앉는 종지 조건, 즉 k가 가리키는 원소는 가라앉을 공간이 없다. 이 상태는 k의 왼쪽 아이의 인덱스는size보다 크고size는 인덱스의 측면에서 볼 때 다음 코드 원소의 위치를 가리킨다.더미에 원소가 하나밖에 없다면size=1,size는 더미 원소의 왼쪽 아이를 가리킨다. 더미 원소의 왼쪽 아이의 색인도 1이다. 다음 더미 원소의 코드 위치는 더미 원소의 왼쪽 아이의 위치이다. 이것은 더미 원소가 왼쪽 아이가 없고 오른쪽 아이가 없다는 것을 의미한다. 이것이 바로 k가 가라앉는 공간이 없는 상태이다. k는 왼쪽 아이가 있다

바늘 j로 k의 왼쪽 아이를 가리킨다

k가 오른쪽 아이가 있는지 확인하고 k의 오른쪽 아이가 k의 왼쪽 아이보다 크다. 그러면 j가 k의 오른쪽 아이를 가리키게 한다. 그렇지 않으면 j가 k의 왼쪽 아이를 가리킨다. 이때 j는 k의 가라앉은 것으로 추정되는 위치를 가리킨다

k와 그 가라앉은 것으로 추정되는 위치를 비교한 결과 k가 가라앉은 위치로 추정되는 원소보다 작지 않으면 가라앉지 않고 순환을 벗어나 가라앉는 동작이 끝난다

만약에 k가 가라앉은 위치로 추정되는 원소보다 작으면 가라앉는 동작을 시작하고 k와 가라앉은 위치로 추정되는 원소를 교환한다

가라앉는 것이 완성된 후 k로 하여금 가라앉을 원소를 다시 따라잡게 한다

private void siftDown(int k){
    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); 
        //  k ， 
        if( j + 1 < data.getSize() &&
                data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;   // j   leftChild   rightChild  
    
        //  ， ， 
        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;
        
        // k   j  ， 
        data.swap(k, j);
        // k  
        k = j;
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

더미 03 추출 & 가라앉기

E extractMax() - 추출 더미에서 가장 큰 요소

void siftDown(int k) - 새 더미 요소 가라앉히기

좋은 웹페이지 즐겨찾기