호우동의 개발일지

Today :

article thumbnail
Published 2022. 12. 20. 21:49
[자료구조] 우선순위 큐 - 힙(Heap)과 연결리스트로 이해,구현 그리고 응용 Computer Science/Data Structure

우선순위 큐

  • 우선순위를 가진 항목들을 저장하는 큐

 

우선순위큐 ADT

  • 객체
    • n개의 element형의 우선순위를 가진 요소들의 모임

  • 연산
    • create() ::= 우선순위 큐를 생성
    • init(q) ::= 우선순위 큐 q를 초기화
    • is_empty(q) ::= 우선순 큐 q가 비어있는지를 검사
    • is_full(q) ::= 우선순위 큐 q가 가득 찼는가를 검사
    • insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    • delete(q) : = 우선순위 큐 q로부터 가장 우선순위가 높은 요소를 삭제 및 반환
    • find(q) ::= 우선순위가 가장 높은 요소를 반환

  • 우선순위 큐는 2가지로 구분
    • 최솟값 우선수위 큐
      • 작을수록 우선순위가 높음

    • 최댓값 우선순위 큐
      • 높을수록 우선순위가 높음

 

우선순위 큐 구현방법

  • 배열로 구현
    • 순서 없는 배열
      • 삽입 : O(1)
      • 삭제 : O(n)

    • 정렬된 배열
      • 삽입 : O(n)
      • 삭제 : O(1)

  • 연결리스트를 이용한 우선순위 큐
    • 순서 없는 연결리스트
      • 삽입 : O(1)
      • 삭제 : O(n)

    • 정렬된 연결 리스트
      • 삽입 : O(n)
      • 삭제 : O(1)

  • 힙(heap)을 이용한 우선순위 큐
    • 삽입 = 삭제 = O(logn)

 

힙(heap)

  • 노드들이 저장하고 있는 키들이 다음 조건을 만족하는 완전이진트리
    • 최대 힙(max heap) → key(부모노드) ≥ key(자식노드)

      최대 힙

    • 최소 힙(min heap) → key(부모노드) ≤ key(자식노드)

최소힙

 

힙(heap)의 높이

  • n개의 노드를 가지고 있는 힙의 높이 = O(log n)

 

힙(heap)의 구현 방법

  • 배열로 구현
    • 완전 이진트리이므로 밀집된 배열로 구성 → 편리함
    • 각 노드에 번호를 매김 → 배열로 인덱스로 사용

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

부모노드와 자식 노드의 관계
부모 노드와 자식 노드의 관계

 

힙(heap) 구조체

힙 구조체
힙 구조체

#define MAX_ELEMENT 200

typedef struct{
    int key;
}element;

typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size
}HeapType;

 

힙(heap) 삽입 연산

  1. 새로운 요소가 들어오면 새로운 노드를 heap의 마지막 노드에 이어서 삽입
  2. 삽입 후에 새로운 노드를 부모 노드들과 교환해서 heap의 조건 만족
  • Upheap 연산 알고리즘 사용
    1. 새로운 키(k) 삽입 후 heap의 성질 만족 확인
      • 삽입된 노드 ~ 루트 노드까지 k와 비교

    2. 키 k 부모 노드(비교한 노드) 보다 크면 교환
      작으면 upheap 알고리즘 종료
      • heap의 높이가 O(log n)이므로 upheap 연산은 O(log n)이다

Upheap 연산 알고리즘
Upheap 연산 알고리즘

 

힙(heap) 삭제 연산

  • 최대 heap에서는 가장 큰 키 값을 가진 노드를 삭제하는 것
  • 시간복잡도는 삽입 연산과 같음 → O(log n)
  1. 루트 노드 삭제
  2. 마지막 노드를 루트 노드로 이동
  3. 루트에서 단말 노드까지의 경로에 있는 노드들을 교환하여 heap 조건 만족
  • downheap 연산 알고리즘 사용

downHeap 연산 알고리즘
downheap 연산 알고리즘
downHeap 연산 알고리즘
downHeap 연산 알고리즘
downheap 연산 알고리즘
downheap 연산 알고리즘

 

힙(heap) 정렬

  • heap을 이용하여 정렬을 구현
    1. 정렬해야 할 n개의 요소들을 최대 heap에 삽입
    2. 한 번에 하나씩 요소를 heap에서 삭제하여 저장

  • 삭제되는 요소들은 값이 증가되는 순서(최소 heap)의 경우
  • 하나의 요소를 heap에 삽입하거나 삭제할 때 시간
    • O(log n) 만큼 소요되고 요소의 개수가 n개이므로 전체적으로 O(nlogn)

  • N개의 데이터 중 오름차순/내림차순으로 X개 뽑고자 할 때 특히 유용하게 쓰인다.

 

힙(heap) 트리 구현

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

#define MAX_ELEMENT 200

typedef struct{
    int key;
}element;

typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;

// 생성 함수
HeapType* create(){
    return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h){
    h -> heap_size = 0;
}

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입함수(최대 heap)
void insert_max_heap(HeapType *h, element item){
    int i;
    i = ++(h->heap_size);

    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while((i != 1) && item.key > h -> heap[i/2].key){
        h -> heap[i] = h -> heap[i/2];
        i /= 2;
    }
    h ->heap[i] = item;
}

// 삭제 함수(최대 heap)
element delete_max_heap(HeapType* h){
    int parent, child;
    element 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].key < h -> heap[child+1].key))) child++;
        if(temp.key >= h -> heap[child].key) break;

        // 한단계 아래로 이동
        h->heap[parent] = h ->heap[child];
        parent = child;
        child *= 2;
    }
    h -> heap[parent] = temp;
    return item;
}

// 우선 순위 큐인 heap를 이용한 정렬
void heap_sort(element a[],int n)
{ 
    int i;
    HeapType *h;

    h = create();
    init(h);

    for(i = 0; i < n; i++) insert_max_heap(h,a[i]);

    for(i = n-1; i >= 0; i--) a[i] = delete_max_heap(h);
}
int main(){

        element e1 = {10}, e2 = {5}, e3 = {30};
        element e4,e5,e6;
        HeapType* heap;

        heap = create();
        init(heap);

        insert_max_heap(heap, e1);
        insert_max_heap(heap, e2);
        insert_max_heap(heap, e3);

        e4 = delete_max_heap(heap);
        printf("< %d > ", e4.key);
        e5 = delete_max_heap(heap);
        printf("< %d > ", e5.key);
        e6 = delete_max_heap(heap);
        printf("< %d > ", e6.key);
        free(heap);
        printf("\n");


        element a[] = {1,4,2,5};

                // heap sort 이전
        printf("a = ");
        for(int i = 0; i < 4; i++) printf("%d ", a[i]);
        heap_sort(a,4);
        printf("\n");
                // heap sort 이후
        printf("a = ");
        for(int i = 0; i < 4; i++) printf("%d ", a[i]);
    }

<출력>

< 30 > < 10 > < 5 > 
a = 1 4 2 5 
a = 1 2 4 5

 

최소 Heap 트리 구현

void insert_min_heap(HeapType *h, element item){
    int i;
    i = ++(h->heap_size);

    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while((i != 1) && item.key < h -> heap[i/2].key){
        h -> heap[i] = h -> heap[i/2];
        i /= 2;
    }
    h ->heap[i] = item;
}

// 삭제 함수
element delete_min_heap(HeapType* h){
    int parent, child;
    element 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].key < h -> heap[child+1].key))) child++;
        if(temp.key >= h -> heap[child].key) break;

        // 한단계 아래로 이동
        h->heap[parent] = h ->heap[child];
        parent = child;
        child *= 2;
    }
    h -> heap[parent] = temp;
    return item;
}

 

최소 Heap 트리 응용 : 머신 스케줄링

// ------- 구현한 최소 힙 트리 함수 ------- //

#define JOBS 7
#define MACHINES 3

int main(){
    int jobs[JOBS] = {8,7,6,5,3,2,1}; // 작업은 정렬되어 있다고 가정
    element m = {0,0};
    HeapType* h;
    h = create();
    init(h);

    for(int i = 0; i < MACHINES; i++){
        m.id = i+1;
        m.avail = 0;
        insert_min_heap(h,m);
    }
    // 최소 heap에서 기계를 꺼내서 작업을 할당하고 사용가능 시간을 증가시킨 후
    // 다시 최소 히프 추가
    for(int i = 0; i < JOBS; i++){
        m = delete_min_heap(h);
        printf("JOBS %d을 시간 =%d부터 시간 =%d까지 기계%d번에 할당\n"
        ,i,m.avail,m.avail + jobs[i]-1,m.id);
        m.avail += jobs[i];
        insert_min_heap(h,m);
    }
    return 0;
}

<출력>

JOBS 0을 시간 =0부터 시간 =7까지 기계1번에 할당
JOBS 1을 시간 =0부터 시간 =6까지 기계3번에 할당
JOBS 2을 시간 =7부터 시간 =12까지 기계3번에 할당
JOBS 3을 시간 =8부터 시간 =12까지 기계1번에 할당
JOBS 4을 시간 =13부터 시간 =15까지 기계3번에 할당
JOBS 5을 시간 =13부터 시간 =14까지 기계1번에 할당
JOBS 6을 시간 =15부터 시간 =15까지 기계1번에 할당

 

Heap 정렬 응용 : 허프만 코드

  • 이진트리는 각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는 데 사용 가능
    • 이런 종류의 이진트리 → 허프만 코딩 트리

  • 허프만 코드 생성 절차

허프만 코드 생성 절차
허프만 코드 생성 절차

 

허프만 코드 프로그램

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

#define MAX_ELEMENT 100

// 트리 구조체
typedef struct TreeNode{
    int weight; // 빈도수
    char ch; // 문자
    struct TreeNode *left_child;
    struct TreeNode *right_child;
}TreeNode;

typedef struct{
    TreeNode *ptree; //가리키는 노드
    char ch;
    int key;
}element;

typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;

// 생성 함수
HeapType* create(){
    return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h){
    h -> heap_size = 0;
}

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입함수
void insert_min_heap(HeapType *h, element item){
element delete_min_heap(HeapType* h){}
// 위에서 구현한 최소 heapTree

TreeNode *make_tree(TreeNode *left, TreeNode* right){
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node -> left_child = left;
    node -> right_child = right;
    return node;
}

void destory_tree(TreeNode* root){
    if(root == NULL) return;
    destory_tree(root -> left_child);
    destory_tree(root -> right_child);
    free(root);
}
// 단말 노드인지 확인
int is_leaf(TreeNode* root){
    return !(root->left_child) && !(root->right_child);
}

// 배열 출력
void print_array(int codes[],int n){
    for(int i = 0; i < n; i++) printf("%d",codes[i]);
    printf("\n");
}

// 출력 함수
void print_codes(TreeNode* root, int codes[], int top){

    // 1을 저장하고 순환호출한다.
    if(root -> left_child){
        codes[top] = 1;
        print_codes(root->left_child,codes,top+1);
    }
    // 0을 저장하고 순환호출한다.
    if(root -> right_child){
        codes[top] = 0;
        print_codes(root->right_child,codes,top+1);
    }
    if(is_leaf(root)){
        printf("%c", root ->ch);
        print_array(codes,top);
    }
}

//허프만 코드
void huffman_tree(int freq[], char ch_list[], int n){
    int i;
    TreeNode *node, *x;
    HeapType* heap;
    element e, e1, e2;
    int codes[100];
    int top = 0;

    heap = create();
    init(heap);

    for(i = 0; i<n; i++){
        node = make_tree(NULL,NULL);
        e.ch = node -> ch = ch_list[i];
        e.key = node->weight = freq[i];
        e.ptree = node;
        insert_min_heap(heap,e);
    }
    for(i=1;i<n;i++){
        // 최소값을 갖는 두 개의 노드 삭제   
        e1 = delete_min_heap(heap);
        e2 = delete_min_heap(heap);

        // 두개의 노드를 합친다.
        x = make_tree(e1.ptree,e2.ptree);
        e.key = x->weight = e1.key + e2.key;
        e.ptree = x;
        insert_min_heap(heap,e);
    }
    e = delete_min_heap(heap);
    print_codes(e.ptree,codes,top);
    destory_tree(e.ptree);
    free(heap);
}
int main(){
    char ch_list[] = {'s','l','n','t','e'};
    int freq[] = {15,12,8,6,5};
    huffman_tree(freq,ch_list,5);
    return 0;
}

<출력>

t1
n01
s001
e0001
l0000

 

 

추가구현

최소 힙 트리 - 입력받아서 저장하고 우선순위대로 일 출력하기

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

#define MAX_ELEMENT 200

typedef struct{
    int num;
    char* text;
}element;

typedef struct{
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;

// 생성 함수
HeapType* create(){
    return (HeapType*)malloc(sizeof(HeapType));
}
// 초기화 함수
void init(HeapType* h){
    h -> heap_size = 0;
}
void insert_min_heap(HeapType *h, element item){
    int i;
    i = ++(h->heap_size);

    // 트리를 거슬러 올라가면서 부모 노드와 비교
    while((i != 1) && item.num < h -> heap[i/2].num){
        h -> heap[i] = h -> heap[i/2];
        i /= 2;
    }
    h ->heap[i] = item;
}

// 삭제 함수
element delete_min_heap(HeapType* h){
    int parent, child;
    element 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].num< h -> heap[child+1].num))) child++;
        if(temp.num >= h -> heap[child].num) break;

        // 한단계 아래로 이동
        h->heap[parent] = h ->heap[child];
        parent = child;
        child *= 2;
    }
    h -> heap[parent] = temp;
    return item;
}

#define JOBS 7
#define MACHINES 3

int main(){
    char input;
    HeapType* h = create();
    init(h);

    while(1){
        printf("삽입(i), 삭제(d): ");
        scanf("%s",&input);

        char *txt = (char*)malloc(sizeof(char) * 10);
        switch(input){
            case('i'):
                element item;
                printf("\n 할일 : ");
                scanf("%s",txt);
                item.text = txt;
                printf("\n 우선순위 : ");
                scanf("%d", &item.num);
                insert_min_heap(h,item);
            break;
            case('d'):
                printf("%s\n",delete_min_heap(h).text);
            break;
            case('q'):
            printf("프로그램을 종료합니다\n");
                exit(1);
            break;
            default:
            printf("잘못입력하셨습니다. 다시 입력하세요\n");
            break;
        }
    }
}

<출력>

삽입(i), 삭제(d): i

 할일 : 옷 입기

 우선순위 : 삽입(i), 삭제(d): 잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): i

 할일 : do work

 우선순위 : 삽입(i), 삭제(d): 잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): i   

 할일 : i

 우선순위 : f
삽입(i), 삭제(d): 잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): i       

 할일 : djfjf

 우선순위 : 1
삽입(i), 삭제(d): x
잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): q
junpyohong@hongjunpyoui-MacBookPro 자료구조 % ./DS18HongJunpyo01
삽입(i), 삭제(d): i

 할일 : 안녕

 우선순위 : 2
삽입(i), 삭제(d): i

 할일 : 짐 옮기기

 우선순위 : 삽입(i), 삭제(d): 잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): i

 할일 : 짐 옮기기

 우선순위 : 삽입(i), 삭제(d): 잘못입력하셨습니다. 다시 입력하세요
삽입(i), 삭제(d): i

 할일 : 기다리기

 우선순위 : 3
삽입(i), 삭제(d): 걷i 

 할일 : 걷기

 우선순위 : 1
삽입(i), 삭제(d): d
걷기
삽입(i), 삭제(d): d
짐
삽입(i), 삭제(d): d
기다리기
삽입(i), 삭제(d): d
짐
삽입(i), 삭제(d): q

 

연결리스트로 Heap 트리 구현(Max-Heap)

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

// 연결리스트 구조체
typedef struct LinkedList
{
    int data;
    struct LinkedList *link; // 자기 참조 구조체
} LinkedList;

LinkedList *create()
{
    return (LinkedList *)malloc(sizeof(LinkedList));
}

LinkedList *init(LinkedList *head)
{
    head->data = 0;
    head->link = NULL;
}
int is_empty(LinkedList *head)
{
    return (head == NULL);
}
int is_full(LinkedList *head)
{
    return 0;
}

LinkedList *insert_max_heap(LinkedList *head, int item)
{
    if (head == NULL)
    {
        head = create();
        head->data = item;
        return head;
    }

    LinkedList *p = head;
    LinkedList *pre = NULL;
    LinkedList *node = (LinkedList *)malloc(sizeof(LinkedList));
    node->data = item;

    while (p != NULL)
    {
        if (p->data <= item)
        {
            if (pre == NULL)
            {
                head = node;
                head->link = p;
            }
            else
            {
                node->link = p;
                pre->link = node;
            }
            return head;
        }
        pre = p;
        p = p->link;
    }

    pre->link = node;
    node->link = NULL;

    return head;
}

// 첫번째 노드를 삭제하는 함수
int delete_max_heap(LinkedList *head)
{
    LinkedList *removed = head;
    head = head->link;
    int value = removed->data;
    free(removed);
    return value;
}
int find_max(LinkedList *head)
{
    return head->data;
}
// 노드 출력
void print(LinkedList *head)
{
    // 노드가 NULL일때까지 즉, 마지막 노드까지 반복
    for (LinkedList *p = head; p != NULL; p = p->link)
    {
        printf("%d ", p->data);
    }
    printf("\n");
}

int main()
{
    LinkedList *h = create();
    h = insert_max_heap(h, 1);
    h = insert_max_heap(h, 5);
    h = insert_max_heap(h, 2);
    h = insert_max_heap(h, 4);
    h = insert_max_heap(h, 5);
    h = insert_max_heap(h, 2);
    h = insert_max_heap(h, 3);

    print(h);
    printf(" 가장 큰 값 : %d\n", find_max(h));
}

<출력>

5 4 3 2 2 1 0 
 가장 큰 값 : 5
저작자표시 변경금지

검색 태그

0-1
1005
1010
10282
1043
10844
1092
10942
10진표기법
11049
11053
11054
11055
11509
11657
11660
1167
11724
11779
1182
12015
12100
1238
12851
12865
12933
13023
13172
1343
13460

티스토리툴바