자료구조 Heap

//Heap.h 헤더 파일을 만든다.

//힙에 가장 작은 데이터를 갖는 노드는 루트 노드이다.
//1. 힙에 새로운 노드를 삽입하는 연산
//2. 힙의 최소값을 삭제하는 연산

/*
힙에 새로운 노드 삽입
1. 힙의 최고 깊이, 최 우측에 새 노드를 추가한다. 물론 이때 완전 이진트리를 유지해야 한다.
2. 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 제 위치에 삽입된 것이므로 연산을 종료한다.
하지만 부모 노드보다 작으면 다음 단계로 진행한다.
3. 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 서로 바꾼다. 바꾸고 나면 다시 2단계를 진행한다. */

/*힙의 최소값 삭제
1. 힙의 루트에 최고 깊이, 최 우측에 있던 노드를 루트노드로 옮겨온다.
이때 힙의 속성이 파괴된다. 이를 복원하기 위한 작업을 다음 단계에서부터 시작한다.

2. 옮겨온 노드의 양쪽 자식을 비교하여 작은쪽 자식과 위치를 교환한다. 
3. 옮겨온 노드가 더 이상 자식이 없는 리프 노드가 되거나, 양쪽 자식보다 작은 값을 갖는 경우에는 삭제 연산을 종료한다.
그렇지 않은 경우에는 2단계를 반복한다. 
*/

#ifndef HEAP_H
#define HEAP_H

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef int ElementType;

typedef struct tagHeapNode {
        ElementType Data;
}HeapNode;

typedef struct tagHeap {
        HeapNode* Nodes;
        int Capacity;
        int UsedSize;
}Heap;

Heap* Create(int InitialSize);
void Destroy(Heap* H);
void Insert(Heap* H, ElementType NewData);
void DeleteMin(Heap* H, HeapNode* Root);
int GetParent(int index);
int GetLeftChild(int index);
void SwapNodes(Heap* H, int Index1, int Index2);
void PrintNodes(Heap*H);
#endif

====================================================================================

Heap* Create(int InitialSize){
        Heap* NewHeap = (Heap*)malloc(sizeof(Heap));
        NewHeap->Capacity = InitialSize;
        NewHeap->UsedSize = 0;
        NewHeap->Nodes = (HeapNode*)malloc(sizeof(HeapNode)*NewHeap->Capacity);

        printf("size : %d\n", sizeof(HeapNode));

        return NewHeap;
}

void Destroy(Heap* H){
        free(H->Nodes);
        free(H);
}

void Insert(Heap* H, ElementType NewData){
        int CurrentPosition = H->UsedSize;
        int ParentPosition = GetParent(CurrentPosition);

        if (H->UsedSize == H->Capacity) {
                H->Capacity *= 2;
                H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode)*H->Capacity);
        }
        H->Nodes[CurrentPosition].Data = NewData;

        while (H->Nodes[CurrentPosition].Data < H->Nodes[ParentPosition].Data) {
                SwapNodes(H, CurrentPosition, ParentPosition);

                CurrentPosition = ParentPosition;
                ParentPosition = GetParent(CurrentPosition);
        }
        H->UsedSize++;
}

void DeleteMin(Heap* H, HeapNode* Root){
        int ParentPosition = 0;
        int LeftPosition = 0;
        int RightPosition = 0;

        memcpy(Root, &H->Nodes[0],sizeof(HeapNode));
        memset(&H->Nodes[0], 0, sizeof(HeapNode));
        H->UsedSize--;
        SwapNodes(H, 0, H->UsedSize);

        LeftPosition = GetLeftChild(0);
        RightPosition = LeftPosition + 1;
        while (1) {
                int SelectedChild = 0;
                //자식이 없는 경우
                if (LeftPosition >= H->UsedSize) break;

  //오른쪽에 자식이 없는 경우(왼쪽에만 있는 경우)
                if (RightPosition >= H->UsedSize)
                        SelectedChild = LeftPosition;
  else { //양쪽 모두 자식이 있는 경우
                        if (H->Nodes[LeftPosition].Data > H->Nodes[RightPosition].Data)
                                SelectedChild = RightPosition;
                        else SelectedChild = LeftPosition;
                }

                if (H->Nodes[ParentPosition].Data > H->Nodes[SelectedChild].Data) {
                        SwapNodes(H, ParentPosition, SelectedChild);
                        ParentPosition = SelectedChild;
                }
                else {
                        break;
                }
                LeftPosition = GetLeftChild(ParentPosition);
                RightPosition = LeftPosition + 1;
        }
        if (H->UsedSize < (H->Capacity) / 2) {
                H->Capacity /= 2;
        }
}
int GetParent(int index){
        return (index - 1) / 2;
}

int GetLeftChild(int index){
        return (2 * index) + 1;
}

void SwapNodes(Heap* H, int Index1, int Index2){
        int CopySize = sizeof(HeapNode);
        HeapNode* Temp = (HeapNode*)malloc(CopySize);
        memcpy(Temp, &H->Nodes[Index1], CopySize);
        memcpy(&H->Nodes[Index1], &H->Nodes[Index2], CopySize);
        memcpy(&H->Nodes[Index1], Temp, CopySize);
}

void PrintNodes(Heap*H){
        for (int i = 0; i < H->UsedSize; i++) {
                printf("%d", H->Nodes[i].Data);
        }
        printf("\n");
}

void main() {
        Heap* H = Create(3);
        HeapNode MinNode;

        Insert(H, 12);
        Insert(H, 87);
        Insert(H, 111);
        Insert(H, 34);
        Insert(H, 16);
        Insert(H, 75);

        PrintNodes(H);

        DeleteMin(H, &MinNode);
        PrintNodes(H);
        system("pause");
}