데이터 구조 (제5 장)

나무 밑 에서 제일 먼저 말 해 봐. 쌓 는 게 뭐야?더 미 를 이야기 하기 전에 우 리 는 우선 대열 이 무엇 인지 먼저 보 자.우선 대기 열: 특수 한 대기 열 입 니 다. 이름 으로 볼 때 우선, 말 그대로 꺼 낸 요 소 는 요소 가 대기 열 에 들 어 가 는 우선 순위 가 아 닙 니 다.우선 대기 열의 완전 이 진 트 리 는 더미 의 두 가지 특성 을 나타 낸다. 구조 성: 배열 로 표 시 된 완전 이 진 트 리 이다.질서 성: 모든 노드 의 키 워드 는 하위 트 리 의 모든 노드 의 최대 값 (또는 최소 값) 입 니 다.최대 치 와 최소 치 에서 우 리 는 새로운 개념 인 '최대 더미', '최소 더미' 의 최대 더 미 를 이 끌 어 낼 수 있다. 모든 노드 의 요소 수 치 는 하위 노드 의 요소 값 보다 작 지 않다.최소 더미: 모든 노드 의 요소 값 은 하위 노드 의 요소 값 보다 크 지 않 습 니 다.주로 가장 많은 작업 위 에 있 습 니 다. 가장 큰 모임 이 있 기 때문에 가장 작은 무 더 기 는 자연히 문제 가 되 지 않 습 니 다. 가장 많은 무 더 기 를 만 드 는 것 입 니 다.

typedef struct HeapStruct *MaxHeap;
struct HeapStruct
{
    ElementType *Elements[];//     
    int Size;//     
    int Capacity;//      
}
MaxHeap Create(int MaxSize)
{
    MaxHeap H=malloc(sizeof(struct Heapstruct));
    H->Elements=malloc((MaxSize+1)*sizeof(sizeof(ElementType));
    H->Size=0;
    H->Capacity=MaxSize;
    H->Elements[0]=Maxdata;// Maxdata  mindata           
    return 

가장 많은 삽입 알고리즘 은 새로 추 가 된 결점 을 아버지 결점 에서 뿌리 결점 까지 의 질서 있 는 서열 에 삽입 하면 우 리 는 가장 많은 질서 성 을 확보 하고 삽입 을 완성 할 수 있다 는 것 이다.

void Insert(MaxHeap H,ElementType item)
{
    int i;
    if(IsFull(H))
    {
        printf("  ");
        return;
    }
    i=++H->Size;//i                
    for(;H->Elements[i/2]<item;i/=2)
    {
        H->Elements[i]=H->Elements[i/2];//      
    }
    H->Elements[i]=item;//    
}

가장 많은 삭제 작업 을 하 는 알고리즘 은 루트 노드, 즉 우리 의 가장 큰 요 소 를 제거 하 는 동시에 더 미 를 삭제 하 는 것 입 니 다.

ElementType DeleteMax(MaxHeap H)
{
    int Parent,Child;
    ElementType MaxItem,temp;
    if(IsEmpty)//  
    {
        printf("  ");
        return;
    }
    MaxItem=H->Elements[1];//     ，   
    temp=H->Elements[H->Size--];
    for(Parent=1;Parent*2<=H->Size;Parent=Child)//                         
    {
        Child=Parent*2;
        if((Child!=H->Size)&&(H->Elements[Child]<H->Elements[Child+2]))
        {
            Child++;//       
        }
        if(temp>=H->Elements[Child])
            break;
       else
           H->Elements[Parent]=H->Elements[Child];     
    }
    H->Elements[Parent]=temp;
    return MaxItem;
}

두 번 째 는 헤 프 만 나무의 정의 와 원리 라 고 합 니 다. 헤 프 만 아 저 씨 는 나무의 한 노드 에서 다른 노드 사이 의 가 지 는 두 노드 사이 의 경 로 를 구성 하고 경로 의 가 지 는 경로 길이 라 고 합 니 다. 그러나 나무의 경로 길 이 는 뿌리 노드 에서 나무의 모든 노드 까지 의 경로 길이 와 같 습 니 다. 권한 을 가 진 경로 가 가장 작은 이 진 나 무 는 헤 프 만 나무 라 고 합 니 다.가장 좋 은 이 진 트 리 라 고도 부른다.헤 프 만 알고리즘 (헤 프 만 나 무 를 찾 는 데 사용) 설명: 주어진 n 개의 가중치 {w1, w2...} 에 따라 구 성 된 n 개의 이 진 트 리 의 집합 F = {T1, T2...}, 그 중에서 이 진 트 리 Ti 는 하나의 권한 만 있 고 좌우 자 트 리 는 모두 비어 있 습 니 다.F 에서 두 개의 노드 의 가중치 가 가장 작은 나 무 를 좌우 서브 트 리 로 선택 한 다음 에 새로운 이 진 트 리 를 만 들 고 새로운 이 진 트 리 의 뿌리 결산 점 의 가중치 는 좌우 나무 위의 뿌리 결산 점 의 가중치 의 합 이다.F 에서 이 두 그루 의 나 무 를 삭제 하고 새로 얻 은 이 진 트 리 를 F 에 넣 어 F 가 한 그루 의 나무 만 포 함 될 때 까지 이 절 차 를 반복 한다.그리고 이 나 무 는 헤 프 만 나무 다.그렇게 많은 말 을 했 지만 사실은 저도 잘 모 르 겠 습 니 다. 소감: 이 장 을 통 해 배 웠 습 니 다. 나무 와 숲 은 복잡 해 보이 지만 우 리 는 이 진 트 리 와 같은 규칙 적 인 나 무 를 통 해 이 를 규범화 시 킬 수 있 습 니 다. 규칙 이 있 으 면 우 리 는 규칙 에 따라 가면 버드나무 가 어 둡 고 꽃 이 밝 습 니 다. 그 다음 에 예전 에 여러 조 를 사용 하 는 것 을 좋아 했 던 것 은 간단 하고 조작 하기 쉬 웠 기 때 문 입 니 다. 그러나 지금 은 알 게 되 었 습 니 다.그것 은 공간 을 너무 낭비 하고 나무의 구 조 는 많은 공간 을 절약 하여 효율 을 높 였 다.