[쌓 기] 쌓 기의 정의 와 쌓 기 정렬

더미 정의:
더 미 는 특수 한 데이터 구 조 를 통칭 하 는데 더 미 는 보통 나무의 배열 대상 으로 볼 수 있다.
쌓 기 는 다음 과 같은 성질 을 만족시킨다.
1) 더미 의 특정한 노드 의 값 은 항상 아버지 노드 의 값 보다 크 거나 작 지 않다.
2) 더 미 는 항상 완전 이 진 트 리 이다.
완전 이 진 트 리: 마지막 층 을 제외 하고 모든 층 의 노드 수 는 최대 치 에 달 합 니 다.마지막 층 에는 오른쪽 에 있 는 몇 개의 결점 만 부족 하 다.
만 이 진 트 리: 나무 에는 잎 노드 를 제외 하고 모든 노드 에 두 개의 키 노드 가 있다.
완벽 한 이 진 트 리: 완전 이 진 트 리 의 성질 을 만족 시 키 고 나무의 잎 노드 는 모두 마지막 층 에 있다 (즉, 완벽 한 삼각형 을 형성 했다).
더미 의 정의: n 개 요소 의 서열 {k1, k2, ki,..., kn} 은 다음 과 같은 관 계 를 만족 시 킬 때 만 더미 라 고 합 니 다.
(ki < = k2i, ki < = k2i + 1) 또는 (ki > = k2i, ki > = k2i + 1), (i = 1, 2, 3,.., n / 2)
완전 이 진 트 리 의 모든 비 터미널 점 의 값 은 좌우 아이들 노드 의 값 보다 크 지 않 습 니 다.따라서 서열 {k1, k2,..., kn} 이 쌓 이면 쌓 인 요소 (또는 완전 이 진 트 리 의 뿌리) 는 서열 중 n 개 요소 의 최소 값 (또는 최대 값) 이 어야 합 니 다.
위 에서 알 고 있 는 무더기 의 성질 에 따라 큰 무더기 와 작은 무더기 로 나 뉜 다.즉, 쌓 기 요소 서브 시퀀스 n 개 요소 중 최대 치 또는 최소 치 입 니 다.쌓 기 정렬 은 바로 이 성질 에 따라 정렬 하 는 것 이다.
더미 정렬
단계:
1. 입력 한 시퀀스 {R1, R2, R3,..., Rn} 을 큰 더미 로 초기 화 합 니 다.
2. 쌓 인 요소 R [1] 을 마지막 요소 R [n] 과 교환 합 니 다. 이때 새로운 무질서 구역 (R1, R2,..., Rn - 1) 과 질서 구역 (Rn)
3. 교환 후의 새로운 무질서 구역 을 새로운 지붕 더미 로 조정 합 니 다.R1 을 마지막 요소 와 다시 교환 하여 새로운 무질서 구역 (R1, R2, R3,..., Rn - 2) 과 질서 구역 (Rn - 1, Rn) 을 얻 습 니 다.
4. 질서 있 는 구역 의 요소 개수 가 n - 1 일 때 까지 2, 3 과정 을 계속 반복 하면 정렬 이 완 료 됩 니 다.
주의: 첫 번 째 단계 에서 큰 무 더 기 를 초기 화하 고 세 번 째 단계 에서 큰 무 더 기 를 다시 조정 합 니 다. 시퀀스 의 비 엽 점 을 옮 겨 다 니 는 순서 가 다 릅 니 다.첫 번 째 단 계 는 마지막 에 잎 결점 에서 위로 조정 하고 세 번 째 단계 에서 가장 큰 더 미 를 조정 하 며 맨 위 결점 부터 아래로 조정 한다.
코드:

#include 

using namespace std;

/****
*   
*              （         ，        ）
*     R[1]       R[n]  ，       （R1,R2,...,Rn-1）    (Rn)
*          ，        。   R1         ，       （R1,R2,R3,...,Rn-2）    (Rn-1,Rn)
*       ，           n-1，     
****/

void sift_down(int *a, int start, int last){

    while(1){   //          ，                
        /*
        *          0  ，     i,     2*i+1,       2*i+2;
        *    1  ，     2*i,     2*i+１
        */
        int left = 2*start+1;  //        
        if(left>last){
            break;
        }
        if(left+1 <= last && a[left+1] > a[left]){  // #          ，          
            left += 1;
        }
        if(a[left] > a[start]){
            int temp = a[left];
            a[left] = a[start];
            a[start] = temp;

            start = left;   // #                      ，     
        }else{   //#           ，     
            break;
        }
        cout<< ">>";
        for(int i=0;i<=last;i++){
            cout<>n;
int a[n];
for(int i=0;i>a[i];
}
for (int i = n / 2 - 1; i > = 0; i -) {/ n / 2 - 1 은 마지막 아이 가 있 는 노드 를 표시 합 니 다. \ # 마지막 아이 가 있 는 노드 부터 위로 조정 합 니 다.
cout<0;head --) {/ / 이 for 순환, 더미 요소 와 더미 요 소 를 하나씩 교환 하기 시작 합 니 다.
/ / 교환 후 sift down 함 수 를 호출 하여 큰 더미 로 재 조정 합 니 다.
int team = a[head];
a[head] = a[0];
a[0] = team;
sift down (a, 0, head - 1); / / 쌓 아 올 리 는 노드 노드 부터 아래로 조정 하여 한 번 에 큰 쌓 아 올 리 기
}
for(int i=0;i<=n-1;i++){
cout<