(3)실습3주차_힙과 힙정렬(1)_1_문제1번

알고리즘십습_3주차.pdf

0.15MB

##기억해야할 내용 :

• UpHeap()메소드

- 이론 :  맨 마지막 노드에 값을 삽입 후, 최대 힙 규칙에 맞춰, 적절한 위치로 부모노드로 올리는 메소드

- 매개변수 : Heap 구조체 포인터, 해당 조정할 노드의 인덱스(i)

- 코드상 순서 :

1_ Parent(i)의 노드와 i의 노드 SWAP

2_ i노드를 Parent(i)노드로 업데이트

3_ while로 i가 루트 도달 전 && 자식노드의 data > 부모노드의 data라면, 반복

 

 

• DownHeap()메소드

- 이론 :  해당 노드 값에서, 최대 힙 규칙에 맞춰, 적절한 위치로 자식노드로 내리는 메소드

- 매개변수 : Heap 구조체 포인터, 해당 조정할 노드의 인덱스(i)

- 코드상 순서 :

1_ △구조로, 부모노드를 (Best==i), 왼쪽자식(L), 오른쪽 자식을 (R)로 인덱스 지정

2_ 조건문으로 Best 노드 data vs L 노드 data =>  Best 노드 data vs R 노드 data 대결의 순서로, 가장 큰 노드의 인덱스를 Best로 업데이트

3_ 2의 과정을 거친 후, Best와 i가 같다면 => 그냥 종료 / ★Best와 i가 같지 않다면, SWAP하고, 

4_ ★재귀호출로 Best를 i로 지정 호출 

##전체 코드 :

 

#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
#pragma warning (disable : 4996)
 
typedef int element;
 
typedef struct _MaxHeap {
    element H[SIZE];
    int size;
} Heap;
 
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 Upheap(Heap* H, int i) {
    while (i > 0 && H->H[i] > H->H[Parent(i)]) {
        element tmp = H->H[i];
        H->H[i] = H->H[Parent(i)];
        H->H[Parent(i)] = tmp;
        i = Parent(i);
    }
}
 
void DownHeap(Heap* H, int i) {
    int Best = i;
    int L = LeftChild(i);
    int R = RightChild(i);
 
    if (L < H->size && H->H[L] > H->H[Best])
        Best = L;
 
    if (R < H->size && H->H[R] > H->H[Best])
        Best = R;
 
    if (Best != i) {
        element tmp = H->H[i];
        H->H[i] = H->H[Best];
        H->H[Best] = tmp;
        DownHeap(H, Best);
    }
}
 
void InsertItem(Heap* heap, element data) {
    if (heap->size >= SIZE) {
        printf("FULL HEAP!!\n");
        return;
    }
 
    heap->H[heap->size] = data;
    Upheap(heap, heap->size);
    heap->size++;
    printf("0\n");
}
 
element DeleteItem(Heap* H) {
    if (H->size == 0) {
        printf("Heap Empty!!\n");
        return -1;
    }
 
    element root = H->H[0];
    H->H[0] = H->H[--H->size];
    DownHeap(H, 0);
    return root;
}
 
void PrintHeap(Heap* H) {
    for (int i = 0; i < H->size; i++) {
        printf(" %d", H->H[i]);
    }
    printf("\n");
}
 
int main() {
    Heap* heap = (Heap*)malloc(sizeof(Heap));
    heap->size = 0;
 
    char sign;
 
    while (1) {
        scanf("%c", &sign);
        getchar();
 
        if (sign == 'i') {
            element input;
            scanf("%d", &input);
            InsertItem(heap, input);
            getchar();
 
        }
        else if (sign == 'd') {
            printf("%d\n", DeleteItem(heap));
        }
        else if (sign == 'p') {
            PrintHeap(heap);
        }
        else if (sign == 'q') {
            break;
        }
    }
 
    free(heap);
    return 0;
}