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

알고리즘십습_4주차.pdf

0.11MB

##노트 정리 PDF

 

실습문제_4주차_문제1,2번_노트정리.pdf

2.64MB

##문제 풀기 전 알아야 할 개념(요약) :

1_ 상향식 힙 생성 :

과정 :

1. Heap에 한꺼번에 여러 원소를 저장한다.
2. 맨 마지막 노드의 부모노드부터 역순으로 루트노드까지 DownHeap과정을 거친다.

2_ 힙트리 + 제자리힙정렬 (중복된 키들이 들어간 힙트리도 적용된다.):

- 언제 쓰이는 지의 상황 : 상향식 힙트리 생성 과정을 거친 힙트리일 때,

- 과정 :

1. 루트노드와 마지막 노드 Swap
2. 맨마지막 노드를 삭제
3. 루트노드를 대상으로 DownHeap과정을 거친다.
4. 1~3번 과정을 Heap의 Size가 1이 될때 까지 반복

- 과정을 거친 후 결과 :

최대 힙 트리 → 오름차순으로 정렬된 Heap 배열

최소 힙 트리 → 내림차순으로 정렬된 Heap 배열

##코드 :

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#pragma warning (disable : 4996)
 
//힙트리 구조체
typedef int element;
 
typedef struct _HeapTree 
{
    element heap[MAX_SIZE];
    int size;
}Heap;
 
//부모, 왼자식, 오자식 인덱스 반환 메소드
int Parent(int i) 
{
    return i / 2;
}
 
int LeftChild(int i) 
{
    return i * 2;
}
 
int RightChild(int i) 
{
    return i * 2 + 1;
}
 
//UpHeap , DownHeap 메소드(최대 힙 기준)
 
void UpHeap(Heap* H, int i) 
{
    while (i>0&&H->heap[i]<H->heap[Parent(i)]) {
        element tmp = H->heap[i];
        H->heap[i] = H->heap[Parent(i)];
        H->heap[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->heap[Best] < H->heap[L]) Best = L;
    if (R <= H->size && H->heap[Best] < H->heap[R]) Best = R;
 
    if (Best == i) return;
    else {
        element tmp = H->heap[Best];
        H->heap[Best] = H->heap[i];
        H->heap[i] = tmp;
 
        DownHeap(H, Best);
    }
 
}
 
//InsertHeap
void InsertHeap(Heap* H, element data) 
{
    //예외조건
    if (H->size > MAX_SIZE) {
        printf("Heap Full!!\n");
        return;
    }
 
    H->heap[++H->size] = data;
 
    UpHeap(H, H->size);
}
 
//DeleteHeap
element DeleteHeap(Heap* H) {
 
    //예외조건 2가지 0 , 1
    if (H->size == 0) 
    {
        printf("Heap Empty!!\n");
        return -1;
    }
    else if (H->size==1) 
    {
        return H->heap[H->size--];
    }
 
    element root = H->heap[1];
    H->size--;
 
    DownHeap(H, 1);
}
 
void BuildHeap(Heap* H) {
    for (int i = Parent(H->size); i >= 1; i--)DownHeap(H, i);
}
 
//★InPlaceHeapSort
void InPlaceHeapSort(Heap* H) 
{
    //1_ Heap사이즈 임시 저장
    int origin_size = H->size;
    //역순으로 제자리 힙정렬 수행
    for (int i = H->size; i >= 1; i--) {
        //2_ 마지막 노드 , 루트 노드 교환
        element tmp = H->heap[1];
        H->heap[1] = H->heap[H->size];
        H->heap[H->size] = tmp;
 
        //3_ Heapsize 차감, DownHeap(루트노드)
        H->size--;
        DownHeap(H, 1);
    }
 
    //4_ Heapsize 복구
    H->size = origin_size;
 
    return;
}
 
void PrintHeap(Heap* H) 
{
    for (int i = 1; i <= H->size; i++) 
    {
        printf(" %d", H->heap[i]);
    }
    printf("\n");
}
 
int main() {
 
    int N;
 
    scanf("%d", &N);
 
    Heap* heap = (Heap*)malloc(sizeof(Heap));
 
    heap->size = N;
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &(heap->heap[i]));
    }
 
    BuildHeap(heap);
 
    InPlaceHeapSort(heap);
 
    PrintHeap(heap);
 
    free(heap);
 
 
    return 0;
}