[algorithm]heap

less than 1 minute read

Heap

우선순위 큐

우선순위 큐에서 사용되는 자료구조

  • 우선순위 큐
    • 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 빠져나간다.
    • 우선순위 큐 이용 사례
      • a.네트워크 트래픽 제어
      • b.운영체제의 작업 스케줄링

Heap

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

Heap의 종류

  • 최대 힙(max heap)

    • 부모노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리
    • 부모노드 key >= 자식노드 key
  • 최소 힙(min heap)

    • 부모노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리
    • 부모노드 key <= 자식노드 key

    Heap의 구현

    • 배열을 통해 구현한다.
    • 부모노드와 자식노드의 관계
      • 왼쪽 자식의 인덱스 = (부모의 인덱스)*2
      • 오른쪽 자식의 인덱스 = (부모의 인덱스)*2+1
      • 부모의 인덱스 = (자식의 인덱스)/2

Updated: