정렬 알고리즘 (3) - 우선 대기 열, 쌓 기 정렬

본 고 는 주로 이 진 더미 데이터 구조의 우선 대기 열의 실현 과 파생 된 더미 정렬 을 바탕 으로 우선 대기 열 을 실현 하고 창고, 대기 열 등 데이터 구 조 를 사용 할 수 있 음 을 논의 하고 자 한다. 이 약 문 은 마지막 에 더미 정렬 전체 코드 를 첨부 한다.
우선 순위 대기 열
1. 주로 문 제 를 해결한다

             ，   ，           （  ）   
             （    ）        ，       。

다른 데이터 구조의 우선 대기 열 구현: 대기 열 (가장 오래된 요소 삭제) 및 스 택 (최신 요소 삭제) 유사
2. 이 진 더미 의 개념

 1）.                 ，      。
 2）.    ，   k   ，       k/2   ，    2k 2k+1
 3）.     N          lgN   。

3. 두 갈래 로 된 두 가지 중요 한 작업
1). 위 에서 아래로 질서 화 (상부) 더미 의 질서 있 는 상 태 는 어떤 결점 이 그의 아버지 결점 보다 더 커 졌 기 때문에 질서 있 는 상 태 를 깨 뜨리 려 면 아버지 결점 과 교환 하여 질서 있 는 더 미 를 다시 실현 해 야 한다.

    private void swim(int k)
    {
        while(k>1 && less(k/2,k))
        {
            exch(k/2,k); //  arr[k/2] arr[k]    
            k = k/2;     //        ，         
        }
    }

2). 아래 에서 위로 쌓 인 질서 화 (침하) 더미 의 질서 있 는 상 태 는 어떤 결점 이 그의 자 결점 보다 작 기 때문에 깨 지면 그 와 의 자 결점 에서 비교적 큰 것 을 교환 하여 질서 있 는 더 미 를 실현 해 야 한다.

    private void sink(int k)
    {
        while(2*k<=N)
        {
            int j = 2*k;
            if(j1))
                j++;
            if(!less(k,j))
                break;
            exch(k,j);
            k = j;
        }
    }

4. 이 진 더미 기반 우선 대기 열 구현
1). 요 소 를 삽입 하여 새 요 소 를 배열 의 끝 에 추가 하고 쌓 인 크기 를 증가 시 키 며 이 새 요 소 를 적당 한 위치 로 올 립 니 다.

    public void insert(T v)
    {
        arr[++N] = v;
        swim(N);
    }

2). 최대 요 소 를 삭제 하고 배열 의 맨 위 에서 최대 요 소 를 삭제 하 며 마지막 요 소 를 맨 위 에 올 려 놓 습 니 다 (이때 질서 있 게 쌓 여 깨 짐). 쌓 인 크기 를 줄 이 고 이 요 소 를 적당 한 위치 로 내 려 놓 습 니 다.

    public T delMax()
    {
        T del = arr[1];
        exch(1,N--);
        arr[N+1] = null; //      
        sink(1);
        return del;
    }

복잡 도 는 N 개의 요 소 를 포함 하 는 더미 우선 대기 열 에 대해 요 소 를 삽입 하 는 것 이 (lgN + 1) 회 를 초과 하지 않 고 요 소 를 삭제 하 는 작업 이 2lgN 회 를 초과 하지 않 습 니 다.
5. 쌓 기 정렬

    **1）.  ：**
              ，       ，                  
 **2）.  ：**

    public static void HeapSort(Comparable[] arr)
    {
        int N = arr.length;
        for(int k = N/2; k>=1; k--)
            sink(arr,k,N);
        while(N>1)
        {
            Hexch(arr,1,N--);
            sink(arr,1,N);
        }
    }

3). 복잡 도: 시간 복잡 도: NLogN 공간 복잡 도: 14). 쌓 기 정렬 특징: 현재 알 고 있 는 유일한 시간 과 공간 을 최 적 으로 이용 하 는 정렬 방법 - 최 악의 경우 에 도 ~ NLGN 차 를 비교 하 는 추가 공간 을 사용 할 수 있 습 니 다.따라서 쌓 기 정렬 은 공간 이 매우 긴 장 될 때 (내장 시스템 등) 에 적용 된다.정렬 전체 코드 쌓 기:

package sort;
/**
  * @author : luoz
  * @date time：2016 9 4    12:10:48 
**/
public class HeapSort {
     

    //        ，     1  ，      -1,  .
    private static boolean Hless(Comparable[] a,int i,int j)
    {
        return a[i-1].compareTo(a[j-1])<0;
    }

    private static void Hexch(Comparable[] a,int i,int j)
    {
        Comparable t = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = t;
    }

    //sink() a[],N    ,    .
    private static void sink(Comparable[] a,int k,int N)
    {
        while(2*k <= N)
        {
            int j = 2*k;
            if(j1)) 
                j++;
            if(!Hless(a,k,j))
                break;          
            Hexch(a,k,j);
            k = j;
        }
    }
    /**
     *     arr,N     .  
     * @param arr
     */
    public static void heapSort(Comparable[] arr)
    {
        int N = arr.length;
        for(int k = N/2; k>=1; k--)
            sink(arr,k,N);
        while(N>1)
        {
            Hexch(arr,1,N--);
            sink(arr,1,N);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Comparable[] HeapArray = {
    "A","C","E","D","K","Z"};     
        heapSort(HeapArray);        
        for(Comparable a : HeapArray)
            System.out.println(a);      
    }

}

알고리즘 제4 판

    ，