[자료구조] 힙(Heap)의 개념과 구조, 그리고 힙을 통한 우선순위큐 구현(C)

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

---

우선순위큐 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 연산 알고리즘 사용

Upheap 연산 알고리즘

1. 새로운 키(k) 삽입 후 heap의 성질 만족 확인(삽입된 노드 ~ 루트 노드까지 k와 비교)
2. 키 k 부모 노드(비교한 노드) 보다 크면 교환
   작으면 upheap 알고리즘 종료
   
   

• heap의 높이가 O(log n)이므로
  upheap 연산은 O(log n)이다.

 

---

힙(heap) 삭제 연산

• 최대 heap에서는 가장 큰 키 값을 가진 노드를 삭제하는 것
• 시간복잡도는 삽입 연산과 같음 → O(log n)

1. 루트 노드 삭제
2. 마지막 노드를 루트 노드로 이동
3. 루트에서 단말 노드까지의 경로에 있는 노드들을 교환하여 heap 조건 만족

• downheap 연산 알고리즘 사용

downheap 연산 그림

downheap 연산3

 

 

 

 

---

힙(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을 삽입한다.
// 삽입함수
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;
}

// 삭제 함수
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;
}
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);
    }

<출력>

< 30 > < 10 > < 5 >