CS 공부/자료구조

[CS 자료구조] Heap에 대해서

winterlove 2024. 7. 13. 14:56

힙(heap) 이란

힙이란 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조다.
우선순위 큐를 위해 만들어진 자료구조이다.

우선순위 큐 (Priority Queue)
큐는 FIFO(First In, First Out) 형식의 자료 구조.
우선순위 큐는 먼저 들어오는 데이터가 아닌, 순위가 높은 데이터가 먼저 나가는 형태의 자료구조다.
힙을 이용하여 구현함

insert(x) : 우선순위 큐에 요소 x 추가
remove() : 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
find() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환
  1. 완전 이진 트리(Complete Binary Tree) 기반의 자료구조 
  2. 힙은 일종의 반정렬( 느슨한 정렬 ) 상태를 유지한다.
    큰 값이 상위 작은 값이 하위 레벨에 존재. 즉, 부모 키 값이 자식 노드 키 값보다 항상 크거나 작은 이진트리
  3. 루트 노드( 최상위 노드) 가 최댓값 또는 최솟값을 가진다.
  4. 배열로 표현 가능하며 중복을 허용한다.

힙(heap)의 종류

  1. 최대 힙 : 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리 ( 부모 >= 자식 )
  2. 최소 힙 : 부모 노드가 자식 노드보다 작거나 완전 같은 이진트리 ( 부모 <= 자식 )

힙을 저장하는 표준 자료 구조는 배열이다.
일반적으로 루트 노드가 index 1에 위치한다.

예를 들어서 5, 5, 7, 7, 2, 6, 3 순서대로 힙에 삽입하는 예시를 들어본다면

최대 힙

    7
   / \
  7   6
 / \  / \
5   2 5  3


최소 힙

   2
  / \
 3   6
 / \ / \
5  7 5  7

기본 개념

  1. 완전 이진 트리의 특성
    루트 노드부터 왼쪽 -> 오른쪽 레벨 순대로 노드가 채워지며 마지막 레벨의 노드는 왼쪽부터 차례로 채워져 있다.
    힙은 부모 노드의 값이 자식노드보다 크거나 작은 규칙을 따른다. ( 최대/최소)

  2. 부모-자식 관계
    완전 이진트리에서 각 노드는 최대 두 개의 자식 노드를 가질 수 있다.

    부모 노드 인덱스 i 일 때,
    왼쪽 자식 노드 인덱스       [ 2*i + 1 ]
    오른쪽 자식 노드 인덱스    [ 2*i + 2 ]

  3. 배열을 이용한 힙 구현
    인덱스 0에서 시작하는 배열 사용
    특정 노드의 인덱스 i 일 때,
    왼쪽 자식 노드 인덱스       [ 2*i + 1 ]
    오른쪽 자식 노드 인덱스    [ 2*i + 2 ]
    부모 노드 인덱스                [ (i-1) / 2 ]

힙(heap)의 연산

  1. 삽입 ( Push )
    새로운 요소를 힙 마지막에 추가.
    속성 유지 위해 상향식 조정( bubble-up, Up-Heapify ) 부모와 비교하여 적절 위치에 배치한다.

  2. 삭제 (Pop )
    힙에서의 삭제는 일반적으로 루트 노드(최상위)를 삭제하는 연산을 말한다.
    최상위 노드 삭제 후 마지막 노드를 루트로 이동 (완전 이진 트리 성질 유지하게 됨)
    속성 유지 위해 하향식 조정 ( bubble-down, Down-Heapify ) 자식과 비교하여 적절 위치에 배치한다.

  3. 검색
    루트 값에 바로 접근이 가능하기에 최댓값, 최솟값 검색을 바로 할 수 있다.
    특정 값을 검색하기 위해서는 모든 노드를 순회해야 한다.
    특정 값 업데이트 또한 지원하지 않으며 삭제 후 다시 삽입하는 방법을 사용한다.

Heapity 작업

Up-Heapify (상향식 조정) - 요소 삽입 후 힙 속성 만족하도록 유지하는 과정

  1. 새로운 요소가 힙 맨 끝에 추가
  2. 추가 요소와 부모 요소 비교하여 만족시킨다.
    새 요소가 부모 노드보다 크거나 작은 경우, 위치 변경

Down-Heapify (하향식 조정) - 요소 삭제 후 루트 노드부터 힙 속성 회복하는 과정

  1. 요소 삭제 후 루트 노드 값 변경
  2. 루트에서 시작하여 자식과 비교하여 힙 속성 회복
    루트 - 자식 비교 중 루트보다 크거나 작은 경우, 위치 변경

시간 복잡도 분석

  1. insert - O(log n)
    힙에 새 요소를 삽입 시 상향식 조정을 수행하여 힙 속성을 유지해야 한다.
    이때, 삽입 위치까지 경로 길이에 비례하는 시간이 걸린다.
  2. remove() - O(log n)
    삭제 시 루트 노드를 삭제하고 하향식 조정을 수행하기에 O(log n) 시간이 소요된다.
  3. find() - O(1)
    루트 노드를 반환

예를 들어 n=10이라면 log2 10은 약 3.32다.

힙(heap)의 장점 & 단점

장점

  1. 빠른 삽입 및 삭제 : 특정 순서에 따라 정렬 상태를 유지하기에 O(log n) 시간 안에 이루어진다.

단점

  1. 임의 접근 어려움 : 특정 값에 접근하기 위해서는 O(n)의 시간이 걸린다.
  2. 정렬 유지 오버헤드 : 정렬 상태를 유지하기 위해 삽입, 삭제 연산 시 오버헤드 발생시킬 수 있다.
  3. 배열로 구현 시 추가적 공간 요구 : heap은 일반적으로 배열, 연결 리스트를 사용해 구현되기에 공간을 미리 할당하여 요소 개수에 따라 적절한 크기를 선택해야 한다.

즉, heap은 삽입, 삭제 연산에는 뛰어난 성능을 보이나 임의 접근, 정렬은 한계가 있다.

예시 응용 

자바에서의 우선순위 큐 사용 예시

public static void main(String[] args) {

     //기본적으로 최소 힙이 생성
     PriorityQueue<Integer> pq = new PriorityQueue<>();

    // offer(x) : Heap에 값 삽입
    pq.offer(5); 
    pq.offer(3); 
    pq.offer(7); 
    
    // peek() : 가장 높은 순위를 가진 값 반환
    System.out.println("Root Node search : " + pq.peek());

    // poll() : 최상위 노드 삭제 후 반환
    System.out.println("Root Node Remove : " + pq.poll());

    System.out.println("Root Node search : " + pq.peek());

	
    
    //최대 힙 생성 위해서는 Collections.reverseOrder()를 사용해서 반대로 만들어준다.
    PriorityQueue<Integer> pqm = new PriorityQueue<>(Collections.reverseOrder());

    // offer(x) : Heap에 값 삽입
    pqm.offer(5); 
    pqm.offer(3); 
    pqm.offer(7); 
    
    // peek() : 가장 높은 순위를 가진 값 반환
    System.out.println("Root Node search : " + pqm.peek());

    // poll() : 최상위 노드 삭제 후 반환
    System.out.println("Root Node Remove : " + pqm.poll());

    System.out.println("Root Node search : " + pqm.peek());
    
}
Root Node search : 3
Root Node Remove : 3
Root Node search : 5

Root Node search : 7
Root Node Remove : 7
Root Node search : 5

 

 

저작자표시 비영리