[C/C++]최대 히프, 최소 히프

HeapDefine.h

MaximamHeap.h

MinimamHeap.h

 알고리즘을 배우면서 히프라는 것을 많이 보고 쓰게된다. 정렬이라던지 허프만이라던지 기타등등...

그래서 여기 최대히프와 최소히프를 올린다. 나도 참고하고 쓰실 분들도 참고하기 바란다.

1. HeapDefine.h

 최대 사이즈가 100으로 잡혀있다. 사이즈를 늘리고 싶으면 Define 헤더에서 늘려서 쓰도록하자.

#define MAX_ELEMENT 100

//히프 만들 때, 사용하는 히프노드

typedef struct

{

    int heap[MAX_ELEMENT];

    int heap_size;

} HeapType;

2. MaximamHeap.h

#include "HeapDefine.h"

//초기화 함수

void initMaxHeap(HeapType *h)

{

    h->heap_size = 0;

}

//삽입 함수

void insertMaxHeap(HeapType *h, int item)

{

    int i;

    i = ++(h->heap_size);

    

    while((i != 1) && (item > h->heap[i/2]))

    {

        h->heap[i] = h->heap[i/2];

        i /= 2;

    }

    h->heap[i] = item;

}

//삭제 함수

int deleteMaxHeap(HeapType *h)

{

    int parent, child;

    int item, temp;

    

    item = h->heap[1];

    temp = h->heap[(h->heap_size)--];

    parent = 1;

    child = 2;

    

    while(child <= h->heap_size)

    {

        if((child < h->heap_size) && (h->heap[child] < h->heap[child+1]))

            child++;

        

        if(temp >= h->heap[child])

            break;

        h->heap[parent] = h->heap[child];

        parent = child;

        child *= 2;

    }

    h->heap[parent] = temp;

    return item;

}

3. MinimamHeap.h 

#include "HeapDefine.h"

//초기화 함수

void initMinHeap(HeapType *h)

{

    h->heap_size = 0;

}

//삽입 함수

void insertMinHeap(HeapType *h, int item)

{

    int i;

    i = ++(h->heap_size);

    

    while((i != 1) && (item < h->heap[i/2]))

    {

        h->heap[i] = h->heap[i/2];

        i /= 2;

    }

    h->heap[i] = item;

}

//삭제 함수

int deleteMinHeap(HeapType *h)

{

    int parent, child;

    int item, temp;

    

    item = h->heap[1];

    temp = h->heap[(h->heap_size)--];

    parent = 1;

    child = 2;

    

    while(child <= h->heap_size)

    {

        if((child < h->heap_size) && (h->heap[child] > h->heap[child+1]))

            child++;

        

        if(temp <= h->heap[child])

            break;

        h->heap[parent] = h->heap[child];

        parent = child;

        child *= 2;

    }

    h->heap[parent] = temp;

    return item;

}