데이터 구조 - 더미 의 기본 작업 (더미 의 구축, 삽입, 삭제 등) 에 대한 상세 한 설명

머리말
데이터 구조의 - 더미 (Heap) 이 블 로 그 는 쌓 인 개념 을 대충 설명 했다. 그 다음 에 쌓 인 기본 적 인 작업 들 은 모두 최대 더미 (큰 더미) 를 예 로 들 었 다.
쌓다

#define MAXDATA 10000
struct HNode {
    int* Data;         			   //         
    int Size;          			   //          
    int Capacity;      			   //        
};
//      MaxSize       
HNode* CreateHeap(int MaxSize) {
    HNode* H = new HNode;
    H->Data = new int[MaxSize + 1];//            1  
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0] = MAXDATA;          //  "  "             ,       10000
    return H;
}

판단 이 비다

bool IsFull(HNode* H)
{
    return (H->Size == H->Capacity);
}
bool IsEmpty(HNode* H)
{
    return (H->Size == 0);
}

더미 삽입
생각:

삽입 하기 전에 더미 가 가득 찼 는 지 판단 하고 불만 이 있 으 면 먼저 잎 노드 에 삽입 합 니 다

이때 쌓 인 논리 구조 가 정확 한 지 판단 하고 정확 하지 않 으 면 정확 할 때 까지 조정 한다

HNode* Insert(HNode* H, int key) {
    if (IsFull(H)) {
        cout << "The heap is full
";    //      
        return H;                        //     
    }
    int i = ++H->Size;                   //   Size  1，   i          ，
    for (; H->Data[i / 2] < key; i /= 2) //       key        
            H->Data[i] = H->Data[i / 2]; //   key
    H->Data[i] = key;                    //   key
    return H;                            //     
}

최대 더미 요소 삭제
더 미 는 특수 한 '대기 열' 입 니 다. 요 소 를 꺼 내 는 순 서 는 요소 의 우선권 (키워드) 크기 에 따라 삭제 작업 은 루트 노드 를 삭제 하 는 것 입 니 다.

뿌리 노드 를 삭제 한 후에 우 리 는 두 개의 키 트 리 가 있 을 것 이다. 우 리 는 이 를 바탕 으로 재 구성 해 야 한다.

먼저 마지막 노드 를 새로운 노드 로 만 들 고 새로운 이 진 트 리 를 구성한다.

새로운 뿌리 노드 와 서브 노드 를 계속 비교 합 니 다.만약 에 새로운 노드 가 두 개의 키 노드 중 큰 노드 보다 작다 면 이 노드 와 교환 합 니 다.이 노드 가 어느 하위 노드 보다 작 지 않 거나 잎 노드 가 될 때 까지.

int DeleteMax(HNode* H)
{
    int Parent, Child;
    int MaxItem, X;

    if (IsEmpty(H)) {
        cout << "The heap is empty
";                                  //     
        return -1;                                                      //      
    }

    MaxItem = H->Data[1];                                               //            
    X = H->Data[H->Size--];                                             //X          ，  Size  
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
            Child++;                                                    // Child            
        if (X >= H->Data[Child]) break;                                 //    X   
        else                                                            //   X 
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MaxItem;
}

Ps: 오류 가 있 으 면 지적 을 환영 합 니 다.