자료구조 Heap

김성호·2023년 3월 28일
자료구조
0

자료구조

목록 보기
7/7

Heap이란?

힙(Heap)은 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(Complete Binary Tree)를 기반으로 한 자료구조입니다.

힙은 두 종류가 있습니다.

  • Max Heap : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진트리
  • Min Heap : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진트리

Heap의 특징

  • 최대값(Max Heap) 또는 최소값(Min Heap)을 빠르게 찾을 수 있습니다. 최대값(Max Heap) 또는 최소값(Min Heap)이 항상 루트 노드에 위치하기 때문입니다.
  • 삽입(Insert) 및 삭제(Delete) 연산의 시간복잡도는 O(log n)입니다. 트리의 높이(log n)만큼 연산을 수행하기 때문입니다.
  • Heap은 다른 자료구조와 함께 사용될 수 있습니다. 예를 들어, Heap을 이용하여 Dijkstra 알고리즘, Prim 알고리즘 등의 그래프 알고리즘을 최적화할 수 있습니다.

Heap의 연산

  • 삽입(Insert): 새로운 요소를 추가합니다. 일반적으로 완전 이진트리의 마지막 노드에 추가하고, 새로 추가된 노드를 부모 노드와 비교하여 힙 조건을 만족시킵니다.
  • 삭제(Delete): 최대값(Max Heap) 또는 최소값(Min Heap)을 제거합니다. 일반적으로 루트 노드를 제거하고, 마지막 노드를 루트 노드로 이동시킨 후 힙 조건을 만족시킵니다.

많이 들어본 듯한 Heap

Heap이란 단어는 OS에서 프로세스, JVM의 메모리 영역 중 Heap 영역을 통해 많이 들어봤습니다. 언뜻 생각하기에 이 것들이 같은 걸 말하는 건가 해서 알아봤습니다.

일단 프로세스, JVM의 메모리 영역의 Heap과 자료구조 힙은 아예 다른 것이었습니다.

메모리 영역 중 힙은 동적으로 메모리를 할당받는 메모리 영역을 말합니다. 메모리가 비연속적인 공간을 사용하며 프로그램 실행 중에 동적으로 메모리를 할당하고 해제할 수 있습니다. Java에서 new연산자를 통해 Heap에 메모리를 할당할 수 있습니다.

프로그래밍에서 일반적으로 Heap이라고 하면 자료구조 힙이 아니라 메모리 영역 Heap을 말한다고 합니다.

Heap의 구현

Heap을 구현하는 여러 방법이 있지만 일반적으로 배열(Array), 완전 이진트리(Complete Binary Tree)를 통해 구현된다고 합니다.

배열을 사용한 Heap은 일차원 배열로 구현되며, 각 노드는 배열의 인덱스에 해당합니다. 루트 노드는 항상 인덱스 0에 위치하며, 자식 노드는 각각 왼쪽 자식과 오른쪽 자식으로 배열의 인덱스를 이용하여 계산됩니다. 배열을 사용한 Heap은 메모리를 덜 사용하고 삽입/삭제 연산이 빠른 장점이 있습니다.

완전 이진트리를 사용한 Heap은 이진트리(Binary Tree) 중에서도 완전 이진트리(Complete Binary Tree)를 사용합니다. 완전 이진트리는 노드가 왼쪽에서부터 차례대로 채워지는 이진트리로, Heap에서는 루트 노드가 완전 이진트리의 맨 위에 위치하며, 자식 노드는 왼쪽부터 채워지기 때문에 배열과 유사한 구조를 가지고 있습니다.

그러나 완전 이진트리 또한 Array로 구현하는 것이 Linked List로 구현하는 것보다 삽입, 삭제 연산이 빠르기 때문에 Heap은 Array로 구현하면 됩니다. Linked List로 구현하는게 좋은 케이스는 노드의 개수가 너무 많아지는 경우 배열로 구현하기 어렵기 때문에 이 때는 Linked List로 구현하는게 좋습니다.

Heap과 우선순위 큐(Priority Queue)

Java에서는 PriorityQueue 클래스를 이용하여 우선순위 큐를 구현할 수 있습니다. PriorityQueue 클래스는 Heap을 이용하여 구현되며, 기본적으로 최소 힙(Min Heap)을 사용합니다.

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 우선순위 큐 생성
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        
        // 원소 추가
        pq.add(3);
        pq.add(1);
        pq.add(5);
        
        // 최소값 반환 및 삭제
        System.out.println(pq.poll()); // 1
        
        // 원소 추가
        pq.add(2);
        
        // 전체 출력
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
        // 2, 3, 5
    }
}

Heap으로 구현된 우선순위 큐는 다음과 같은 곳에서 사용됩니다.

  1. 작업 스케줄링: 우선순위 큐를 이용하여 CPU나 I/O 등의 자원을 가장 많이 사용하는 작업을 먼저 처리합니다.
  2. 네트워크 트래픽 제어: 우선순위 큐를 이용하여 네트워크 트래픽을 관리합니다. 대역폭이 제한된 경우, 우선순위 큐를 이용하여 중요한 데이터를 먼저 전송합니다.
  3. 데이터 압축: Huffman 알고리즘에서는 우선순위 큐를 이용하여 최적의 문자열 압축을 구합니다.
  4. 이벤트 처리: GUI(GUI) 프로그래밍에서는 이벤트 처리를 위해 우선순위 큐를 이용합니다. 사용자가 발생시킨 이벤트 중에서 우선순위가 높은 이벤트를 먼저 처리합니다.
  5. Dijkstra(다익스트라) 알고리즘: 최단 경로를 찾는 Dijkstra 알고리즘에서는 우선순위 큐를 이용하여 노드를 방문하는 순서를 결정합니다.
  6. A 알고리즘: 경로 탐색 알고리즘인 A 알고리즘에서도 우선순위 큐를 이용하여 경로를 탐색합니다.
profile
김성호
개발공부하는사람
이전 포스트

Deque

0개의 댓글