데이터 구조 - 더미 의 실현 에 대한 심도 있 는 분석

소개 하 다
예전 에 학습 더미 에 있 을 때 두 편의 글 을 썼 습 니 다. 데이터 구조 - 더미 의 실현 (상)   화해시키다   데이터 구조 -- 더미 의 실현 (하),  더미 에 대한 인식 이 부족 한 것 같 습 니 다.본 고 는 주로 데이터 구조 더미 (작은 지붕 더미 토론) 의 기본 적 인 작업 의 세부 사항 을 분석 하고 자 한다. 예 를 들 어 insert (삽입) 작업 과 deleteMin (지붕 요소 삭제) 작업 의 실현 세부 사항, 쌓 인 시간 복잡 도, 쌓 인 장단 점 과 이 진 더미 의 부족 을 분석한다.
 
2. 더미 의 실현 분석
쌓 인 물리 적 저장 구 조 는 1 차원 배열 이 고 논리 적 저장 구 조 는 완전 이 진 트 리 이다.더미 의 기본 동작 은 insert - 더미 에 요 소 를 삽입 합 니 다.deleteMin -- 더미 요소 삭제
그러므로 쌓 인 유형 구 조 는 다음 과 같다.

public class BinaryHeap<T extends Comparable<? super T>> {
    
    private T[] array;
    private int currentSize;
    
    public BinaryHeap() {
        
    }
    
    public BinaryHeap(T[] array){
        
    }
    
    public void insert(T x){
        //do something
    }
    public T deleteMin(){
        
    }
    
    //other operations....
}

 
① insert 작업

1     public void insert(T x){
2         if(currentSize == array.length - 1)//  0       
3             enlarge(array.length * 2 + 1);0
4         
5         int hole = currentSize++;
6         for(array[0] = x; x.compareTo(array[hole / 2]) < 0; hole /= 2)
7             array[hole] = array[hole / 2];//       
8         array[hole] = x;//              
9     }

1) 수조 0 호 원 소 를 보초병 으로 하여 교환 조작 을 피 할 수 있다.
부모 노드 와 비교 하 는 과정 에서 부모 노드 가 삽입 할 노드 보다 크 면 부모 노드 와 삽입 할 노드 를 교환 해 야 하기 때문이다.보초병 을 도입 하면 삽입 할 노드 를 배열 0 호 요소 에 저장 하고 부모 노드 가 삽입 할 노드 보다 클 때 부모 노드 로 삽입 할 노드 (하위 노드) 를 직접 교체 합 니 다.
2) 복잡 도 분석
최 악의 경우 뿌리 노드 까지 비교 하면 끝 나 는 것 으로 나 타 났 다.따라서 insert 작업 시간 은 나무의 높이 에 달 려 있다.그러므로 복잡 도 는 O (logN) 이다.그러나 평균 적 인 상황 에서 insert 작업 은 O (1) 시간 만 있 으 면 완성 할 수 있 습 니 다. 모든 노드 가 루트 노드 로 배 치 된 것 이 아니 기 때문에 삽입 할 노드 의 가중치 가 가장 시간 이 지나 야 위로 올 라 갈 수 있 습 니 다.
그 밖 에 이 진 트 리 에 대해 서 는 부모 노드 작업: hole = hole/2 를 나 누 면 2 를 오른쪽 으로 한 자 리 를 옮 겨 서 실현 할 수 있 습 니 다.
따라서 d 포크 트 리 (이 진 트 리 d = 2 완성) 를 볼 수 있 고 d 가 크 면 나무의 높이 가 작 아 삽입 성능 이 어느 정도 향상 된다.왜 꼭 이 라 고 했 어 요?나중에 자세히 분석 해 보 겠 습 니 다.
 
② deleteMin 조작
deleteMin 작업 은 더미 의 마지막 요 소 를 첫 번 째 요 소 를 교체 한 다음 첫 번 째 요소 에서 아래로 쌓 아 올 립 니 다.

 1     public AnyType deleteMin( )
 2     {
 3         if( isEmpty( ) )
 4             throw new UnderflowException( );
 5 
 6         AnyType minItem = findMin( );
 7         array[ 1 ] = array[ currentSize-- ];//            
 8         percolateDown( 1 );//       
 9 
10         return minItem;
11     }

 

 1     /**
 2      * Internal method to percolate down in the heap.
 3      * @param hole the index at which the percolate begins.
 4      */
 5     private void percolateDown( int hole )
 6     {
 7         int child;
 8         AnyType tmp = array[ hole ];
 9 
10         for( ; hole * 2 <= currentSize; hole = child )
11         {
12             child = hole * 2;
13             if( child != currentSize &&
14                     array[ child + 1 ].compareTo( array[ child ] ) < 0 )
15                 child++;
16             if( array[ child ].compareTo( tmp ) < 0 )
17                 array[ hole ] = array[ child ];
18             else
19                 break;
20         }
21         array[ hole ] = tmp;
22     }

첫 번 째 원소 (퇴적 원소) 에서 아래로 퇴적 조정 을 할 때, 일반적으로 이 원 소 는 잎 결점 으로 조정 된다.쌓 인 원소 의 높이 는 나무의 높이 이다.그러므로 시간의 복잡 도 는 O (logN) 이다.
 
③ 다른 조작
1)decreaseKey(p,Δ)/increaseKey(p,Δ)---위치 p 곳 요소 의 가중치 변경
이 두 동작 은 일반적으로 자주 사용 되 지 않 습 니 다. 더미 의 성질 을 파괴 할 수 있 습 니 다. 따라서 p 요소 의 가중치 가 수정 되 었 을 때 더미 조정 이 필요 합 니 다. (decreseKey 는 위로 조정 하고 increaseKey 는 아래로 조정 합 니 다)
2) delete (p) -- 더미 의 위치 가 p 인 요 소 를 삭제 합 니 다.
앞에서 소개 한 deleteMin 작업 은 쌓 인 요 소 를 삭제 합 니 다. 쌓 인 요 소 를 어떻게 삭제 합 니까?
사실, 삭제 더미 의 모든 요소 (이 요소 의 위 치 는 p) 를 삭제 더미 요소 로 변환 할 수 있 습 니 다.
1) 에서 위치 p 에 있 는 요소 의 가중치 작업 을 수정 합 니 다: decrese (p,Δ).p 곳 요소 의 가중치 를 마이너스 무한대 로 낮 춥 니 다. 이 때 이 요 소 는 위로 올 라 가 더미 위로 조정 한 다음 deleteMin 을 실행 하면 됩 니 다.
 
3. 쌓 기 (buildHeap)
마지막 비 엽 점 부터 앞으로 내 려 가 조정 합 니 다.

1     /**
2      * Establish heap order property from an arbitrary
3      * arrangement of items. Runs in linear time.
4      */
5     private void buildHeap( )
6     {
7         for( int i = currentSize / 2; i > 0; i-- )
8             percolateDown( i );
9     }

i 의 초기 값 은 마지막 비 잎 결점 의 위치 입 니 다.
 시간 복잡 도 분석:
쌓 아 올 리 는 시간의 복잡 도 는 쌓 아 올 리 는 모든 결점 의 높이 와 같다.
 분석 은 다음 과 같다. 우선, 잎 결점 의 높이 는 0 이다. 쌓 아 올 리 는 것 은 마지막 비 잎 결점 부터 percolateDown (i), percolateDown (i) 을 계속 호출 하 는 것 이다.방법의 시간 복잡 도 는 바로 위치 i 점 노드 의 높이 입 니 다. 위의 7 줄 for 순환 에서 i 가 1 로 줄 었 을 때 이미 더미 요소 에 도 달 했 음 을 나타 내 므 로 전체 buildHeap 의 시간 복잡 도 는 모든 비 잎 결점 의 높이 의 합 입 니 다. 잎 결점 의 높이 는 0 이기 때문에 buildHeap 의 시간 복잡 도 는 전체 이 진 더미 의 모든 결점 의 높이 로 이해 할 수 있 습 니 다.하고
이상 적 인 두 갈래 더미 에 대해 말하자면 (두 갈래 더 미 는 완전한 두 갈래 나무 이 고 이상 적 인 두 갈래 더 미 는 두 갈래 나무 이다)
모든 결점 의 높이 는 2 ^ (h + 1) - 1 - (h + 1) 이다. 그 중에서 h 는 이 진 더미 의 높이 를 나타 낸다.
또한 N - b (N), N 은 더미 속 의 결점 의 개수 이 고 b (N) 는 N 의 이 진 표현법 중의 1 의 개수 이다. 예 를 들 어 b (7) = 3 이다.
 
더미
위 에서 이 진 더미 의 기본 조작 을 분 석 했 습 니 다. 그럼 d 더 미 는 무엇 입 니까? 왜 d 더 미 를 가지 고 있 습 니까?
두 갈래 더미 에 대해 d = 2. 말 그대로 d 더 미 는 모든 노드 에 d 명의 아들 이 있 는 더미 입 니 다. 왜 이런 더미 가 필요 합 니까?
이 진 더미 의 기본 동작 을 분석 하려 면 insert 작업 은 부모 의 결점 을 찾 아야 합 니 다. 이것 은 나눗셈 작업 이 필요 합 니 다. 작업 횟수 는 나무의 높이 와 관계 가 있 습 니 다. deleteMin 작업 은 모든 아들 중에서 가중치 가 가장 작은 아들 을 찾 아야 합 니 다. 아들 노드 를 찾 으 려 면 곱셈 작업 이 필요 합 니 다. 작업 의 복잡 도 는 아들 의 개수 와 관계 가 있 습 니 다 (d 가 클 수록 노드 의 아들 수가 많 고 찾기 가 느 립 니 다).
만약 에 우리 의 수 요 는 대량의 insert 작업 이 있 고 소량의 deleteMin 만 있다 고 가정 하면 d 더 미 는 이론 적 으로 성능 이 좋 습 니 다. d 가 2 보다 훨씬 클 때 나무의 높이 가 매우 작 기 때 문 입 니 다. 그러나 d 가 2 의 배수 가 아 닐 때 나눗셈 작업 은 자 리 를 옮 겨 서 이 루어 지지 못 하고 일정한 성능 손실 이 있 을 수도 있 습 니 다. 이것 도 insert 조작 분석 에서 말 한 이유 입 니 다."삽입 성능 이 어느 정도 향상 된다."
만약 에 대량의 deleteMin 작업 이 있다 면 d 더 미 는 오히려 저 성능 을 제거 할 수 있 습 니 다. d 가 클 수록 노드 의 아들 개수 가 많 을 수록 가중치 가 가장 작은 아들 을 찾 는 데 더 많은 비교 횟수 가 필요 하기 때 문 입 니 다.
이 를 통 해 알 수 있 듯 이 d 더미 의 제 기 는 수요 가 다 르 기 때문에 발생 한 것 이다. 예 를 들 어 insert 는 고주파 수요 에 속한다.
 
다섯, 이 진 더미 의 부족
위의 분석 에 따 르 면 이 진 더미 의 insert 복잡 도 O (logN), deleteMin 이 가장 나 쁜 것 도 O (logN) 이다.
하지만 더미 속 의 어떤 요 소 를 찾 아야 한다 면? 아니면 두 개의 더 미 를 합 쳐 야 할 까?
이 진 더미 의 경우 find 와 merge 작업 에 대한 지원 이 부족 합 니 다. 이 진 더미 의 저장 구조 에 의 해 결 정 됩 니 다. 이 진 더미 의 요 소 는 실제 배열 에 저장 되 어 있 기 때 문 입 니 다. 그 렇 기 때문에 모든 효율 적 인 통합 을 지원 하 는 고급 데이터 구 조 는 체인 데이터 구 조 를 사용 해 야 합 니 다.
 
여섯, 기타 형식의 "더미"
이 진 더미 의 부족 을 극복 하기 위해 일부 유형의 더 미 를 제 시 했 습 니 다. 주로 merge 와 find 작업 을 지원 하기 위해 서 입 니 다. 자세히 소개 하지 않 겠 습 니 다.
① 왼쪽 더미
더미 의 구조 에 대해 어느 정도 요구 가 있다. '0 경로 길이' 라 는 개념 이 있다. ① 임의의 노드 의 0 경로 길 이 는 각 아들 의 0 경로 길이 보다 최소 1 크다. ② 더미 의 모든 노드 에 대해 왼쪽 아들 의 0 경로 길 이 는 적어도 오른쪽 아들 의 0 경로 와 같다.
 
② 비스듬히 쌓 기
쌓 인 구조 에 대한 요구 가 없다.
 
③ 두 개의 대열
 가장 큰 특징 은 merge 작업 시간 복잡 도 는 O (logN) 이 고 insert 작업 의 평균 시간 복잡 도 는 O (1) 이다.