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

※문제에 대한 PDF는 아래의 링크에 있습니다.

https://kojammin.tistory.com/87

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

 

#이 문제를 풀기 위해 알아야 할 개념 :

1_ 상향식 힙 생성 :

1_1) 정의 : 우선 키의 개수와 키들을 한꺼번에 입력한 뒤, 리프 노드의 이전 레벨의 모든 노드를 DownHeap()과정을 거쳐 힙트리를 구성하는 방식이다.

1_2) 자세한 과정 :

ex_ 키의 개수 : 6 , 키의 구성 : 24 17 33 50 60 70

 

 

 

2_ 상향식 힙 생성 과 순차힙생성 과정의 비교 :

비교:

1. 결과:
   • 순차힙생성 과정과 상향식 힙생성 과정 모두 최대힙을 구성할 수 있지만, 순차힙생성 의 경우 순차적으로 삽입하는 방식에서 삽입 순서에 따라 결과가 달라질 수 있습니다.
   • 상향식 힙생성은 이미 주어진 모든 요소로 한 번에 힙을 생성하기 때문에 더욱 일관된 결과를 제공합니다.
2. 시간복잡도:
   • 순차힙생성 은 각 삽입마다 O(log n)이 걸리므로 전체적으로 O(n log n)의 시간이 소요됩니다.
   • 상향식 힙 생성는 O(n) 시간 복잡도로 더 빠르게 힙을 생성할 수 있습니다.

 

3_ 핵심 코드인  BuildHeap()메소드 :

우선 키들을 순차적으로 배열에 저장한 뒤, 맨 뒤의 인덱스의 부모노드부터 역순으로 루트노드까지 DownHeap()과정을 거치는 메소드이다.

##전체 코드

 

#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 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 BuildHeap(Heap* H) {
    for (int i = Parent(H->size - 1); i >= 0; i--) {
        DownHeap(H, i);
    }
}
 
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;
 
    int N;
 
    // 요소 개수 입력
    scanf("%d", &N);
 
    // 입력된 모든 요소를 배열에 저장
    for (int i = 0; i < N; i++) {
        scanf("%d", &heap->H[i]);
        heap->size++;
    }
 
    // 상향식 힙 생성
    BuildHeap(heap);
 
    // 힙 출력
    PrintHeap(heap);
 
    free(heap);
 
    return 0;
}
 

상향식 힙 생성 결과