노트

이진 힙

Binary Heap

CS#algorithm · 연결된 개념 4개

쉽게 말하면

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

비유가 깨지는 곳 토너먼트와 달리 형제끼리는 겨루지 않아요. 부모와 자식 사이만 정해져 있어서 전체가 정렬된 게 아니고, 특정 값을 찾으려면 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)에 쓰인다. 정렬 알고리즘 비교는 정렬 알고리즘.

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • 연결 리스트

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

  • 이진 탐색

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

  • 그래프

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

  • 재귀

    함수가 자기 자신을 다시 호출해 문제를 푸는 방식. 같은 함수를 점점 작은 입력으로 부르다가 더 나눌 필요가 없는 지점(기저 조건, Base Case)에서 멈춘다.

  • 트리 순회

    트리의 모든 노드를 한 번씩 방문하는 방법. 같은 층을 먼저 훑는 너비 우선(Breadth-First)과, 한 가지를 끝까지 내려가는 깊이 우선(Depth-First)이 있고, 깊이 우선은 노드를 언제 방문하느냐에 따라 셋으로 나뉜다.

보기 옵션