Heap or binary heap

mon99745·2022년 6월 13일
0
post-thumbnail

🤔 목적

컴퓨터공학의 기초가 되는 cs지식을 되새기면서 이 후 있을 기술면접을 대비 하고자한다.

힙(Heap)이란?

Heap은 이진 힙(binary heap)이라고도 하며, 무언가 쌓아 올린 더미라는 뜻을 갖고 완전 이진 트리의 형태로 만들어진 자료구조이다
이외에도 아래와 같이 정의할 수 있다.

  • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
  • 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.
    • 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다는 정도
      즉, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다.
  • 힙 트리에서는 중복된 값을 허용한다.

힙(Heap)의 종류

최대 힙(Max Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 말한다
즉,

  • Key(parent) >= key(child)
  • 가장 큰 값이 루트 노드에 있다.

최소 힙(Min Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리를 말한다.
즉,

  • Key(parent) ≤ Key(child)
  • 가장 작은 값이 루트 노드에 있다.

힙(heap)의 표현

  • 힙을 저장하는 표준적인 자료구조는 배열이다.
  • 개발의 편의성과 가독성 때문에 배열 인덱스는 0이 아닌 1부터 사용한다.
  • 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다
    • 예를 들어 루트 노드의 오른쪽 노드는 번호가 항상 1이다.
  • 힙에서의 부모 노드와 자식 노드의 관계
    • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
    • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
    • 부모의 인덱스 = (자식의 인덱스) / 2

References (참고 자료)

0개의 댓글