자료구조 :: 힙(1) 배열을 이용한 힙, 힙정렬

# 힙(Heap)

Heap.cpp

■ 힙의 정의
힙은 여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조다.
힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리 구조를 말한다.

■ 최대 힙(Max Heap)
부모 노드의 키값이 자식 노드의 키값보다 크거나 같은 완전 이진 트리
key(부모노드) ≥ key(자식노드)

■ 최소 힙(Min Heap)
부모 노드의 키값이 자식 노드의 키값보다 작거나 같은 완전 이진 트리
key(부모노드) ≤ key(자식노드)

■ 힙에서 자식 노드와 부모 노드의 관계
(1) 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
(2) 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
(3) 부모의 인덱스 = (자식의 인덱스)/2

[배열로 구현된 최대 힙]

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

#define MAX_ELEMENT 200

typedefstruct { 
int heap[MAX_ELEMENT]; 
int heap_size; 
}HeapType; 

void InsertHeap(HeapType *h,int data) 
{ 
int i; 
    i=++(h->heap_size); 

while(i != 1 && data > h->heap[i/2]) // 부모노드와 비교
    { 
        h->heap[i]=h->heap[i/2]; 
        i/=2; 
    } 

    h->heap[i]=data; 
} 

int DeleteHeap(HeapType *h) 
{ 
int parent=1,child=2; 
int data,temp; 

    data = h->heap[parent]; 
    temp = h->heap[(h->heap_size)--]; // 삭제에 의한 size 감소

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 data; 
} 

void sortHeap(HeapType *h,int *pArr) // 최대힙 정렬
{ 
int i; 

for(i=h->heap_size-1;i>=0;i--) 
    { 
        pArr[i]=DeleteHeap(h); // 요소를 반환하여 배열에 역순으로 저장
    } 
} 

int main() 
{ 
    HeapType heap; 
    heap.heap_size=0; 
int i,arr[5]; 

for(i=0;i<5;i++) 
    { 
        printf("Insert Item : %d\n",i); 
        InsertHeap(&heap,i); 
    } 

    printf("Heap Size : %d\n",heap.heap_size); 

//for(i=0;i<5;i++)
// printf("Delete Item : %d\n",DeleteHeap(&heap)); 

    sortHeap(&heap,arr); 
    printf("Heap Sort : "); 
for(i=0;i<5;i++) 
        printf("%d ",arr[i]); 

    printf("\n"); 

return0; 
}