컴퓨터과학 자료구조 우선순위 큐, 힢(heap)

힢의 정의

 - 피라미드 모양으로 쌓아올린 더미

 - 쌓아놓은 더미이고 항상 가장 위의 것을 우선 꺼낸다.

 - 부모-자식 노드사이에서 정렬된 포화 이진트리로 부모노드는 자식노드보다 우선순위가 높다.

우선순위 큐

 - 큐 : 선입선출

 - 우선순위 큐 : 대기 리스트에서 항상 우선순위가 높은 것을 먼저 처리

힢의 추상자료형

 - 힢 객체의 정의 : 부분적으로 정렬된 포화이진트리로 부모노드는 자식노드보다 우선순위가 높다.

최소힢 : 루트가 전체 노드 중에서 최소값인 힢

최대힢 : 루트가 전체 노드 중에서 최대값인 힢

힢 구현을 위한 자료구조

 - 힢은 완전이진트리라서 배열로 구현해도 기억장소 낭비가 적다.

 - 연결리스트보다 효율적, 기억장소 측면에서도 장점

연습문제

1. 다음 설명은 무엇에 대한 설명인가 ?  최대 힢

트리의 모든 노드가 자식 노드보다 큰 값을 가짐

⇨ 트리의 레벨에 따라 데이터가 순서를 갖지는 않음

⇨ 탐색 트리처럼 왼쪽, 오른쪽 노드 사이에 크기 제한도 없음

⇨ 루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨

2. (가)의 값은?

void insertHeap(HeapType *h, int item) {

     int i;

     i = ++(h->heap_size);

     while((i != 1) && (item < h->heap[i/2])) {

           (가) : h -> heap[i] = h -> heap[i/2]  // 부모노드와 크기비교

        i /= 2;

     }

     h->heap[i] = item;

}

3. 다음 설명으로 옳은 것은 무엇인가 ? 4번

 1) 우선순위 스택 : 대기 리스트에서 항상 우선순위가 높은 것을 먼저 처리하는 구조

 2) 스택 : 먼저 들어간 데이터가 먼저 삭제되는 자료구조

 3) 최대 힢 : 루트가 최소값인 힢

 4) 배열을 이용한 힢의 구현은 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음