(17)[Chapter7]최소힙트리_이론,삽입,삭제_코드

Chapter7_2_최소힙트리_코드이론.pdf

2.74MB

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
#pragma warning (disable : 4996)
 
//힙트리 구조체
 
typedef int EType;
 
typedef struct _HeapNode 
{
    EType heap[MAX_SIZE];
    int size;
}Heap;
 
 
//구조체 생성, 초기화 메소드
 
Heap* CreateHeap(Heap* H) 
{
    H = (Heap*)malloc(sizeof(Heap));
    H->size = 0;
 
    return H;
}
 
//해당 인덱스 대입 시, 부모, 왼자, 오른자 인덱스 반환 메소드
int Parent(int i) 
{
    return (i - 1) / 2;
}
 
int LeftChild(int i) 
{
    return (2*i + 1);
}
 
int RightChild(int i)
{
    return (2 * i + 2);
}
 
//힙트리 노드 삽입 메소드(최소힙)
void InsertHeap(Heap* H , EType data) 
{
    //예외 조건 : 힙트리가 가득 찼다면,
    if (H->size == MAX_SIZE) 
    {
        printf("Heap Full!!\n");
        return;
    }
 
    //★맨 마지막 인덱스 임시 저장 후, 유효사이즈 증감
    int i = H->size++;
 
    H->heap[i] = data;
 
    while ((i>0)&&(H->heap[i]<H->heap[Parent(i)]))
    {
        EType tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[Parent(i)]=tmp;
 
        i = Parent(i);
 
    }
 
    return;
}
 
 
//최소힙 제거 메소드
int DeleteHeap(Heap* H) 
{
    //예외 조건 : 유효개수 0, 1개일 경우
    if (H->size == 0) 
    {
        printf("Heap empty!!\n");
        return -1;
    }
    else if (H->size == 1) 
    {
        //유효개수 감소후
        H->size--;
        return H->heap[0];
    }
 
    //root노드 반환용 변수에 저장
    int root = H->heap[0];
    //root노드에 마지막 노드값 저장, 유효개수 차감
    H->heap[0] = H->heap[--H->size];
 
    int i = 0;
 
    while (1) 
    {
        //삼각형으로 각 인덱스 초기화
        int smallest = i;
        int L = LeftChild(i);
        int R = RightChild(i);
 
        //판단 순서 : smallest => L => R
        if ((H->heap[L] < H->heap[smallest]) && (L < H->size)) 
        {
            smallest = L;
        }
        if ((H->heap[R] < H->heap[smallest]) && (R < H->size))
        {
            smallest = R;
        }
        //smallest자리 변화x => 멈춤
        if (smallest == i) break;
 
        //smallest와 i와 SWAP
        EType tmp = H->heap[smallest];
        H->heap[smallest] = H->heap[i];
        H->heap[i] = tmp;
 
        //smallest자리 i 업데이트
        i = smallest;
 
 
    }
    //제거된 값 반환
    return root;
}
 
void PrintHeap(Heap* H) {
    printf("MinHeap : ");
    for (int i = 0; i < H->size; i++) {
        printf("%d ", H->heap[i]);
    }
    printf("\n");
 
}
int main() {
    Heap *H=NULL;
    H=CreateHeap(H);
 
    InsertHeap(H, 3);
    InsertHeap(H, 1);
    InsertHeap(H, 6);
    InsertHeap(H, 5);
    InsertHeap(H, 2);
    InsertHeap(H, 4);
 
    PrintHeap(H);
 
    printf("Deleted root: %d\n", DeleteHeap(H));
    PrintHeap(H);
 
    return 0;
}

 

 

위의 코드 출력 장면