ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 알고리즘 기초 04) 힙 (Heap) 자료 구조
    Algorithm 공부자료/기본 알고리즘 정리 2020. 3. 12. 01:14

    사전 개념 : 우선순위 큐 (Priority Queue) 자료 구조

    우선 순위의 개념을 queue에 도입한 자료 구조이다.

    데이터들이 우선 순위를 갖고 있으며, 우선 순위가 높은 데이터가 먼저 빠져나간다.

     

    대표적인 사용처 : 시뮬레이션 시스템, 네트워크 트래픽 제어, CPU scheduling, 수치 해석적인 계산 등

     

    구현 : list (array), linked list, heap 등으로 구현이 가능하며, 이 중 heap으로 구현하는 것이 가장 효율적이다.

     

    개념

    complete binary tree의 일종으로 우선순위 큐의 구현을 위해서 만들어진 자료 구조이다. 시간 복잡도 : O(logN)

    여러 개의 값들 중에서 max 혹은 min value를 빠르게 탐색하기 위해서 만들어졌다. 

    중복된 값을 허용하지 않는 일반적인 complete binary tree와는 달리 heap tree에서는 중복된 값을 허용한다. 

     

    heap의 기본 속성 : A가 B의 부모 노드라면, A의 key value와 B의 key value에는 대소 관계가 성립하며, 해당 대소관계는 heap의 종류에 따라서 달라진다. 

     

    종류

     

    1) Max Heap : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 complete binary tree

    2) Min Heap : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 complete binary tree

     

    구현

    heap을 구현할 때는 보통 list (array) 자료 구조를 사용한다.

    구현의 편의를 위해서 보통 첫번째 Index는 사용하지 않으며, 새로운 노드가 추가된다고 해서 각 노드의 번호가 변경되지는 않는다.

     

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

    왼쪽 자식 노드의 Index : 부모 노드의 index * 2

    오른쪽 자식 노드의 index : 부모 노드의 index * 2 + 1

    부모 노드의 index : 자식 노드의 index / 2

     

    연산

    insertion (삽입) : heap 에 새로운 요소가 들어오며느 새로운 노드를 힙의 마지막 노드에 추가하여, 삽입을 해둔다. 새로운 노드를 부모 노드들과 비교하며 힙의 성질에 따라 교환 해 나간다. 

     

     

    deletion (삭제) : max heap에서의 deletion 연산을 생각해보자. max heap에서 max value는 root node이므로, root node를 삭제한다. 삭제된 root node에는 heap의 마지막 node를 일단 가져다 놓는다. heap의 성질에 따라서 비교하며 재구성한다.

     

     

     

     

     

    댓글

Written by Geulleun