노트

이진 힙

Binary Heap

CS#algorithm · 연결된 개념 5개

쉽게 말하면

이진 힙은 토너먼트 대진표처럼 각 자리에서 더 센 쪽이 위로 올라가는 구조예요. 그래서 맨 꼭대기에는 늘 가장 크거나 작은 값이 있어 바로 꺼낼 수 있어요.

비유의 한계 토너먼트와 달리 형제끼리는 겨루지 않아요. 부모와 자식 사이만 정해져 있어서 전체가 정렬된 게 아니고, 특정 값을 찾으려면 O(n)이 걸려요. 힙은 탐색용이 아니에요.

부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

배열로 표현한다

완전 이진 트리라서(왼쪽부터 빈틈없이 채운다) 포인터 없이 배열 하나로 담을 수 있다. 인덱스 n인 노드의 왼쪽 자식은 2n + 1, 오른쪽은 2n + 2, 부모는 Math.floor((n - 1) / 2)다.

연산

  • 삽입: 배열 끝에 넣고, 부모보다 크면(최대 힙) 자리를 바꾸며 올라간다(bubble up)
  • 꺼내기: 루트를 빼고, 마지막 원소를 루트로 옮긴 뒤 더 큰 자식과 바꾸며 내려간다(sink down, heapify)
function push(heap: number[], v: number) {
  heap.push(v)
  let i = heap.length - 1
  while (i > 0) {
    const p = Math.floor((i - 1) / 2)
    if (heap[p] >= heap[i]) break
    ;[heap[p], heap[i]] = [heap[i], heap[p]]
    i = p
  }
}

복잡도

삽입과 꺼내기는 트리 높이만큼인 O(log n), 최댓값 확인은 O(1)이다. 특정 값 찾기는 O(n)으로, 힙은 탐색용이 아니다(이진 탐색 트리와 다른 점).

우선순위 큐를 구현하는 표준 방법이고, 다익스트라 같은 그래프 알고리즘과 힙 정렬(Heapsort)에 쓰인다. 정렬 알고리즘 비교는 정렬 알고리즘.

책: 8장. 힙: 가장 큰 것 몇 개만

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 퀵 정렬

    기준값(피벗, Pivot)을 하나 골라 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤, 양쪽을 다시 같은 방식으로 정렬하는 알고리즘. 나누고 나면 피벗은 최종 자리에 놓이므로 합치는 단계가 필요 없다.

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 이진 탐색

    정렬된 배열에서 가운데 값과 찾는 값을 비교해 매번 절반을 버리며 찾는 방법. 원소가 100만 개여도 20번 남짓이면 끝난다(O(log n)). 처음부터 하나씩 확인하는 선형 탐색(Linear Search)은 O(n)이다.

  • B-tree와 B+tree

    한 노드가 자식을 수백 개 가지는 균형 다진 트리. 높이가 낮아 디스크 페이지를 몇 번만 읽고 값을 찾으며, 잎이 정렬된 채 이어져 있어 범위 검색에 강하다.

  • 그래프

    정점(vertex, 노드)과 정점들을 잇는 간선(edge)으로 이루어진 자료구조. 트리도 그래프의 한 종류다. SNS 친구 관계, 지도와 경로, 웹 페이지 링크, 추천 시스템, 패키지 의존성처럼 "무엇과 무엇이 연결돼 있다"는 모든 것을 표현한다. 이 지식 맵도 노트를 정점, 링크를 간선으로 한 그래프다.

보기 옵션